Universal and Perfect Hashing

http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0215.pdf

Hashing is a great practical tool, with an interesting and subtle theory too. In addition to its use as
a dictionary data structure, hashing also comes up in many different areas, including cryptography
and complexity theory. In this lecture we describe two important notions: universal hashing (also
known as universal hash function families) and perfect hashing.
Material covered in this lecture includes:
• The formal setting and general idea of hashing.
• Universal hashing.
• Perfect hashing.