CS369N: Beyond Worst-Case Analysis Lecture #6: Pseudorandom Data and Universal Hashing∗

This lecture discusses a very neat paper of Mitzenmacher and Vadhan [8], which proposes a robust measure of “sufficiently random data ” and notes interesting consequences for hashing and some related applications. We consider hash functions from N = {0, 1}n to M = {0, 1}m. Canonically, m is much smaller than n. We abuse notation and use N,M to denote both the sets and the cardinalities of the sets. Since a hash function h: N → M is effectively compressing a larger set into a smaller one, collisions (distinct elements x, y ∈ N with h(x) = h(y)) are inevitable. There are many way of resolving collisions. One that is common in practice is linear probing, where given a data element x, one starts at the slot h(x), and then proceeds to h(x) + 1, h(x) + 2, etc. until a suitable slot is found. (Either an empty slot if the goal is to insert x; or a slot that contains x if the goal is to search for x.) The linear search wraps around the table (from slot M − 1 back to 0), if needed. Linear probing interacts well with caches and prefetching, which can be a big win in some application. Recall that every fixed hash function performs badly on some data set, since by the Pigeonhole Principle there is a large data set of elements with equal hash values. Thus the analysis of hashing always involves some kind of randomization, either in the input or in the hash function. The best-case scenario occurs when the hash function h that you use spreads out the data set S ⊆ N that you care about as evenly as possible, say as if each hash value h(x) was an independent and uniform random sample from M. How could this “perfectly random ” scenario arise? 1. A fixed hash function that maps N/M elements to each of the M slots (e.g., using the low-order bits) and a uniformly random data set S. This is clearly an overly strong assumption on the data. ∗ c©2009, Tim Roughgarden