Hash Tables

Finding things in one step

An interactive lesson with 6 steps, about 5 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• A hash function jumps straight to a slot; collisions are resolved by probing.
• Average cost depends on the load factor α, not the number of items.
• Tables are resized when α gets too high (around 2/3).

Steps

1. Jump straight to the answer
2. Two keys collide
3. How full is too full?
4. Why so fast?
5. A half-full table
6. Keeping it fast