Hash tables in practice (1)
The following trials compare the performance of three hash tables, each with m buckets:
- a CBHT
- an OHBT with step length s = 1
- an OHBT with step length s determined by double hashing.
The hash function distributes keys uniformly among the buckets (i.e., the probability that a key is mapped to any particular bucket is 1/m).
In each trial, all three hash tables are loaded with the same set of n randomly-generated keys.