To test the above hypothesis, we implemented both double hashing and the
new exponential hash function. Table sizes were determined using the
double prime criterion, where N=p=2t+1 is required for the exponential
hash function, with p and t both prime. The Miller-Rabin
probabilistic primality test was used to determine the next largest
prime table size meeting this criterion given a target table size.
Based on the earlier analyses for both,
functions this should produce optimal probe lengths.
All trial runs were done by creating two identical empty hash tables
of the same size. Elements chosen at random from the data distributions
described below were successively added to the table to achieve a
load factor of 95% (
) of the table size. The measure
of merit was the average number of probes required per element added.
For example, if k elements take a total of m probes, the average
probes per element is simply 
. Samples of this metric were taken
every 5% of the table load factor, from 
, in order to
determine the behavior as load factor increased.
Five experiments are presented here: