The Hash Table

To find a word in a paper dictionary you can start at page one and turn pages until you reach it. That is a linear search, O(n), and it gets slower as the dictionary gets thicker. Or you can use the index at the front: the spelling of the word tells you which page to open, and you go there directly. The size of the dictionary barely matters. The second method works because the word itself, put through a fixed rule, produces a position.

An array already has this ability. Give it an index and it reaches the element in O(1), because the address is computed from the index rather than searched for. But the index has to be a small non-negative integer. A hash table extends the same ability to any kind of key: a hash function turns the key — a string, an object, a pair of coordinates — into an integer, and that integer is used as the index into an array. Nothing is scanned. That is the whole idea. A hash table is not a new way to store data; it is an array, a rule for computing indexes, and a plan for when two keys compute the same one.

A hash function takes a key and returns an integer. It could compute almost anything, but three requirements decide whether the table works at all. Each one exists because of what goes wrong without it.

How does a string become a number? The classic method is a polynomial hash: multiply each character code by a power of 31 and add the results. For "cat" (c = 99, a = 97, t = 116):

hash("cat") = 99 × 31² + 97 × 31 + 116 = 95139 + 3007 + 116 = 98262

Why not simply add the character codes? Because then "cat" and "act" would produce the same value: same letters, different order. Multiplying by powers of 31 makes the position take part in the result — a character further to the left is multiplied by 31 more times. Written as a loop it is one line: h = h × 31 + code(c). The last step takes this large number modulo the bucket count, which pushes it into the range of legal array indexes. Try the machine yourself:

Option one: separate chaining. A bucket holds a list instead of a single entry, and a colliding entry is appended to that list. A lookup hashes to the bucket and then compares the keys in the list one by one. Java's HashMap works this way, and so does the implementation in §04.

Option two: open addressing. A bucket holds at most one entry. On a collision the table follows a fixed rule to find another free bucket. The simplest rule is to try the next bucket to the right, which is called linear probing. CPython's dict and Rust's standard HashMap use open addressing. It is friendlier to the CPU cache, because the next bucket probed is usually in the same cache line. Here are the same six keys under both strategies:

The fuller the buckets, the more often keys collide. The measure of "full" is the load factor: the number of stored entries divided by the number of buckets. A Java HashMap grows once the load factor passes 0.75 by default. Growing means allocating a bigger bucket array — the capacity doubles — and then placing every existing key again. That second part is called rehashing, and it is not optional. The index comes from hash % bucketCount, so changing the bucket count changes where a key belongs. For example, 98262 % 8 = 6 and 98262 % 16 = 6, so that key happens to stay; but 98270 % 8 = 6 while 98270 % 16 = 14, so that key moves. With a power-of-two capacity an entry in bucket i either stays at i or moves to i + oldCapacity, and every entry still has to be visited to find out which.

Rehashing means a single insert can cost O(n). Because the capacity doubles, that cost is spread over the insertions that follow, so insertion is O(1) amortized rather than O(1) every time. Why 0.75? Higher, and each bucket holds more entries on average, so the lists grow and the average lookup stops being constant. Lower, and many buckets stay empty and waste memory.

A bucket array with one list per bucket, and five methods: hash (locate), put, get, remove, and resize. Watch the line inside resize that computes the index again. That single line is the rehash described in §03.

Every language ships an industrial-strength hash table, and each ships it in two shapes. A Map (dictionary) stores key-value pairs. A Set stores keys only — it is the same hash table with no value attached, which is why a membership test is as fast as a map lookup. The APIs are similar. The mistakes are language-specific:

Every hash-table solution in this chapter does the same thing: it spends O(n) memory so that a search that would cost O(n) becomes one lookup that costs O(1) on average. Three signals tell you when that applies:

The first problem on LeetCode, and the prototype of the pairing signal. The task: find two numbers in the array that add up to target, and return their indexes. Brute force: two nested loops over every pair, O(n²). Where the improvement comes from: look at what the inner loop is doing. For each i, it searches the part of the array before i for target − nums[i]. That is a linear search. Put the numbers you have already passed into a hash table, and that search becomes one O(1) lookup:

The task: group the words that contain the same letters in a different order. Brute force: compare every pair of words, O(n² · k). Where the improvement comes from: instead of comparing words with each other, give every word a signature — a value that is identical for anagrams and different for everything else. Then a Map from signature to list collects the groups on its own:

The task: in an unsorted array, find the length of the longest run of consecutive values. Their positions do not matter, and the solution must be O(n). First idea: sort and scan — but sorting is O(n log n), which the problem rules out. Where the improvement comes from: put every value into a set, and "is x + 1 present" becomes O(1), so a run can be measured by walking right. Doing that from every value is still O(n²): in the run 1..100 you would count from 1, then from 2, then from 3. One rule fixes it: only start counting at the beginning of a run, that is at a value x for which x − 1 is not in the set: