Algorithms Ch.3: How Hash Tables Make O(1) Lookup Real

0:00 Welcome to Learning Podcasts. Algorithms, chapter 3: hash tables. Today we explain how the data structure behind every dictionary in your code finds anything in constant time, no matter how big the table grows. Here is the question every system has to answer thousands of times per 2nd. You have a million customer records. Someone hands you an email address. Find the matching record. If you stored those records in an array, the only honest strategy is to walk the whole thing until you find the match.

0:31 That is O of n. Fine for a thousand records. Brutal for a million. Catastrophic for a billion. So we need a structure that does not get slower when the table gets bigger. That structure is the hash table. The promise is that lookup time stays flat as the table grows. A thousand records, a million, a billion: the average cost of finding a key is roughly the same. That is what people mean when they say O of one. The runtime does not grow with the input. Which is the whole reason your code never thinks about lookup cost when it indexes into a dictionary.

1:07 The trick is the hash function. A hash function takes any key, a string, a number, anything, and returns a fixed-size integer. The same key always returns the same integer. Different keys almost always return different integers. The hash table takes that integer, divides it by the number of buckets, and uses the remainder as the bucket index. So the key tells the table exactly which bucket to look in. Right. No walking, no searching. One arithmetic operation gets you to the bucket where the value lives.

1:38 That is the constant in constant time. And worth saying clearly: the hash functions used inside hash tables are not cryptographic. SHA-256 is overkill and far too slow for a per-lookup operation. Real hash tables use functions optimized for speed and uniform distribution, things like SipHash, MurmurHash, and the language-specific variants the runtime ships with. But there is a problem you cannot avoid. The hash function returns an integer in some huge range. The table only has, say, a thousand buckets.

2:10 The integers get squeezed down. Sooner or later, two different keys land in the same bucket. A collision. A collision. The rest of the chapter is about what hash tables do when that happens. The 1st strategy is called chaining. Each bucket holds a small linked list of all entries that hashed to it. Lookup goes to the bucket, walks the chain, compares each key, and returns the matching value. Linked lists inside the buckets. This is exactly the place chapter 2 said linked lists actually win. The bucket gives you the direct head pointer, you only ever splice at the head, and you only ever walk a few entries before you hit the match.

2:48 The list never grows long enough for the cache penalty to bite. The 2nd strategy is called open addressing. There are no linked lists. Every entry lives directly in a bucket. When a new key hashes to a bucket that is already taken, the table probes the next bucket, then the next, until it finds an empty slot. So lookup also probes forward until it finds the matching key or hits an empty slot. Right. The whole table is one contiguous array, every entry sits next to its neighbors, and the hot operation is a straight-line scan over a few buckets.

3:22 That is very friendly to the cache. Both strategies degrade as the table fills up. The number that captures this is the load factor: the ratio of entries to buckets. At a load factor of 0.5, half the buckets are empty and collisions are rare. At 0.8, collisions get common. As the load factor approaches one, lookup cost climbs sharply because every probe or chain walk gets longer. So you cap it well before it gets near one. Exactly. Real implementations enforce a load-factor cap and grow the table well before it gets too full.

3:58 The cap they pick is a tradeoff between memory and lookup speed. A lower cap, around 0.5, gives faster average lookup but wastes more memory on empty buckets. A higher cap, around 0.7 5, packs the table tighter at the cost of more frequent collisions. The choice depends on what the runtime is optimizing for. Growing the table is not free. When the load factor crosses the cap, the runtime allocates a new table with roughly twice as many buckets, walks every existing entry, recomputes its bucket index against the new size, and inserts it.

4:33 That single resize is O of n in the current entry count. But it amortizes. Right. Chapter 1's amortized argument applies again. The rare resize copies every entry, but the cost amortizes to constant per insert across the whole history of the table. So is hash table lookup actually O of one? Technically, no. If your hash function is bad and every key lands in the same bucket, the chain at that bucket grows to n entries, and lookup walks all of them. That is O of n. The worst case of hash table lookup is the same as walking an array from the front.

5:09 So why does the worst case never happen? Because real hash functions distribute keys uniformly across the bucket range. A million keys hashed by a good function land in roughly equal numbers across a million buckets. Collisions happen, but they stay short, usually one or two entries deep. The constant time you see in practice is the average, and the average is what dominates. But there is a real attack vector here. Right. The worst case is reachable if an attacker can choose keys that all hash to the same bucket.

5:40 That is called a hash flooding attack. The defense most modern hash tables use is to randomize the seed of the hash function at startup. Python's dict does this. Java's HashMap does this. The seed is process-local and unpredictable, so an attacker cannot precompute colliding keys. With that protection in place, the worst case essentially never shows up. Now the implementations you actually use. Python's dict type uses open addressing. When a key collides, Python perturbs the hash and probes the next slot in a non-linear pattern, which avoids the long runs of consecutive collisions that simple linear probing produces.

6:18 Python keeps the load factor under about two thirds and grows the table aggressively when it crosses that cap. All inside the brackets when you write `users[email]`. Exactly. Every dictionary access in Python is one hash, one probe, almost always one bucket lookup, and a returned value. Java's HashMap class made the other choice. It uses chaining. Each bucket holds a small linked list, and the table grows when the load factor crosses about three quarters. There is one twist: if a single bucket's chain ever crosses about 8 entries, Java converts that bucket from a linked list into a small balanced tree.

6:56 So the worst-case lookup at that bucket goes from O of n down to O of log n. Right. It is a defense against adversarial inputs that try to force every key into one bucket. One more pattern worth seeing. Redis is an in-memory key-value store, and its dictionary holds millions of keys. A naive resize would freeze the whole server while it rehashed every entry. Redis avoids that with incremental rehashing. When the table needs to grow, Redis allocates the new table beside the old one. Reads check both. New writes go to the new table.

7:30 And on every operation, Redis migrates one bucket from the old table to the new. So the resize happens in tiny pieces, spread across thousands of regular requests. No latency spike. The resize is invisible. One closing pointer. The same hashing idea extends across machines. In a distributed cache or a sharded database, a hash function decides which server holds each key. The naive version of that, hash modulo the number of servers, falls apart the moment you add or remove a server, because suddenly every key gets a new home and the cache empties.

8:07 Consistent hashing solves that. It maps both servers and keys onto a single ring, and each key lives on the next server clockwise. When a server is added, only the keys between it and its predecessor move. When a server is removed, only its keys move. The blast radius of a topology change is roughly one over N instead of all of it. We will come back to it later in the series. Next chapter we move from lookup by key to ordering and priority. Stacks, queues, heaps, and the schedulers that run on top of them.

8:38 Thanks for listening to Learning Podcasts.