On Sun, Nov 28, 2010 at 11:37:12PM +0000, Sad Clouds wrote: > I've had some issues with a hash table that was power of 2 in size, and > most of the keys were multiples of 4, or 8 integers, for example. > However making hash table size a prime number and using a good hash > function, results in very good key distribution. This works especially > well when hashing simple intergers, e.g. file descriptors, etc.
If you have issues with a power of 2 hash table size, you do not have a good hash function in first place. A simple multiplicative hash function like ((uint64_t)X * random32) >> 32 % size is known to provide good results for most choices of random32. The suggestion to use a prime number goes back to using primitive hash functions that don't properly avoid funnels. With a good hash function, using a non power of 2 size just tends to be slower. Joerg
