Suggested Final Project Topics

Why it's worth studying: Hopscotch hashing is an interesting mix of theory and practice. On the one

hand, the analysis of hopscotch hashing calls back to much of the formal analysis of linear probing hash

tables and therefore would be a good launching point for a rigorous analysis of linear probing. On the

other hand, hopscotch hashing was designed to work well in concurrent environments, and therefore

might be a good place to try your hand at analyzing parallel data structures.

Why Simple Hash Functions Work

Many of the data structures we talked about (cuckoo hashing, count sketches) required hash functions

with strong independence guarantees. In practice, people tend to write pretty mediocre hash functions that

don't meet these criteria, yet amazingly they tend to work out quite well. Why exactly is this? In 2007,

Michael Mitzenmacher and Salil Vadhan published a paper explaining why, in most cases, weak hash

functions work well by showing how they preserve the underlying entropy in the data source.