Hashing

Abstract

Hashing is the trick of turning a key into an address: run the key through a scrambling function, use the result as an index, and reach the data in one step instead of searching for it. It was invented inside IBM in the early 1950s, before it had a name, to make an assembler’s symbol table fast, and it now sits under nearly every database index, language dictionary, cache, and content-addressed store. This article follows the idea from a 1953 IBM memo through the analysis that made it respectable, to the Bloom filter that answers set membership in a few bits, the consistent hashing that lets a thousand servers share a load, and the day attackers turned hash tables into a denial-of-service weapon.

An Address Instead of a Search

The problem hashing solves is old: given a key, find its record. A sorted array lets you binary-search in log n steps; a tree does similar. Hashing aims for one step. A hash function maps each key to a number in a fixed range, and that number is the slot where the record lives. Insert and lookup become “compute the function, go to the slot”, constant time on average no matter how large the table. The complication is collisions: different keys can hash to the same slot, because you are cramming an unbounded set of possible keys into a finite array. Every hash table is really two decisions, the function that spreads keys out and the scheme that resolves the inevitable clashes.

The idea appeared, unnamed, inside IBM. In January 1953 Hans Peter Luhn wrote an internal memorandum describing hashing with chaining: each slot holds a linked list, and colliding keys join the list. At almost the same time Gene Amdahl, Elaine McGraw, Nathaniel Rochester, and Arthur Samuel, building the assembler for the IBM 701, used the other main scheme, open addressing with linear probing: on a collision, walk forward to the next empty slot. (Andrey Ershov hit on the same method independently in the Soviet Union.) The word itself came late. W. Wesley Peterson coined “open addressing” in 1957; Arnold Dumey published the idea of taking the remainder modulo a prime as a hash function; and “hashing” as the name for the whole technique was first put in print by Robert Morris in a 1968 Communications of the ACM survey. The technique was a decade old before it had the label everyone now uses.

Making It Respectable

Practitioners loved hashing; theorists distrusted it, because its good behavior is an average over “typical” inputs and an adversary or an unlucky data set can pile every key into one slot, collapsing constant-time lookups into a linear scan. Two lines of work addressed this. First, analysis: Donald Knuth worked out the precise expected cost of linear probing in 1963, a calculation he later said gave him the confidence that he could write The Art of Computer Programming at all, because it showed algorithms could be analyzed as rigorously as they could be run. Second, universal hashing: in 1977 Larry Carter and Mark Wegman proposed choosing the hash function at random, from a carefully designed family, each time the program runs. No fixed input can then be adversarial against a function it cannot predict, and the good average-case bounds become provable guarantees. Universal hashing turned hashing from a heuristic into a technique with theorems.

A Filter Made of Bits

In 1970 Burton Howard Bloom published a structure that answers a narrower question, set membership, using astonishingly little space. A Bloom filter is an array of bits plus several hash functions. To add an element, hash it several ways and set those bits; to test membership, hash it and check whether all those bits are set. The structure has a deliberate asymmetry: it can produce false positives (the bits happen to be set by other elements) but never false negatives (if the element was added, its bits are certainly set). Bloom’s own motivating case was a hyphenation program: 90% of English words hyphenate by simple rules, and a filter using only 18% of the space of an exact table could eliminate 87% of the expensive dictionary lookups for the remaining words. The structure was dormant for decades, then became ubiquitous once systems got large enough to care about the bits. Google’s Bigtable, Apache Cassandra, HBase, and PostgreSQL use Bloom filters to skip disk reads for rows that are absent; Google Chrome once used one to check URLs against a malware list; CDNs use them to detect “one-hit wonders” not worth caching.

Spreading Load Across Machines

Ordinary hashing has a flaw once the table is a fleet of servers rather than an array. If keys are assigned to n servers by taking the hash modulo n, then adding or removing a single server changes n, which changes almost every key’s assignment and forces the whole cache to reshuffle. In 1997 David Karger and colleagues at MIT solved this with consistent hashing, presented at STOC in a paper on relieving hot spots on the web. Servers and keys are both hashed onto the same circle, and each key belongs to the next server clockwise; adding or removing a server moves only about a 1/n fraction of keys. One of the co-authors, Daniel Lewin, co-founded Akamai in 1998 and built the idea into its content-delivery network, where it handled the “flash crowd” problem that took popular sites down. Consistent hashing later became a standard partitioning method in distributed data stores, including Amazon’s Dynamo (2007), Cassandra, and distributed memcached.

When Hashing Became a Weapon

The adversary the theorists worried about arrived in public in late 2011. At the 28th Chaos Communication Congress, researchers showed that many web frameworks parsed request parameters into a hash table using a fixed, publicly known hash function. An attacker could therefore precompute thousands of keys that all collide into one slot, turning the table’s constant-time inserts into a quadratic crawl and hanging the server with a single crafted request. The attack, hash flooding or HashDoS, hit PHP, Python, Ruby, Java, and others at once. The fix was exactly Carter and Wegman’s insight, keyed randomization, made practical: in 2012 Jean-Philippe Aumasson and Daniel J. Bernstein designed SipHash, a fast keyed hash secure enough that an attacker without the secret key cannot engineer collisions. It was adopted as the default hash-table function in Python, Ruby, Rust, Perl, Swift, and elsewhere. A structure invented in 1953 to make an assembler faster had, six decades later, to be hardened against attackers who understood it better than the programmers using it.