## Prime number Hash table

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

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

### Prime number Hash table

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
AlvaroBegue
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 power-of-2 size is fine unless your hash function is broken. If your hash function is mediocre and you want to improve the distribution, pass your 64-bit hash through an avalanche function to mix in all the bits:

Code: Select all

``````uint64_t avalanche(uint64_t x) {
x ^= x >> 32;
x *= 0xf959d19084fd5339ull;
x ^= x >> 32;
return x;
}
``````
Probably even just the first two lines would be enough for this purpose, and it should be faster to evaluate than a modulo operation.
hgm
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.)
Volker Annuss
Posts: 180
Joined: Mon Sep 03, 2007 9:15 am

### Re: Prime number Hash table

jackk03
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
BeyondCritics
Posts: 406
Joined: Sat May 05, 2012 2:48 pm
Full name: Oliver Roese

### Re: Prime number Hash table

jackk03 wrote: Sun Jan 21, 2024 5:13 pm 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.
...
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.