Unit 5: Integer Data Structures

This unit covers:

• static perfect hashing
• dynamic perfect hashing
• x-fast tries
• y-fast tries
• lower bounds
• (fusion trees)

Material

• slides

• lecture notes

• Video 5-1 (2026-06-09): Recap (universal) hashing

• Video 5-2 (2026-06-15): Universal Hashing Guarantees

• Video 5-3 (2026-06-15): Perfect Hashing

• Video 5-4 (2026-06-15): Dynamic Perfect Hashing

• Video 5-5 (2026-06-16): Binary Tries

• Video 5-6 (2026-06-16): x-Fast Tries & y-Fast Tries

• Video 5-7 (2026-06-16): Cell-Probe Lower Bounds

Further sources

The presentation of hashing takes inspiration from

• Demaine. Advanced Data Structures. MIT Open Courseware

Dynamic perfect hashing follows the original paper:

• Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert, Tarjan. Dynamic Perfect Hashing: Upper and Lower Bounds. (1994).

The presentation of x-fast and y-fast tries is based on

• Morin. Open Data Structures.

---

Unit 4  ⋅  Syllabus  ⋅  Unit 6