Asked out loud, answered out loud. Read the answer, then say it in your own words.
How does a hash table give you O(1) lookup?
The key is hashed to an integer, that integer is reduced modulo the number of buckets, and the entry lives in that bucket — so finding it is arithmetic, not searching. The O(1) is average case and it depends on the hash spreading keys evenly. If every key lands in one bucket you have written a linked list with extra steps, and lookup degrades to O(n).
That degradation is a real attack: hash-flooding sends crafted keys that all collide. It is why runtimes seed their hash functions randomly per process.
What happens on a collision?
Two strategies. Chaining keeps a list (or a small tree) per bucket and appends — simple, tolerant of a high load factor, and it costs a pointer chase. Open addressing probes for the next free slot in the same array — no pointers, cache-friendly, but it degrades sharply as the table fills and deletion needs tombstones so a probe sequence is not broken.
What is the load factor, and what happens when it is exceeded?
Entries divided by buckets. Once it crosses a threshold — around 0.75 for chaining, lower for open addressing — collisions stop being rare and lookups start walking. The table then resizes: it allocates roughly double the buckets and rehashes every key, because the bucket index depends on the bucket count. That single operation is O(n), which is why insertion into a hash table is amortised O(1) rather than plain O(1).
If you know the size in advance, pre-sizing the map skips every intermediate rehash. It is one of the cheapest wins in a hot loop.
What makes a good hash function here?
Fast, deterministic within a process, and it must avalanche — flipping one bit of the key should change about half the bits of the output, so near-identical keys do not land in neighbouring buckets. It does not need to be cryptographic; a hash table is not a security primitive, and using SHA-256 as a dictionary hash buys nothing but latency.
