Hi,
while studying hash tables I read that if the number of entries of the table is a prime number, that can contribute to have a more uniform distribution and therefore reduce the number of collisions.
Now, this effect is obviously more obvious if the table in quesiton isn't costantly filled to near 100%, but I still think it could bring some small gain in performance.
Does any engine already have the hash table entries set to be a prime number? or has anyone already tried and tested this?
I expect the difference to be, if any, small, and I don't have the possiiblity of doing an accurate test with my engine by running thousands of games, so that's why I'm asking for help
Prime number Hash table
Moderators: hgm, Rebel, chrisw

 Posts: 17
 Joined: Wed Jul 12, 2023 1:38 pm
 Full name: Giacomo Porpiglia

 Posts: 931
 Joined: Tue Mar 09, 2010 3:46 pm
 Location: New York
 Full name: Álvaro Begué (RuyDos)
Re: Prime number Hash table
I remember reading an implementation that used prime numbers for hash table size many years ago (maybe gnuchess?). I don't think it makes much sense to do that. Using a powerof2 size is fine unless your hash function is broken. If your hash function is mediocre and you want to improve the distribution, pass your 64bit hash through an avalanche function to mix in all the bits:
Probably even just the first two lines would be enough for this purpose, and it should be faster to evaluate than a modulo operation.
Code: Select all
uint64_t avalanche(uint64_t x) {
x *= 0x61664b66ad5f0385ull;
x ^= x >> 32;
x *= 0xf959d19084fd5339ull;
x ^= x >> 32;
return x;
}

 Posts: 27931
 Joined: Fri Mar 10, 2006 10:06 am
 Location: Amsterdam
 Full name: H G Muller
Re: Prime number Hash table
If your Zobrist base keys are good, the distribution of probes over the table should already be as uniform as it could ever be. Size of the table has no effect on this at all. Sizes that are not powers of two just slow down the calculation of the index from the key, especially if you use modulo or division fin it. (Bob Hyatt once reported a slowdown of Crafty of about 20% just by using the modulo for calculating the index.)

 Posts: 180
 Joined: Mon Sep 03, 2007 9:15 am

 Posts: 17
 Joined: Wed Jul 12, 2023 1:38 pm
 Full name: Giacomo Porpiglia
Re: Prime number Hash table
Thanks Voler, yours seems a good idea, I will defenitely try it.
I actually tried to have a hash table with prime number of entries, and it didn't make any difference at all. I will try your idea to get rid of the modulo operation
I actually tried to have a hash table with prime number of entries, and it didn't make any difference at all. I will try your idea to get rid of the modulo operation

 Posts: 406
 Joined: Sat May 05, 2012 2:48 pm
 Full name: Oliver Roese
Re: Prime number Hash table
I remember having also stumbled over this, a long time ago. Interesting that this is still around, the net never forgets.
Back in the first days of programming you had to fight very hard for performance and every program had to be a big blob of everything, including your own hash table. And at that time multiplication was as slow as division, therefore modulo hashing was not uncommon. Seemingly some assumed that modulo hashing was the only sensible way of doing it, so much that they didn't bother to mention it. And if you are only using modulo hashing, it makes sense to make the hash table always prime sized, so that you are calculating in a field, otherwise there might be issues with zero divisors.
Obligatory fun fact:
Some cicade species breed only once in n years [1] , where n is a prime number. A suggested explanation is, that this minimizes the number of resonant frequencies.
[1] https://en.wikipedia.org/wiki/Cicada