Universal and Perfect Hashing (lect1004) 计算机科学

Lecture 10Universal and Perfect Hashing10.1 OverviewHashing 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 h