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, 27:10): Recap (universal) hashing
  
• Video 5-2 (2026-06-15, 12:48): Universal Hashing Guarantees
  
• Video 5-3 (2026-06-15, 27:52): Perfect Hashing
  
• Video 5-4 (2026-06-15, 32:21): Dynamic Perfect Hashing
  
• Video 5-5 (2026-06-16, 19:05): Binary Tries
  
• Video 5-6 (2026-06-16, 32:02): x-Fast Tries & y-Fast Tries
  
• Video 5-7 (2026-06-16, 27:51): Cell-Probe Lower Bounds
  
• Video 5-7 (2026-06-22, 44:33): Cell-Probe Lower Bounds 2
  

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