Linear Probing with 5-Independent Hashing

2015/09/15 by Mikkel Thorup, Thorup, Mikkel · 1 voice
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1509.04549

arxiv published 2015/09/15 · arxiv updated 2017/05/11

Abstract

These lecture notes show that linear probing takes expected constant time if the hash function is 5-independent. This result was first proved by Pagh et al. [STOC'07,SICOMP'09]. The simple proof here is essentially taken from [Patrascu and Thorup ICALP'10]. We will also consider a smaller space version of linear probing that may have false positives like Bloom filters. These lecture notes illustrate the use of higher moments in data structures, and could be used in a course on randomized algorithms.

Discussions

• The analysis by Thorup in arxiv.org/pdf/1509.04549 is fairly accessible, and as a bonus only requires 5-wise independence [bsky, 3 points, 1 comments]

Related

• Linear Probing with Constant Independence
• On the k-Independence Required by Linear Probing and Minwise\n Independence
• Two-way Linear Probing Revisited
• Tight Analyses of Ordered and Unordered Linear Probing
• A unified approach to linear probing hashing with buckets