Hash Table

Keys to values, fast.

A hash table (a.k.a. hash map / dictionary) stores pairs of keys and values and lets you look up a value by its key almost instantly. A hash function turns the key into a number that tells the table which slot ("bucket") the value lives in.

• put(key, value), get(key), remove(key) — average O(1).
• Keys are unique; putting an existing key overwrites its value.
• Backs language dictionaries: Python dict, Java HashMap, JS objects/Maps.

Collisions and load factor.

Different keys can hash to the same bucket — a collision. Two main resolution strategies:

• Separate chaining — each bucket holds a list (or tree) of entries.
• Open addressing — probe for the next free slot (linear/quadratic probing, double hashing).

The load factor (entries ÷ buckets) drives performance. When it gets too high the table resizes (rehashes all entries into a bigger array) — an occasional O(n) cost that keeps average operations O(1).

Worst cases and quality.

• Worst case O(n) — if many keys collide (poor hash or adversarial input) a bucket degenerates to a list; Java 8+ converts long chains to balanced trees for O(log n) fallback.
• Hash quality — a good hash spreads keys uniformly; the equals/ hashCode contract must hold (equal keys → equal hashes).
• Hash flooding — attackers force collisions to DoS a server; mitigate with randomized/seeded hashing (SipHash).
• Ordering & iteration — plain hash maps have no order; linked/ordered maps and open-addressing layouts trade memory for locality and predictable iteration.