Linear Probing with Constant Independence
Authors:
- Anna PaghAPAnna Pagh
- Rasmus PaghRPRasmus Pagh
- Milan RužićMRMilan Ružić
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (3) , 1107-1120
Abstract
Hashing with linear probing dates back to the 1950s and is among the most widely studied algorithms. In recent years, it has become one of the most important hash table organizations because it uses the cache of modern computers very well. Unfortunately, previous analyses relied either on complicated and space-consuming hash functions, or on the unrealistic assumption of free access to a hash function with random and independent function values. Carter and Wegman, in their seminal paper on universal hashing, have already raised the question of extending their analysis to linear probing. However, we show in this paper that linear probing using a pairwise independent family may have expected logarithmic cost per operation. On the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. This resolves the question of finding a space- and time-efficient hash function that provably ensures good performance for linear probing.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- String Hashing for Linear Probing2009
- Strongly History-Independent Hashing with Applications2007
- Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins2005
- Cuckoo hashingJournal of Algorithms, 2004
- On Universal Classes of Extremely Random Constant-Time Hash FunctionsSIAM Journal on Computing, 2004
- PrefaceAlgorithmica, 1998
- Randomized algorithms and pseudorandom numbersJournal of the ACM, 1993
- A complexity theory of efficient parallel algorithmsTheoretical Computer Science, 1990
- New hash functions and their use in authentication and set equalityJournal of Computer and System Sciences, 1981
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979