Hash Tables

A hash table answers "what goes with this key" in the same time whether it holds ten keys or ten million. A hash function turns the key into an array index (see Arrays and Dynamic Arrays), and the answer sits at that index or a few slots away. The structure runs underneath every Python dictionary and set, every module's global variables, every in-memory cache and a database's hash joins.

Its constant time has a price: memory kept empty on purpose, a hash function that spreads keys evenly, and now and then a full rebuild. Lantern's index, from about 1.5 million terms to the records that contain them, is a hash table, and it is the reason one server can answer a search without reading the catalogue.

From Key to Slot

The hash function maps a key of any size to a large integer, 64 bits in CPython. The table reduces that integer to a slot number; when the table size is a power of two, it keeps the low bits. A lookup is then one hash, one array read at that slot and one key comparison to confirm that the entry found really is the key asked for.

So a lookup is O(1) in the number of keys and O(length) in the key, because the whole key is hashed. CPython pays that once per string and then keeps the hash inside the string object. On CPython 3.15, hashing a 10-megabyte string took 3 milliseconds the first time and well under a microsecond the second.

Collisions Are Certain

There are far more possible keys than slots, so some keys will share a slot, and much sooner than intuition expects. In a table of about four million slots, the size CPython would use for Lantern's terms, a collision becomes more likely than not after only about 2,400 keys. This is the birthday effect: the chance grows with the number of pairs of keys, and pairs grow with the square of the keys.

So every hash table needs a policy for collisions, and the two in use differ in where the colliding keys go.

Chaining and Open Addressing

Chaining keeps a small list of entries per slot, and a lookup walks the list at its slot. Java's HashMap works this way, and since Java 8 it turns a chain longer than eight entries into a balanced tree (Chapter 6). Open addressing stores every entry in the array itself. On a collision it probes a sequence of other slots until it finds the key or an empty slot. Python's dictionary and set work this way, and so do the current built-in maps of Rust and, since version 1.24, Go.

Open addressing wins on cache behaviour (Chapter 4): there are no chain nodes to hop between, and the probe reads slots of one array. It has one subtlety. Deleting a key cannot leave its slot empty, or a later lookup whose probe sequence passed through that slot would stop early and miss its key. So the slot gets a tombstone, a marker that says "deleted, keep probing", and tombstones are cleared only when the table is rebuilt.

Load Factor and Resizing

The load factor is the number of keys divided by the number of slots. As it rises, chains lengthen and probe sequences run into each other, so the table resizes at a threshold: two thirds full for CPython's dictionary, three quarters for Java's HashMap. Resizing allocates a larger array and reinserts every key. The insert that triggers it costs O(n); the average stays O(1), by the same amortized argument as a list's growth (Chapter 1).

d = {}
for i in range(3_000_000):
    d[i] = None       # resizes at 6, 11, 22, 43, 86, 171 ... 699,051, 1,398,102 and 2,796,203 keys

The listing inserts three million keys and notes each length at which the dictionary's size jumped. Each jump comes when the table would pass two thirds full, and each one moves the table to the next power of two. For Lantern's 1.5 million terms, the dictionary resized at 1,398,102 keys to a table of 4,194,304 slots, and with string keys the dictionary structure alone, before the strings and lists it points to, measured 62 megabytes on CPython 3.15. At least a third of the table is always empty on purpose: memory spent to buy speed (Chapter 1).

Lantern's Index

Lantern's inverted index maps each of its about 1.5 million terms to that term's postings list, the sorted ids of the records that contain it. Looking up the term dispossessed is one hash, one probe and one comparison, and it returns a short list with record 1048576, The Dispossessed, among the ids. Scanning the 2 million records instead would read every one of them (Chapter 1). On disk the same map is kept in term order, as the B-tree of Chapter 6.

A three-term query is three lookups plus the work of combining three postings lists, however large the catalogue grows. That is how one server answers 300 searches a second at the Saturday-morning peak. Doubling the catalogue would roughly double the scan and leave each lookup where it is.

Order, Memory and the Occasional Rebuild

A hash table has no notion of order. The query year greater than 1970 cannot be answered by hashing years, a prefix such as le cannot be found by hashing it (Chapter 6), and "the next term after this one" does not exist in a hash table. Its O(1) is also an average that assumes an even spread, and an attacker who makes every key collide turns each operation into O(n), which is the next topic.

The everyday bill is memory: the table itself, its empty third, and two or three 8-byte words per entry, for the key, the value and, unless the key is a string that already carries it, the hash. The key and value objects come on top. Deleting keys does not shrink it. On CPython 3.15, a dictionary that held a million keys still took 42 megabytes after every key was deleted. And one insert in a while pauses for a full rebuild, on whichever request happens to trigger it.