|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
good hash table primes
|
(Result)
|
|
|
In the course of designing a good hashing configuration, it is helpful to have a list of prime numbers for the hash table size.
The following is such a list. It has the properties that:
- each number in the list is prime (as you no doubt expected by now)
- each number is slightly less than twice the size of the previous
- 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.
Bon hashétite!
|
"good hash table primes" is owned by akrowne.
|
|
(view preamble | get metadata)
Cross-references: percent, order, columns, face, powers of two, number, properties, size, hash table, prime numbers, configuration, hashing
There is 1 reference to this entry.
This is version 6 of good hash table primes, born on 2002-08-21, modified 2004-02-24.
Object id is 3327, canonical name is GoodHashTablePrimes.
Accessed 24290 times total.
Classification:
| AMS MSC: | 68P20 (Computer science :: Theory of data :: Information storage and retrieval) | | | 68P10 (Computer science :: Theory of data :: Searching and sorting) | | | 68P05 (Computer science :: Theory of data :: Data structures) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
