Card 10/ 10
Recap: Hash Tables
Hash, then index; collisions chain or probe; growing rehashes; and expected is not guaranteed.
Hash Tables comes down to the eight ideas below, each listed with the card that covers it.
| The idea | Where |
|---|---|
| A hash function turns a key into a hash code, and the code mod the capacity picks a bucket | Hash Tables: From Key to Slot |
| Chaining keeps a list in each bucket, and a lookup costs one hash code plus one list | Resolve Collisions by Chaining |
| Linear probing walks to the next free slot, builds clusters, and deletes with a marker | Chaining vs Linear Probing |
| The load factor is keys per bucket, and passing the threshold doubles the table | Load Factor and Resizing |
| Growing means rehashing every key, because each bucket depends on the capacity | Copying Buckets Across Unchanged on a Resize |
| A dict, a Map and a LinkedHashMap keep insertion order, and a HashMap promises none | Hash Map With Chaining in Python, Java and TypeScript |
| Many keys in one bucket make a lookup O(n) | When a Hash Lookup Stops Being O(1) |
| A key's hash code and equality must never change, and equal keys need equal hash codes | A Key Whose Hash or Equality Can Change |
The operations reduce to one rule: each costs O(1) while keys spread evenly, and O(n) once they pile into one bucket. Expected means on average over evenly spread keys, and amortised means averaged over many inserts. The O(n) row occurs in practice: a poor hash function, keys that share a pattern, or keys chosen by an attacker can each put most keys in one bucket.
| Operation | Cost | Case | Why |
|---|---|---|---|
| Look up, insert or delete a key | O(1), insert amortised | Expected | One hash code, then a bucket holding few keys |
| Look up, insert or delete a key | O(n) | Worst | Every key shares one bucket and is compared in turn |
| Grow and rehash | O(n) | Every case | Every key is placed again, but rarely enough to cost O(1) amortised per insert |
| Visit every key | O(n) | Every case | In insertion order only where the map promises it |
| Find the smallest key | O(n) | Every case | Buckets keep their keys in no sorted order |
Together they let you place a key by hand under either scheme, keep a table fast as it grows, and choose keys and built-ins that a map can always find and list in the order a program needs.
← → move through sections and cards