Hash Table and Set

Hash Table and Set

Imagine a coat-check counter. You hand over a coat, the clerk computes a locker number from your ticket, and stores the coat there. To get it back, they recompute the same number and walk straight to that locker — no scanning the whole rack. A hash table works exactly this way: instead of searching for a key, it computes where the key should live. That single idea — turn a key into an array index by arithmetic — is what buys us average O(1) lookup, insertion, and deletion, the fastest general-purpose associative structure we have.

A set is the same machine with the coats thrown away: we keep only the tickets. It answers one question fast — "have I seen this before?" A hash table (a map/dictionary) stores key→value; a hash set stores just keys. Internally they are the same skeleton, so their costs are identical.

Precise definition

A hash table is an array of m slots ("buckets") plus a hash function h(key) that maps any key to an index in [0, m). Because the universe of keys is far larger than m, two distinct keys can map to the same bucket — a collision. Every real hash table needs a collision strategy:

• Separate chaining: each bucket holds a small list (or tree) of entries that hashed there. Lookup finds the bucket, then scans that short list.
• Open addressing: all entries live in the array itself; on collision, probe other slots by a rule (linear, quadratic, or double hashing) until an empty or matching slot is found.

The key performance knob is the load factor α = n / m (entries per bucket). To keep chains short and probe sequences fast, the table resizes — typically doubling m and rehashing every entry — once α crosses a threshold (Java's HashMap uses 0.75; Go's map ~6.5 per bucket).

Worked example: counting operations

Take a tiny table with m = 8 buckets and the hash h(k) = k mod 8, using separate chaining. Insert the keys [5, 21, 13, 40]:

• h(5) = 5 → bucket 5 empty, place. 1 write.
• h(21) = 21 mod 8 = 5 → bucket 5 occupied by 5. Compare (miss), prepend to chain. 1 compare + 1 write.
• h(13) = 13 mod 8 = 5 → bucket 5 now holds [21, 5]. Scan chain (2 compares, both miss), prepend. 2 compares + 1 write. Chain length is now 3.
• h(40) = 40 mod 8 = 0 → bucket 0 empty, place. 1 write.

Now search for 13: h(13) = 5, scan bucket 5 = [13, 21, 5], match on the 1st compare. Total = 1 hash + 1 compare. Search for 99: h(99) = 3, bucket 3 empty → miss in 1 hash, 0 compares. Notice the cost tracks the chain length, not n. Here three of four keys collided in bucket 5 — a degenerate hash. With α = 4/8 = 0.5 and a good hash, expected chain length is ~0.5, so lookups average roughly 1 compare regardless of table size.

Pitfalls & what an interviewer probes

• "O(1)" is average, not worst. Worst case is O(n) when every key collides into one bucket (bad hash, or an adversary feeding crafted keys — a real DoS vector, hash flooding). Modern maps mitigate this: Java converts a long chain into a balanced tree (O(log n)); Go and Python randomize the hash seed. Say "average O(1), worst O(n)" out loud.
• Mutable keys. If you mutate an object after using it as a key, its hash changes and you can never find it again. Keys must be immutable (or effectively frozen).
• Contract: equals + hashCode. Two keys that compare equal must hash equal, or lookups silently fail. This is the #1 subtle bug interviewers plant.
• No ordering. Iteration order is unspecified (and in some languages deliberately randomized). Need sorted keys or range queries? A hash table can't do it — reach for a balanced BST / TreeMap.
• Resize is amortized. A single insert can trigger a full rehash costing O(n), but spread over n inserts it averages O(1) each — amortized constant. Interviewers love the word "amortized."

When it matters & trade-offs vs neighbours

Hash tables are the default answer to "make this lookup fast": de-duplication, frequency counting, caches, memoization, join keys, and the classic interview trick of trading space for time (e.g. two-sum in one pass with a seen-map). Whenever a brute-force solution is O(n2) because of a nested "have I seen X?" search, a hash set usually collapses it to O(n).

• vs array/linear scan (O(n) search): the hash table wins on random access by key, but a plain array wins for tiny n, cache locality, and when you need positional/ordered access.
• vs balanced BST / TreeMap (O(log n)): the BST is slower per operation but gives sorted iteration, range queries ("keys between 10 and 50"), predecessor/successor, and a firm O(log n) worst case with no rehash spikes. Choose it when order matters or worst-case guarantees are contractual.
• Cost of the constant: hashing has memory overhead (empty buckets, load-factor slack) and its O(1) hides a non-trivial constant — computing the hash, chasing pointers, occasional cache misses. For a handful of elements, a linear scan is often literally faster.

Key takeaways

• A hash table computes a key's location via h(key), giving average O(1) insert/search/delete; a set is the same structure storing keys only.
• Costs track the load factor and collision handling — honest bounds are average O(1), worst O(n), with resizing making inserts amortized O(1).
• The killers are a broken equals/hashCode contract, mutable keys, and assuming any iteration order — none exists.
• Prefer a balanced BST when you need sorted order, range queries, or a guaranteed O(log n) worst case; prefer hashing when you only need fast keyed membership or lookup.