Why a Hash Table's Performance Can Silently Degrade Over Time
A hash table is fast because it has room to spread items out. Fill it up without letting it grow, and it slowly turns into the slow, item-by-item search it was built to avoid.
A parking garage with 100 spaces works efficiently right up until it gets close to full — with 10 cars parked, finding an open spot near the entrance is instant; with 98 cars parked, you're circling every level hunting for one of the two spaces left. Nothing about the garage's design changed between those two situations — it's purely a function of how full it's gotten. A hash table, covered in this site's hashing article, degrades in almost exactly this way as it fills up.
The measurement that captures "how full" a hash table is called its load factor — roughly, the number of items stored divided by the number of available slots. At a low load factor, most slots are empty or hold just one item, so a lookup almost always finds its target directly, exactly as fast as the coat-check-ticket analogy from the hashing article promises. As the load factor climbs toward 1 (as many items as slots) and beyond, more and more slots end up holding multiple items that collided into the same slot, and each lookup has to check a short list of everyone sharing that slot instead of landing directly on the right one.
This is why every serious hash table implementation resizes itself automatically, well before it actually fills up completely — typically once the load factor crosses some threshold, often around 0.7, the entire table grows to roughly double its previous size and every existing item gets recomputed into a slot in the new, larger table. That resize operation is itself a relatively slow, one-time event, but it happens rarely enough, and buys back enough breathing room, that the average cost of every individual lookup stays fast over the structure's whole lifetime.
The part that catches developers off guard is that this degradation doesn't announce itself with an error or a warning — a hash table that's 95% full still works correctly, returning right answers every time, it just does measurably more work per lookup than it did when it was 20% full, and that slowdown compounds quietly as more items get added, especially in a long-running program that keeps accumulating data in a hash table that was pre-sized once at startup and never revisited.
The practical takeaway for anyone writing performance-sensitive code: if you know roughly how many items a hash table will eventually hold, pre-sizing it generously up front avoids paying for multiple resize operations one after another as it grows, and if a program that used to feel fast has started feeling sluggish specifically on lookups, an over-full hash table nobody's kept an eye on is a genuinely common, easy-to-miss cause worth checking before assuming the slowdown lives somewhere more exotic.