# good hash table primes

The following is such a list. It has the properties that:

1. 1.

each number in the list is prime

2. 2.

each number is slightly less than twice the size of the previous

3. 3.

each number is as far as possible from the nearest two powers of two

Using primes for hash tables is a good idea because it minimizes clustering in the hashed table. Item (2) is nice because it is convenient for growing a hash table in the face of expanding data. Item (3) has, allegedly, been shown to yield especially good results in practice.

And here is the list:

lwr upr % err prime
$2^{5}$ $2^{6}$ 10.416667 53
$2^{6}$ $2^{7}$ 1.041667 97
$2^{7}$ $2^{8}$ 0.520833 193
$2^{8}$ $2^{9}$ 1.302083 389
$2^{9}$ $2^{10}$ 0.130208 769
$2^{10}$ $2^{11}$ 0.455729 1543
$2^{11}$ $2^{12}$ 0.227865 3079
$2^{12}$ $2^{13}$ 0.113932 6151
$2^{13}$ $2^{14}$ 0.008138 12289
$2^{14}$ $2^{15}$ 0.069173 24593
$2^{15}$ $2^{16}$ 0.010173 49157
$2^{16}$ $2^{17}$ 0.013224 98317
$2^{17}$ $2^{18}$ 0.002543 196613
$2^{18}$ $2^{19}$ 0.006358 393241
$2^{19}$ $2^{20}$ 0.000127 786433
$2^{20}$ $2^{21}$ 0.000318 1572869
$2^{21}$ $2^{22}$ 0.000350 3145739
$2^{22}$ $2^{23}$ 0.000207 6291469
$2^{23}$ $2^{24}$ 0.000040 12582917
$2^{24}$ $2^{25}$ 0.000075 25165843
$2^{25}$ $2^{26}$ 0.000010 50331653
$2^{26}$ $2^{27}$ 0.000023 100663319
$2^{27}$ $2^{28}$ 0.000009 201326611
$2^{28}$ $2^{29}$ 0.000001 402653189
$2^{29}$ $2^{30}$ 0.000011 805306457
$2^{30}$ $2^{31}$ 0.000000 1610612741

The columns are, in order, the lower bounding power of two, the upper bounding power of two, the relative deviation (in percent) of the prime number  from the optimal middle of the first two, and finally the prime itself.

Happy hashing!

Title good hash table primes GoodHashTablePrimes 2013-03-22 12:57:37 2013-03-22 12:57:37 akrowne (2) akrowne (2) 10 akrowne (2) Result msc 68P05 msc 68P10 msc 68P20