2009/01/01 by Anna Pagh, Rasmus Pagh, Milan Ružić · 3 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Cryptography and Data Security #Caching and Content Delivery #Hash function #Double hashing #Linear hashing #Dynamic perfect hashing #K-independent hashing #Universal hashing #Computer science #Constant (computer programming) #Logarithm #Independence (probability theory) #Pairwise independence #Pairwise comparison #Theoretical computer science #Perfect hash function #Linear space #Hash table #Function (biology) #Mathematics #Discrete mathematics #Random function #Random variable #Statistics #Artificial intelligence
paper · doi:10.1137/070702278
openalex publication_date 2009/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.