68P05-GoodHashTablePrimes.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{GoodHashTablePrimes}
\pmcreated{2013-03-22 12:57:37}
\pmmodified{2013-03-22 12:57:37}
\pmowner{akrowne}{2}
\pmmodifier{akrowne}{2}
\pmtitle{good hash table primes}
\pmrecord{10}{33327}
\pmprivacy{1}
\pmauthor{akrowne}{2}
\pmtype{Result}
\pmcomment{trigger rebuild}
\pmclassification{msc}{68P05}
\pmclassification{msc}{68P10}
\pmclassification{msc}{68P20}

\endmetadata

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

%\usepackage{psfrag}
%\usepackage{graphicx}
%%%\usepackage{xypic}
\begin{document}
\PMlinkescapeword{size}

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:

\begin{enumerate}

\item each number in the list is prime 
\item each number is slightly less than twice the size of the previous
\item each number is as far as possible from the nearest two powers of two

\end{enumerate}

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:

\begin{center}
\begin{tabular}{lllc}
lwr & upr & \% err & prime  \\
\hline
$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 
\end{tabular}
\end{center}

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!
%%%%%
%%%%%
\end{document}