A hash table is like a hostel's room lockers

Lesson notes

Key points

• Picture a hostel porter who finds your key instantly because your room number tells him exactly which hook to check.
• Your name is the key, a rule turns it into a hook number, and the hook holds your value, so lookup is constant time on average.
• It breaks because two keys can hash to the same bucket, a collision, so real tables use chaining or probing to share space.

Definitions

Collision

Two different keys produce the same bucket index; resolved by chaining (lists) or open addressing (probing).

Takeaway: Hash maps keys to buckets fast, but collisions must be handled.

Direct lookupHash functionCollisions