Hash Table Tutorial
Author
I've looked around(here, google), but I've yet to find a really good, really indepth tutorial about creating your own hash table class. Any good links? =)
Cheers
//edit. In C++ would be great too =)
Quote:Original post by SiCrane
Did you see this one when you were searching gamedev?
Yeah that tutorial is okay, but you could simply forget prime numbers altogether and non-power-of-two sized hash tables and use a CRC function.
It gives about the best hash you can get for practically any datatype you could be using, AND you can then use a power-of-two for the hash table size, avoiding that horrible slow '%' operation by using an '&' instead. I have found this to work exceptionally well in the real world, beating other commercial programs.
Also, if your table size reaches the capacity, then you simply create a new one of double the size. Conversely, if the size goes below 1/4 of the capacity, you may like to shrink it.
Author
Quote:Original post by SiCrane
Did you see this one when you were searching gamedev?
I did. I found it lacking in its explication tho..
@iMalc... Eh? Any tutorials on this method?
Have a look at http://burtleburtle.net/bob/hash/examhash.html
You'll notice that in the table at the botom, CRC does extremely well.
You'll notice that in the table at the botom, CRC does extremely well.
Author
What does funnel mean?
Ok, CRC does seem to be rather nice. Do you know of any tutorials describing how to impliment this?
Ok, CRC does seem to be rather nice. Do you know of any tutorials describing how to impliment this?
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;}Quote:Original post by SiCranehorrible slow '%' operation
Why would that be "horrible slow"? Something like...
// example of c=a%bc=a;while (c>b) c-=b;Has to be fast on a modern processor. I would figure something like that would be optimized considering its frequency of use in software.
Loops imply conditionals, and conditionals are slow. Multiply by several hundred thousand iterations for something like 563223%3, and thats pathetic.
Modulus is considered slow because it entails division, which is one of the slower operations. A more realistic example might look like this:
Modulus is considered slow because it entails division, which is one of the slower operations. A more realistic example might look like this:
template <typename T> T modulus(T a, T b) { return a-b*static_cast<int>(a/b); }Quote:Original post by T1OracleQuote:Original post by SiCranehorrible slow '%' operation
Why would that be "horrible slow"? Something like...
Hey now, if you're going to quote something, at least attribute it to the right guy. :P
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
