ALCOMFT-TR-03-26

Dimitris Fotakis, Rasmus Pagh, Peter Sanders and Paul Spirakis
Space Efficient Hash Tables With Worst Case Constant Access Time
Århus, Patras and MPI. Work packages 4 and 5. September 2003.

Abstract: We generalize Cuckoo Hashing [PagRod01] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1+epsilon) n memory cells, for any constant epsilon > 0. Assuming uniform hashing, accessing or deleting table entries takes at most d = O(\ln(1)/(epsilon)) 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+epsilon) n space, and supports satellite information. Experiments indicate that d = 4 choices suffice for epsilon \approx 0.03. We also describe variants of the data structure that allow the use of hash functions that can be evaluted in constant time.

Postscript file: ALCOMFT-TR-03-26.ps.gz (129 kb).