Hash Table Definition

Question¶

What are hash tables and why do we need them?

A hash table stores key-value pairs and uses a hash function to map a key to an array index.

Main goal:
- Get fast average-time operations:
  - Lookup: \(O(1)\) average
  - Insert: \(O(1)\) average
  - Delete: \(O(1)\) average
Why we need them:
- Arrays are fast by index, but not by arbitrary key.
- Hash tables let us use strings, numbers, tuples, etc. as keys.
- They are the standard tool for:
  - Sets
  - Dictionaries/maps
  - Counting frequencies
  - Caching
  - Deduplication
Core idea:
- Compute hash(key).
- Convert it to a valid bucket index with modulo array size.
- Handle collisions, because different keys can map to the same index.
Collision handling:
- Separate chaining:
  - Each array slot stores a small list of entries.
- Open addressing:
  - If slot is occupied, probe for another slot.

For interviews, separate chaining is usually the cleanest to implement correctly.