Quote:Original post by hplus0603

To get the hash of some block of data:

unsigned int hash( unsigned char const * base, size_t size ) {  return crc32( base, size );}

To get the table index, given the hash:

unsigned int table_index( unsigned int h ) {  assert( !(table_size&(table_size-1)) );  return h & (table_size-1);}

This works for all non-0 powers of 2 for table_size. It also works for most kinds of data that you want to hash. If you don't have a crc32 function laying around (you'll find it in zip, zlib, etc), then you can use a linear congruential rng instead:

// note: I haven't tuned the specific constants used, they are // just examples. You probably want to tweak them so you get a // good spread in the lower bits given similar inputs.unsigned int hash( unsigned char const * base, size_t size ) {  unsigned int v = 0x54321;  while( size > 0 ) {    v = v*0xffeeddcb + *base + 0x938265;    ++base;    --size;  }  return v;}

Ohhhhkkkayayyy.....You lost me :P hahaha. Could you explain that a little more indepth, such as what to do with collison in thos cases, as well as what exactly each function does, and kinda step by step as to how I would impliment this? I raided my uni's library, and got "Itroduction to data structures and algorithms with C++ by Glenn W. Rowe (c) 1997 So i'll read that so I atleast know some of the terms :P Has anyone else read this book? Is it good or?

Cheers! =)

Quote:Original post by T1Oracle

Quote:Original post by SiCranehorrible slow '%' operation

Why would that be "horrible slow"? Something like...
*** Source Snippet Removed ***
Has to be fast on a modern processor. I would figure something like that would be optimized considering its frequency of use in software.

What you wrote is usually *much* slower than '%', considering that the hash value can be on range 0 to (2^32-1) and it is "reduced" on a tiny range like 0-1023. You might have to loop 1 million times in your "fast" loop to get the same result '%' does in one or two instructions.

I don't think '%' is horribly slow either. Computing the CRC or some other hash for a string probably takes so much longer that using '%' doesn't really matter. But I haven't done benchmarks, could very well be wrong (at least for small strings).

Quote:Original post by _Sigma
Could you explain that a little more indepth, such as what to do with collison in thos cases, as well as what exactly each function does, and kinda step by step as to how I would impliment this?

Your hashtable maps keys to values, so it is a function t:K->V, where K is the set of possible keys, and V is the set of possible values.
Your hash function maps each key to a much smaller hash, so it is a function h:K->H, where H is the set of all possible hash values.
Since K can contain much more keys than you have hash values of H available, multiple keys will have the same hash value. In other words, those keys collide.

To get around this, different techniques exist.
Internal hashing will find another place in the table itself, for instance by rehashing.
External hashing will not store the data itself in the table, but just a link to the data. If multiple entries can share the same hash, the link will be implemented as a linked list in most cases. Other options would be a tree or a second hash table (with a different hashing algorithm).

OK, super guys. thanks. I'll have a look at that.