Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / General Programming / hash function... Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

May 23, 2005, 04:46 AM


Usually, I use chars or strings as keys to a hash table... what if I want to use integers as keys? How should my hash function be like? A simple mod?



May 23, 2005, 05:32 AM

A simple mod will work, but might not be the optimal hash function. This depends on your actual data. What you want to do is have an even distribution of values across the slots of the hash table. If the data is very evenly distributed, then yeah, a mod would do just perfect, but if it's clustered together or have gaps, you might want to consider other formulas. For example, if your ints are actually pointers to objects, which would all be aligned to 4 byte boundaries, you might want to divide the value by 4 and then do the mod...


May 23, 2005, 05:45 AM

If you use mod and don't have a lot of hashentries, it could be wise to store an extra few bits/byte(s) in the hashentry itself, so you can make almost sure it's really the right data you are looking up, like an extra verification-code.

For instance you could store the left over from the mod, 10000 mod 1000 leaves 10.



May 23, 2005, 05:56 AM

10000 mod 1000 leaves 0?


May 23, 2005, 06:28 AM

Yah, but 10000 mod 1000 leaves 10..sort of. (10000 div 1000. :) )

Fabian 'ryg' Giesen

May 23, 2005, 12:21 PM

Entirely depends on the distribution of values you typically have.

This thread contains 6 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.