Suggested Final Project Topics

Tabulation Hashing

In lecture, we’ve taken it as a given that we have good hash functions available. But how exactly do you go

about building these hash functions? One popular approach – which has the endorsement of CS legend

Don Knuth – is tabulation hashing, which breaks a key apart into multiple blocks and uses table-based

lookups to compute a hash code. Although tabulation hashing only gives 3-independence, which doesn’t

sound all that great, a deeper analysis shows that using this hashing strategy in certain contexts will per-

form much better than what might initially appear to be the case.