PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (230)
Orphanage
Unclass'd
Unproven (519)
Corrections (18)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] 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:

  1. each number in the list is prime (as you no doubt expected by now)
  2. each number is slightly less than twice the size of the previous
  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.

Bon hashétite!



"good hash table primes" is owned by akrowne.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

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 20211 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
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)