Jump to content
  • Advertisement
Sign in to follow this  
_Sigma

Hash Table Tutorial

This topic is 4613 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 =)

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
What does funnel mean?
Ok, CRC does seem to be rather nice. Do you know of any tutorials describing how to impliment this?

Share this post


Link to post
Share on other sites

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;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCranehorrible slow '%' operation

Why would that be "horrible slow"? Something like...

// example of c=a%b
c=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.

Share this post


Link to post
Share on other sites
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:


template <typename T> T modulus(T a, T b)
{
return a-b*static_cast<int>(a/b);
}



Share this post


Link to post
Share on other sites
Quote:
Original post by T1Oracle
Quote:
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!