Space Efficient Hash Tables with Worst Case Constant Access Time

Hashing} and show how this yields a simple hash table data structure that
stores $n$ elements in $(1+\e)\,n$ memory cells, for any constant $\e >
0$. Assuming uniform hashing, accessing or deleting table entries takes at
most $d=\Oh{\ln\frac{1}{\e}}$ probes and the expected amortized insertion
time is constant. This is the first dictionary that has worst case
constant access time and expected constant update time, works with
$(1+\e)\,n$ space, and supports satellite information. Experiments
indicate that $d=4$ choices suffice for $\e\approx 0.03$. We also describe
a hash table data structure using explicit constant time hash functions,
using at most $d=\Oh{\ln^2\frac{1}{\e}}$ probes in the worst case.

A corollary is an expected linear time algorithm for finding
maximum cardinality matchings in a rather natural model
of sparse random bipartite graphs.