main page — CS 650 Advanced Data Structures
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
- preliminary slides
- Video 5-1 (2026-06-09):
Recap (universal) hashing
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.