Hash functions and hash tables

The formula

The simplest workhorse hash, the division method:

h(k) = k mod m

Reading: take the key (or an integer made from it), divide by the table size m, keep the remainder. Every key lands in one of m slots. Pick m prime and keys with common patterns spread out instead of piling up.

The single number that governs a hash table's behavior, the load factor:

α = n / m        (n keys stored in m slots)

Reading: how full the table is. Every performance formula for hash tables is a function of α, not of n. That is the entire reason lookup stays constant-time as the table grows — you grow m with n and α stays put.

For string or structured keys, the multiplication method scales without a prime table size:

h(k) = floor( m · frac(k·A) ),   A = (√5 − 1)/2 ≈ 0.6180339887

Reading: multiply the key by an irrational constant, keep the fractional part, scale to the table. Knuth's golden-ratio choice of A scatters even sequential keys, and m can be a power of two.

Expected probes to find a key, with chaining (each slot holds a short list):

successful search  ≈ 1 + α/2        unsuccessful ≈ 1 + α

Reading: at α = 1 — as many keys as slots — a lookup touches about one and a half entries on average. Cheap.

Expected probes with linear probing (collisions step to the next open slot), Knuth's result:

successful  ≈ ½·(1 + 1/(1−α))        unsuccessful ≈ ½·(1 + 1/(1−α)²)

Reading: fine until the table gets crowded, then a cliff. At α = 0.5 an insert averages 2.5 probes; at α = 0.9 it averages 50.5. The 1/(1−α)² term is why every serious implementation resizes around 70–90 percent full.

Collision probability for n items hashed into N possible values — the birthday bound:

P(collision) ≈ 1 − exp( −n·(n−1) / (2·N) )        n₅₀ ≈ 1.1774·√N

Reading: expect a duplicate hash once you've drawn roughly the square root of the space, not the space itself. A 32-bit hash has 4.3 billion values, but you hit 50/50 odds of one collision at 77,163 items, 1 percent at about 9,300, and 100,000 items collide with 69 percent probability. Sixteen digits of headroom is really eight.

Where you meet it

The telemetry ground station. Every decoded frame maps parameter names to slots in a current-value table — "CHAMBER_PT_04" to a memory address, thousands of times per second. That map is a hash table, and it is why the display software doesn't care whether the vehicle database defines four hundred measurands or forty thousand.
The data package for a review board. Delivered firmware images and test data files carry a SHA-256 alongside them; the receiving side recomputes it and compares. Match means bit-for-bit identical — with a 256-bit space, the birthday bound puts an accidental match past 2¹²⁸ files, which is never. That one line in the delivery record is a hash function doing configuration management.
Flight and embedded software. Command dispatch by message ID is often a hash table sized at build time, because the alternative — a linear scan of the command list — has latency that grows with every new command added late in the program. The flight-software version is statically sized, never resizes, and someone had to defend the worst-case probe count at the design review.
Post-test log crunching at the bench. Counting unique fault codes across a night of soak-test logs is one dictionary and one loop in Python. The dictionary is a hash table; the reason the script finishes in seconds instead of hours on a million-line log is O(1) versus O(n) per lookup.

How it works

The idea is a filing scheme. Instead of keeping keys sorted and binary-searching (~log₂ n steps) or scanning (~n/2 steps), you compute where the key should live and go straight there. The hash function is the address computation; the table is the shelf. All the engineering is in what happens when two keys compute the same address — and the birthday bound above says they will, far sooner than intuition suggests. Collisions are not a defect to eliminate. They are a load to be carried, and you size for them the way you size a relief valve.

Two standard ways to carry that load. Chaining hangs a short list off each slot; performance degrades gently and linearly with α. Open addressing (linear probing and its cousins) stores everything in the array itself and walks to the next free slot on collision; it is compact and cache-friendly, and it falls off a cliff past α ≈ 0.8 because occupied runs cluster and feed on themselves — the 1/(1−α)² term is that clustering, priced. When the table gets too full, the implementation allocates a bigger array and rehashes everything. Averaged over many inserts that cost is constant; on the one insert that triggers it, it is a full pause proportional to n.

