Suggested Final Project Topics

Why it’s worth studying: FKS hashing is interesting in that it builds nicely on the mathematical tech-

niques we’ll cover for working with randomized data structures and that it was one of the earliest strate-

gies devised for building perfect hash tables. Going from the static case to the dynamic case is a bit tricky,

but is a great way of combining amortization and randomization in a single package.

Concurrent Hash Tables

Many simple data structures become significantly more complex when running in multithreaded environ-

ments. Some programming languages (most famously, Java) ship with an implementation of a hash table

specifically designed to work in concurrent environments. These data structures are often beautifully con-

structed and rely on specific properties of the underlying memory model.