The mistakes that actually bite:

"Average O(1)" is not "always O(1)." The resize pause and the worst-case probe chain are real. A control loop or interrupt handler that inserts into a growable hash table has unbounded jitter hiding in it. Real-time code preallocates the table, caps α, and bounds the probe count — or uses a different structure entirely.
Adversarial keys break the average case. The probe-count formulas assume keys spread evenly. In 2003 Crosby and Wallach showed that an attacker who knows the hash function can craft thousands of keys that all land in one slot, turning a server's hash table into a linear list and its CPU into the victim — a denial of service at dial-up bandwidth ^[7]. Anything hashing untrusted input (message fields, filenames, packet contents) needs a keyed or randomized hash. Most language runtimes fixed this after 2011; homegrown embedded code usually hasn't.
Wrong hash for the job. A CRC catches wire noise; it is trivially forgeable and says nothing about intent. A fast table hash spreads keys; it is not evidence of integrity. Only a cryptographic hash (SHA-256 per NIST FIPS 180-4 ^[8]) supports "nobody altered this file" — and the older ones (MD5, SHA-1) no longer do, because collisions for them can be manufactured. Match the strength to the claim being made in the review package.
Hash and equality must agree. Equal keys must produce equal hashes, always. Hashing floating-point keys, or structs with uninitialized padding bytes, violates this silently: the key is "in" the table and lookup still misses. Use exact keys — integers, strings, quantized values.
Truncating a good hash is fine; trusting the truncation isn't. Keeping 8 hex characters of a SHA-256 as a short ID gives 32 bits — and the birthday math above applies to the 32 bits you kept, not the 256 you threw away. At 77,000 items, expect a duplicate short ID.
Iteration order is not a contract. Walking a hash table visits entries in hash order, which changes with table size, insertion history, and (in randomized runtimes) the process itself. A test report generator that iterates a dictionary can produce differently-ordered output on identical data — poison for diff-based regression checks. Sort before you write anything a human or a script will compare.

Sanity check worth keeping: before trusting any deduplication or ID scheme, compute n²/(2·N) for your expected item count. If it isn't a small number, collisions are in your design whether you planned for them or not.

History

Hashing was born at IBM twice in two years. In January 1953, Hans Peter Luhn — the same Luhn whose checksum digit still sits at the end of every credit card number — wrote an internal memo proposing that records be filed into numbered "buckets" computed from the key, with collisions chained together in the bucket, to make searching fast ^[1]^[3]. Around 1954, a separate IBM group — Gene Amdahl, Elaine McGraw, Nathaniel Rochester, and Arthur Samuel — needed a fast symbol table for the IBM 701 assembler and worked out the other half of the field: store everything in one array, and when a slot is taken, step forward to the next open one. Linear probing, in production, before it had a name ^[1]^[2]. Andrey Ershov reinvented it independently in the Soviet Union and published in 1958; W. Wesley Peterson gave the first open-literature treatment in 1957 and remarked the scheme was so natural others had likely found it too ^[2].

The word itself came later. Programmers said "hash" informally for years before Robert Morris put it in print in his 1968 Communications of the ACM survey, "Scatter Storage Techniques," which made hashing respectable ^[1]^[6]. The analysis came from Donald Knuth, who worked out the exact expected probe counts for linear probing in 1963 — the ½(1 + 1/(1−α)²) above — in notes he circulated but didn't formally publish; Konheim and Weiss published equivalent results in 1966, and Sedgewick later called Knuth's derivation a landmark in the analysis of algorithms ^[2]. The collision side of the story is older than computing: the birthday problem was posed by Harold Davenport around 1927, who declined credit because he couldn't believe it was new, and first published by Richard von Mises in 1939 ^[4]^[5]. Von Mises was asking about people in a room. The answer — duplicates arrive at √N, not N — now sizes every hash space in every system you'll ever test.

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →

The formula

Where you meet it

How it works

History

Sources

Reading is free. The shelf is for cardholders.