07Hash Tables — Name What Counts as the Same Thing

01The reach you did not make

Here is a nightly job that flags any order it has already seen, written the way almost everyone writes it first.

Walk the export once, and for every order walk the export again looking for an earlier row carrying the same number.

The export holds 700,000 rows. The inner walk only has to reach the current row, since it is looking for an earlier match. So it reads half the rows read so far on average, 350,000 each time. That is 700,000 multiplied by 350,000, or 245,000,000,000 element touches, and at 1.5 ns a touch the job runs for 367.5 seconds. Just over six minutes, every night, and nobody has ever filed a bug about it.

Now the version you also know. Keep a set of the order numbers you have seen, ask it about each new order, then put that order in. That is one question and one addition per row, 1,400,000 operations across the whole export. The pair costs about 0.55 microseconds, so 700,000 rows cost 0.385 seconds. The output is identical, row for row. 367.5 seconds against 0.385 seconds is a factor of 955, and that is the number everyone quotes.

It is also the smaller of the two numbers sitting here, which is worth a moment. 245,000,000,000 touches became 1,400,000 operations, so the work fell by a factor of 175,000. The clock moved by 955. The factor of 183 between those two is what one operation costs in the old currency, since 0.275 microseconds is 183 touches of 1.5 ns. That price is real and this page bills you for it much later, once your key is right.

You already own the second version. You have imported it, typed it, and read it in other people's code a thousand times. The loop is still what almost everyone writes, because the loop is what the problem looks like. A duplicate is something you find by looking, so the code goes looking, and six minutes is what looking costs. The enemy on this page is confidence rather than ignorance, and confidence is much harder to interrupt. Both versions ask the same question of every row, in the same order, once each. Nothing about the algorithm changed — only what one probe hands back, which went from a single comparison to the answer itself.

02Two kinds of question, and only two

On page 3 you gave up order to buy the address, you were told the loss was real, and you have never once spent what you bought. The purchase was genuine and the receipt is still in your pocket. What you bought was a structure that answers one narrow kind of question at a price nothing else touches. What you gave up was every question that depends on what sits beside what. That was a cost you agreed to pay inside one algorithm, with the data already in front of you. Here it turns into something else: a ruling you make on somebody else's sentence, before any data exists and before an editor is open.

It has to turn into that, because of the gap between how these tools are stored and how they arrive. They are stored as nouns, and you learned them under names like cache, dedupe set, index. They arrive as verbs, in a colleague's message, in a ticket, in a stakeholder's one-line request. Have we sent this person the welcome email yet does not look like any noun you ever filed. So the noun never fires, you write the loop, and nothing about that loop feels like a mistake while you are writing it. Fig. 1 puts six sentences of exactly that kind in front of you. Sort them into two piles before anything tells you what the piles are.

There are two piles because there are only two questions, and the second one is the one that gets forgotten. An equality question asks whether this exact thing is in there, or what is attached to it, or how many of each there are. A neighbour question asks what is near, next, biggest, between, before. Almost nothing you will be asked to do to a collection falls outside those two, and the exceptions announce themselves. How many are there in total is a group-by with one group. Give them back in the order they arrived is not a question about the data at all. Five of the six sentences settle on a single word. Already, each and one of are equality words. Nearest and between are neighbour words, and once you have seen them you cannot unsee them in a request.

The sixth was built to be got wrong. Suppress the alert if the same alert already fired within ten minutes carries both kinds of word at once. Same is an equality word, within is a neighbour word, and within is much the louder of the two. Most people file that sentence under neighbours and then go and write a scan back through the last ten minutes of alerts, which is a real answer to a real question and costs a great deal. Whichever pile you put it in is pinned now, and you will not get to move it. Notice what did not happen when you chose. Nothing objected. Pushing a neighbour question through a table raises no error at all; it quietly grows a for-loop, and a for-loop passes review.

The sixth sentence is not a neighbour question, and the reason is the most portable thing on this page. A neighbour word inside a sentence does not settle that sentence, because the key is not handed to you by the data. You write the key. And a written key can convert a neighbour word into an equality word, which is how the on-call engineer who took four thousand pages from one alert stops taking them. The conversion is never free, and the fee is always paid in exactness. Round the timestamp to a ten-minute block and "within ten minutes" becomes "same block" — a different question, cheaper to ask, and you have to say which one you are answering.

03The tells, and the three shapes

Read back the words that made you sort those six, because they are the whole instrument. You never once consulted a definition. You heard same, or already, or duplicate, and your hand moved before you could say why it moved. The rest of that pile answers to the same short vocabulary: seen before, unique, dedupe, by X, per X, join on, matches, is it one of. Nobody says the phrase "equality question" at a standup. They say "we keep emailing the same person twice", and that is the tell arriving in its working clothes.

The other pile ran on a different set of words, and you can read those back just as easily. Near, closest, next, between, top, range, prefix, sorted, percentile, within. Ten words. Every one of them asks where a thing sits relative to the others, which is a question no key can answer. So the instrument is about twenty words in total, eleven on one side and ten on the other, and no third list has turned up. The sentence that caught you carried one word from each pile, and that is the ordinary case rather than a cruel one.

Once a sentence lands in the equality pile, the structure question is nearly finished before you have thought about it. The mechanism is page 3's, the randomness is page 4's, and the library was written by somebody else years ago. What is left is a single question: what rides along with the key? There are three answers. Nothing rides along, and you have a set, which only ever reports whether this key has been seen. A value rides along, and you have a map, so one probe hands back the invoice, the embedding, the path. A running total rides along, and you have a counter.

That third shape is the one people reach for constantly without ever noticing they reached. Revenue per region per month. Requests per API key in the last minute. The earliest unpaid invoice per supplier. Everyone calls those a group-by and files them under reporting, and almost nobody files them under hash table, which is what every one of them is. The key is the group, and what rides along is a number you keep updating rather than a value you store once. Total, count, minimum, maximum, a list you append to (the payload varies, the reach does not). Three answers exhaust the question, and that is worth saying plainly, because it means you can be wrong about a key and still never be lost about a shape. Name what rides along with the key and you have named the structure, and there is never a fourth answer to be stuck between.

04The nested loop is a table you have not built yet

Go back to the job at the top of this page and look at what the inner loop is actually for. It is not computing anything and it is not building anything. It walks the orders already read and asks each one the same question: is this the one that matches? It stops early on a yes and runs to the end of the read rows on a no. That is a lookup. The loop does not contain the lookup, it is the lookup, written out by hand as a walk. Every one of the two hundred and forty-five billion comparisons the job makes is one step of one lookup.

So make the edit, and notice how little of the job it touches. The outer pass over the 700,000 rows stays exactly where it is, and so does the flag it writes. Delete the inner loop. In its place put one line that asks a set whether this order has been seen. Under it put one line telling the set it has now. One line out, two lines in, and the job's six minutes become four tenths of a second. The job flags the same orders it flagged before, in the same order, with the same output file.

This generalises, and it is the most mechanical recognition on the page. Whenever an inner loop exists to find the one that matches, that loop is a table you have not built yet. The nested version answers the question by looking, and the table answers it by asking. You do not need to understand the domain to make that edit, or the flag, or what a duplicate order costs finance. Which is why the edit is safe to make almost mechanically, and why it is not the hard part. Look at what the edit left behind. The two new lines both reach into the same expression, and that expression has a hole in it: table[???]. One pass to build and one pass to probe, and the only thing the edit did not fill in is the blank between the brackets.

05Name the key, and say how coarse

Ten thousand rows of a signup export, and one line from a stakeholder: how many customers do we actually have? Everything about the structure is settled before you begin. It is a hash table, it is a set, it is one pass over the file. None of that is the question. Fig. 2 hands all of it over and withholds exactly one thing, an editable blank reading key = ______. Type what almost everyone types first, key = email — but commit a count before you press it. The figure keeps the number hidden until you have said one out loud, and it will pin your guess beside the truth without ever marking it wrong.

The set fills to 8,412 distinct keys. That means 1,588 of the 10,000 rows were byte-identical repeats of something already in there. Then three raw rows stack up on screen, one under the other, where the eye cannot miss them. Ajai@Iolinked.com, ajai@iolinked.com with a trailing space, and ajai@iolinked.com. Three keys, one person. Normalise the thing you can see, and key = lower(trim(email)) reads 7,980. The count fell by 432, because those 432 rows differed from a row already in the set only in letter case and stray whitespace. Not one character of the lookup changed, and no debugger on earth would have caught those 432, because nothing malfunctioned at any point.

The stakeholder writes back: still too high, those two accounts are the same guy. The key field is still open, and a show me the raw rows button is sitting under it, so run it before you read on. What you find is that no column anywhere in this file is called person. A phone column and a card column are all the raw rows offer, so you type key = card_fingerprint and the figure reads 7,151, with a warning strip beside it. 580 of the 7,980 mailbox identities carry no card at all, and they have just vanished from the count. So the key you actually want is not a column at all, but a composite you had better write out: coalesce(card_fingerprint, lower(trim(email))). The 7,400 carded identities share those 7,151 distinct fingerprints, and the 580 uncarded ones keep their mailbox key. 7,151 plus 580 is 7,731.

7,731 is not a better 7,980 — and it is not the right answer either. Of the 249 identities that the fingerprint merged, 186 really are one person holding two mailboxes. The other 63 are two different people sharing one company card, which the figure shows you rather than mentions. Hand-correct those 63 and you get 7,794, a fourth key built out of a human being reading 249 rows by eye. That key answers for this one file and generalises to nothing whatsoever. A key set too fine leaves one thing sitting in the table under two names. A key set too wide collapses two things that were never the same.

Every key you name carries two claims rather than one: which things are the same, and how coarse same is. The second claim fails in both directions, and so far you have only felt it fail one way. Watch it fail the other. key = domain(email) reads 40, because the 7,980 mailboxes span forty company domains. That is a mean of 199.5 mailboxes each, the largest holding 890 and the smallest holding 3. Nothing broke here either, and 40 is the honest and exact count of something real. Notice too that not one of these keys was handed to you by the file. Composite, normalised, derived, digested, bucketed: every one of them was manufactured. From 8,412 down to 40 is a spread of 210 times across four keys that are all correct.

Under all four the cost line printed beneath the figure is identical. Ten thousand rows, one pass, 10,000 probes, against the nested loop's 10,000 × 9,999 / 2 = 49,995,000 comparisons over that same file. The ratio is 4,999.5 times for every one of the four keys, because the structure never moved a millimetre and only the sentence moved. So say which number answers which question, because each of the four answers one. 8,412 answers how many login identities, and 7,980 answers how many mailboxes. 7,731 answers how many payment instruments, and 40 answers how many companies. None of the four answers how many people — which is the only question anybody asked. The table never had an opinion about who is the same person; you did, and the key is the only place your judgement enters the program.

06A bad key is a claim that stops being true

A key is a claim, and a claim can stop being true while the program keeps believing it. Here is the smallest version of that. You add an order object to a seen-set while its status reads pending, and two lines later the shipping worker sets that status to shipped. Nothing was deleted, nothing raised, and the set now denies it has ever seen that order. The key mutated after the insert, and the address moved with it. Fig. 3 draws the mechanism rather than the printout, because four impossible lines on their own buy disbelief and not understanding. Its digest is small enough to add up in your head. That is the point: it will not draw a slot until you have worked out which slot, twice. Compute the address before you look at the picture. The object never moves a pixel, and that is the part you have to see arrive.

It is sitting at the address its old key computed while every lookup goes to the address its new key computes. That is page 3's founding line collecting on you: the key IS the address, so changing the key changes where the thing lives without moving the thing. Length counts occupied slots and still says 1. Iteration walks slots and still prints the order, showing the new status, because it is the same object. Only the lookup computes, and computing is the one operation that disagrees. Insert it again and the table holds two entries pointing at one object. A mutated key lands back on its own slot roughly one time in m, which is 6.25% in a sixteen-slot toy and effectively never in a real table of a million slots. In this particular toy it is zero, since the additive digest displaces every pending-to-shipped key by exactly 749 − 741 = 8 slots. So the intermittency is not slot arithmetic. It is which access path happens to run: iterate and the order is there, look it up and it is gone. That is exactly why this bug reads as a race, collects a retry wrapper, and ships.

The second failure is quieter, because both of its halves look correct on their own. A key answers two questions, and different code asks them. Which slot do I go to, and once I am there, are these two things equal? Define one and inherit the other and you now hold two definitions of same, quarrelling. The usual shape is a custom equality written for a value class, with the hash left as whatever the language gave you. Two objects you have personally declared equal then compute different addresses and never meet in the same slot. Again there is no exception to catch. The probe goes somewhere reasonable, finds nothing there, and reports absence with total confidence. The rule is one sentence, and it is checkable in a code review: every field your equality reads, your hash must read too.

The third failure is the one that just cost you four hundred and thirty-two customers. Case, a trailing space, two unicode spellings of the same accented letter, a composite key assembled as (region, month) here and (month, region) there. Each of those is a second key for a thing you would call one thing. Floats are the sharpest version of it. 0.1 + 0.2 and 0.3 are the same number to you and two different keys to the table, because they are two different bit patterns. So normalisation is not tidying. It is the step where you drag the key back into agreement with the sameness you meant, and it belongs at the moment the key is built, never at the moment you start to doubt it.

The fourth failure has nothing wrong with any individual key. What is wrong is how many of them there can be. A cache keyed on the full request URL is a cache right up until somebody appends a random tracking parameter to every link. After that it is a record of everything that has ever happened, growing without a ceiling, and not one entry is ever read twice. The reliable smell is a key space you do not control. A caller who gets to name their own fields is filling in the blank you were supposed to fill in. An unbounded key space is a memory leak with a lookup bolted to it. Ask how many distinct values your key can take before you store the first one. If you cannot put a number on it, you have not finished choosing the key.

The fifth failure leaves the O(1) completely intact and eats the win inside the constant. Digest a 4 KB request body on every lookup, and at a general-purpose digest rate near 1 GB/s those 4,096 bytes cost about 4,096 nanoseconds. One probe costs 16 nanoseconds warm and 82 nanoseconds cold, which the crossover section prices out from parts. So computing the key for one probe costs between 50 and 256 probes' worth of work, and the structure keeps every promise it made while you pay fifty times over at the very best for the privilege. All five are one failure in different clothes. The key stopped standing for the thing you said it stood for, and no bounds check exists anywhere that could have noticed. Ask two things of every key you name: can it change after you store it, and could two things you would call the same ever compute differently?

07A key has a scope

Now ask a third thing of every key: how far does it travel? Page 4 told you to draw the hash function fresh at every startup, and that is exactly why you must not shard on it. Inside one process that draw costs nothing and protects you. Nothing outside the program ever sees the numbers it produces. The table is built, probed and thrown away between the same two brackets, so the function only has to agree with itself. A key that lives and dies in one process has a scope of one process, and any function will do.

Now write the key down. A shard id picks the machine a row lives on, and it is stored with the row. A partition key is read back by a job that starts tomorrow. A cache filename outlives the process that chose it. A manifest checksum is compared against one another machine computed last month. Each of those keys has to mean the same thing to a program that never met the one that wrote it. Page 4's per-startup draw makes every one of them wrong, quietly, on the next restart. This is why content-addressing and consistent hashing always name their digest out loud — SHA-256, MD5, xxHash — and never say the language's hash.

That gives the word order two meanings, and page 3 and page 4 charged you for them separately. Order-as-sorted is the neighbour question you gave up to buy the address. It was a real loss, named as a loss, and you took it anyway. Order-as-reproducible is different: the same input file, run twice, laying its rows out the same way both times. Iteration order is not an order at all. It is whatever the seed and the insertion history happened to produce, and the seed is new every process.

The symptom is a pipeline that passes on your laptop and fails in CI. Nothing is broken, and there is nothing to debug, because both runs are correct. They just disagree about a sequence neither of them ever promised. The fix is small once you can see it: sort at the boundary where the data leaves the program, or key the output explicitly instead of trusting the order it came out in. Order-as-sorted is a price page 3 made you pay knowingly; order-as-reproducible is one page 4 charged you without saying so.

08The wrong reach, the replacements, and three and a half downgrades

Take a neighbour sentence from that first sort and follow it into the code until a for-loop appears. You wrote the orders into a table keyed by order id, which is a perfectly good table. Then the report asked for everything placed between the fourteenth and the twenty-first. Nothing raised. The dict did not complain, the type checker did not complain, and the tests passed. What happened instead is that a loop appeared underneath the lookup, walking every key and keeping the ones inside the window. That loop is the failure. It is not an exception you can catch. It is four lines of ordinary-looking code that a reviewer reads straight past.

Price it, because the silence is what makes it expensive. 2,000,000 orders sit in the table, and the report matches about 300 of them. The loop scans all 2,000,000 keys for every query it answers. Put the same rows in a sorted row and binary search reaches the fourteenth in 21 probes, then reads those 300 matching rows out in order. That is 321 touches per query against 2,000,000, a factor of 6,231. The table never got slower. It simply never answered this question at all, and the loop answered it instead.

So the move is routing, not rebuilding, and you already own most of the destinations. A between question goes to the sorted row with binary search you built on page 3. A prefix question — the search box suggesting on the third character — goes to the trie you dialled bits into on the same page. A range over more rows than fit in memory goes to the page-aware index, priced in page fetches rather than in comparisons. A top-ten question goes to a heap, and the heap is the only new name on this list. There is a fifth that nobody lists, and it is not a routing move at all. The tokenizer checking 47 reserved words has an n that is small and frozen, so the slot can be settled before the program runs: a perfect hash, or a switch on length and first character, computed once at build time.

The other direction is relaxation, and it is a move you perform rather than a system you adopt. Give up certainty on one side and membership gets cheap: the structure's NO is a proof, its YES is a hint you re-check. You met that shape twice already, in page 4's witness and page 6's certificate, and it is the same bargain wearing a third costume. Give up the values and a digest stands in for the content, so a 4GB working tree becomes 80,000 short keys. Give up the single machine and the key stops choosing a slot and starts choosing a host, which turns a resize into a migration.

The fourth is a half, because you give up exactness of the count itself. Counting distinct users exactly costs one stored id per user, and the dashboard cannot afford to keep them. So hash each id and watch only one thing: how many leading zeros the longest digest had. A digest with 12 leading zeros is about as surprising as 12 heads in a row. So it suggests roughly 2¹² = 4,096 distinct ids went past, held in a few bytes rather than a stored set, with a stated error bar. That is every escape hatch on this page. All of them are still key decisions.

09The constant is maintained, not owned

From here your key is right, and everything left that can go wrong has nothing to do with the key. The page turns here, and it is worth saying so out loud rather than in a clause. You know alpha by name already -- chain length, occupancy, the same n over m you met on page 3 -- and you have never seen its curve. Page 4 handed you α = 1 once, as a single line about five thousand keys in five thousand buckets, and never let it move. Fig. 4 lets it move. Drag the fill from a tenth to ninety-nine hundredths and watch what a single lookup costs at each stop. The line is nearly flat for most of that walk. That flatness is not a property of hashing. It is bought, every time, by a resize policy somebody wrote: page 2's doubling, and its shrink at a quarter. Nobody is maintaining the constant for free.

Before either curve draws, the figure makes you say one number out loud. At ninety per cent full, under linear probing, how many slots does a miss inspect? Most engineers answer two, five, or ten. The formula printed on the figure's face is 0.5 × (1 + 1/(1 − α)²), and at α = 0.9 that evaluates to 50.5 slots. A hit at the same fill costs 5.5 slots, because the hit formula carries 1/(1 − α) and the miss formula carries that same term squared. The reason is plain once you say it aloud. A miss must walk the entire run of occupied slots before it can conclude that nothing is there. Runs grow faster than the fill that makes them. So at α = 0.9 the miss costs 9.2 times the hit, 50.5 against 5.5.

The second panel drew at that same moment, off exactly the same keys, so nothing here is a new experiment — read chaining at that same 0.9. A hit costs 1.45 key comparisons. A miss costs 0.9. The miss is 38 per cent cheaper than the hit, and the two lines never come apart at all. That is not a paradox and it is not a better hash function. A chaining miss walks one bucket of expected length 0.9 and stops. A chaining hit walks, on average, halfway down a chain already known to hold something. Same keys, same fill, same alpha, and a divergence of 9.2x has become 0.62x.

Do not carry 50.5 out of this room as a slogan, which is why the figure keeps its third panel shut until you have committed. Those 50.5 linear-probing slots sit next to each other in memory. At eight bytes a slot they span 404 bytes, which is seven cache lines. One line is cold at about 80 ns and the prefetcher gets the other six at about 4 ns each, so that miss costs roughly 104 ns. Chaining's 0.9 comparisons are 0.9 separate allocations at unrelated addresses, sitting behind one bucket-array fetch, so about 80 plus 72, or roughly 152 ns. Fifty of something adjacent beats one of something scattered. Page 3 told you that you are not billed in comparisons, and this is the invoice.

One caution rides on the figure's own face: these are the idealised uniform-hashing curves for plain linear probing. Real implementations ship Robin Hood displacement, tombstone-aware probing or quadratic steps, and every one of them lands better than 50.5. The direction survives all of them. That direction is the thing to carry, because under open addressing it is the miss side that falls off the cliff first. That is the opposite of how everybody reads a cache dashboard, where the falling hit rate is the number people watch. Which scheme your dictionary uses was settled by whoever implemented your language. You did not choose this and you cannot change it; you can only find out which one you have.

10Price one probe

You priced a page fetch at a hundred thousand memory touches and watched a run of adjacent slots beat the method that won on comparisons. Price a probe the same way and the answer comes back as a threshold you can put in code. A scan walks adjacent bytes. The prefetcher sees it coming, so the machine drags in one 64-byte cache line about every 4 ns. Per element, after that, it pays almost nothing. A probe cannot be seen coming. It is a hash, and then one memory access to an address nothing could have guessed. That fetch costs about 14 ns warm in L2, and about 80 ns cold in main memory. It costs that at 8 entries, and it costs the same at 8 million.

So below some n you can walk the whole array in less time than one unpredictable jump takes to land. Fig. 5 will not race anything until you have said where that n sits. Take a set of 4-byte ints with the table warm. Both sides of that race print their bill on the figure's own face, so the guess is checkable rather than blind. The probe is charged a hash and one unguessable fetch, and it is charged that whatever n is. The scan is charged a comparison and a share of a cache line, once for every element it walks. Say where they cross.

Now the arithmetic under the band you just watched arrive. The probe pays 2 ns to hash plus 14 ns to fetch, which is 16 ns. Each scanned element pays 0.3 ns to compare plus a 0.25 ns share of the line it is walking, which is 0.55 ns. One probe therefore buys 16 / 0.55 = 29 scanned elements. The array is still winning at 20 entries and has lost by 40. Let the same table go cold and the probe costs 2 + 80 = 82 ns, which buys 82 / 0.55 = 149 elements instead. That is why the figure printed a band from 29 to 149 and would not hand you a point. That 16 ns is also the bill rung 1 left open. One set operation there cost 0.275 microseconds, or 183 memory touches, and only 16 of those nanoseconds were the table. The other 259 ns were interpreter dispatch, bounds checks and the boxed-object round trip, which is a language tax rather than a table tax.

Then it unlocks the toggle that is the whole reason the figure exists. Swap the 4-byte int for a 12-byte key like order-1041. Hashing 12 bytes costs about 5 ns, so the warm probe rises to 19 ns. But every scanned element now costs 2 ns to compare plus 0.75 ns of line, which is 2.75 ns. The crossover drops to 19 / 2.75 = 7 warm, and 85 / 2.75 = 31 cold. At 40 bytes (a URL, a pair of UUIDs) the warm crossover is 26 / 4.5 = 6. The direction is the surprise. A bigger key raises both halves of that fraction, and the bottom half wins by a mile. The extra 3 ns of hashing pushes the crossover up on its own. The element going five times dearer, 0.55 ns to 2.75 ns, drags it down far harder. The table starts winning sooner on long keys, which is the opposite of what almost everyone guesses.

Speed is only half the price, and the other half points the other way. A plain array of 4-byte ints spends 4 bytes an entry and nothing else. An open-addressed table held at α = 0.7, with an 8-byte slot, spends 8 / 0.7 = 11.4 bytes an entry, which is 2.9 times the array. A chained one spends 40 bytes an entry: the 8-byte bucket, plus a node holding an 8-byte next pointer, an 8-byte cached hash and the 4-byte key, which a 16-byte-granular allocator rounds up to 32. That is 10 times the array, and 3.5 times the open-addressed table holding the identical set. So Fig. 4's two schemes differ in memory as much as they differ in currency. Neither one can be read alone. Every one of these numbers was set upstream, by the key you named at the click. There is a crossover, it is much smaller than you think, and where it sits is a property of your key rather than of the structure.

11The worked problem, with the wrong first idea left in

A second nightly job, this one flagging duplicate support tickets, takes four hours, and it still misses duplicates. The corpus is 4,000,000 tickets. Each body runs about 900 bytes, or roughly 150 words. The job compares every ticket to every other ticket, so it walks 4,000,000 × 3,999,999 / 2 = 7,999,998,000,000 pairs. A subject compare that usually fails on its first character costs about 1.8 nanoseconds. Multiply those two and the four hours stops being a complaint and becomes a consequence. Nobody asserted it; it falls out of the pair count. Fig. 6 runs the whole thing under a live clock, so you watch the number arrive rather than take it.

Now fill the blank, because you know how. key = (requester_id, digest(normalised body), minute bucket), one pass to build and one pass to probe. Per ticket that is 0.9 microseconds to normalise and digest 900 bytes at a gigabyte a second. Add a cold probe, 82 nanoseconds rounded to 0.1 microseconds, and 1.25 microseconds of row overhead, and one ticket costs 2.25 microseconds. Across 4,000,000 tickets, 2.25 microseconds each is 9.00 seconds, and 14,400 seconds divided by 9.00 seconds is a speedup of 1,600. The minute bucket carries Fig. 1's boundary problem, and carries it one-sidedly as always. It can split a pair filed one second apart. It can never merge a pair filed 61 seconds apart. Then the widget prints the line you should be uneasy about. You made the job 1,600 times faster, you found exactly the duplicates the four hours found, and you missed exactly the ones it missed.

So use fuzzy matching. That reflex feels like a return to the old cost, and it is not remotely that. An edit-distance ratio over two 400-character bodies is a 400 × 400 = 160,000-cell dynamic program, about 40 microseconds for one pair. Those same 7,999,998,000,000 pairs at 40 microseconds each come to 3.2 × 10⁸ seconds, and 3.2 × 10⁸ seconds is 10.14 years. Set that against the four hours you have already refused: 3.2 × 10⁸ over 14,400 is 22,222 times worse. The fix your hand reached for is four orders of magnitude past the cost that started this section. Fig. 6 gives that third clock no stop button. You abandon it, and abandoning it is what prints the 10.14 years.

The resolution panel will not open until you answer one question, and the answer is two. This ticket holds two questions, and only one of them is an equality question. The question are these the same ticket filed twice is equality, and the composite key answers it exactly in 9.00 seconds. The question are these two tickets nearly the same is a neighbour question, and no key exists for it, because near is a neighbour word. So change the question. Cut a 150-word body into overlapping 5-word shingles, which gives 150 − 5 + 1 = 146 of them. Digest each shingle to 64 bits and keep the smallest. The figure cuts its digests to 16 bits, so that one fits on a line. Here is the identity the whole figure is built to show you. Call A and B the two tickets' shingle sets, 146 apiece at full size. On screen they are 8 apiece, because the figure stands the 150-word bodies in as twelve-word tickets you can read whole. Two documents share their minimum with probability |A ∩ B| / |A ∪ B|, their overlap exactly, for an ideal hash. Call that overlap J: set the slider to J = 0.8 and the two minima agree 80% of the time. The width dial refuses 1: on single words these two score J = 0.8333, and so would almost any pair. It refuses anything above 12, because a twelve-word ticket yields no shingles at all up there.

One minimum is a coin, so keep 128 of them. At an overlap of 0.8 you expect 128 × 0.8 = 102.4 agreements, with a standard deviation of 4.53. At an overlap of 0.3 you expect 38.4 agreements, with a standard deviation of 5.18. That gap of 64 agreements is 12.4 standard deviations wide, which is not a close call. Split the 128 minima into b bands of r, and key a table on each band. A pair surfaces when any band matches, with probability 1 − (1 − J^r)^b. The textbook default of b = 32, r = 4 surfaces 0.003195 of pairs at overlap 0.1. Over 7,999,998,000,000 pairs that is 2.6 × 10¹⁰ re-checks, so the default must never ship on 4,000,000 tickets. Take b = 16, r = 8 instead. At overlap 0.1 it surfaces 1.6 × 10⁻⁷ of pairs, so at most 1,280,000 exact re-checks survive out of 7,999,998,000,000 candidates. That is a filter factor of 6.25 × 10⁶. Those survivors still cost 40 microseconds each, so the near-duplicate pass takes 51.20 seconds. That is nearly six times the exact job's 9.00, and four orders of magnitude under the ten years. The price prints beside that win rather than under it. At a true overlap of 0.8 the scheme catches 94.7% of pairs, so 5.3% of genuinely similar pairs are missed. You did not change the structure — you changed what "same" means, and that is still an act of naming the key.

12Twenty-five reps of one motion

Twenty-five sentences, no labels, no jargon, and two things to produce for each of them before anything is revealed. A situation arrives one line at a time, written the way somebody would actually say it at a standup. You commit a key, chosen from six options drawn for that situation, and a shape, chosen from five buttons — set, map and counter, plus two verdicts that are not shapes at all. Both commits lock together, and neither can be changed afterwards. The reveal will not fire until it has both of them. A drill that lets you read the answer first is a page of prose with buttons on it. Then it opens: the verdict, the tell highlighted inside the sentence you just read, and the cost in one line. A wrong-tool verdict also names what you should have reached for instead. A bar along the bottom shows how many are left, and never how many you got right. Try to skip one and it says the only thing it ever says. The drill works by having you wrong first, so commit anything.

Those six key options are not padding. Every one of them is a key a working engineer might really name for that situation, and not one is filler. That is exactly why a reader running on reflex picks a listed option and is wrong. The other failure — scanning a short list, finding nothing plausible, moving on — produces a shrug rather than a correction. Guessing the key right is one in six (16.7%), and guessing the shape right is one in five (20.0%). Guessing both is one in thirty, or 3.3%. Across twenty-five reps that floor hands a pure guesser 0.83 fully correct situations. Three correct means you are doing something, and twenty means you are carrying the instrument. The drill prints neither number, because a running score turns a rep into a grade, and a reader protecting a total stops naming keys honestly. Beside the six options sits a box reading or type your own key. It is never graded, and at reveal it is shown next to the answer, so a reader who was right in different words can see that they were right.

The distribution is deliberately not twenty-five yeses. Eleven of the twenty-five resolve to a plain set, map or counter. Five name a replacement tool out loud, the same routes you walked a moment ago now arriving without their labels. Four say no table answers the question. The fifth keeps its counter and puts a heap on top, because the count is right and only the ranking is beyond a key. One is a conversion, where no key exists until you manufacture one and near becomes same cell. Four are traps in which the table is the cause rather than the cure. Four are downgrades, and those five counts are the whole twenty-five. Cutting across them, three arrive as symptoms with the cause hidden. So the mutable key, the resize pause and the price of one probe get practised instead of merely watched.

Twelve domains carry the set, four more than the eight anyone would have guessed. Databases, web backends, observability and security take the largest shares. Version control takes two. ML serving, logistics, compilers, games, finance, data engineering and distributed systems take one apiece. You did this once slowly at the worked problem, with the wrong first idea left in. Now you have done it twenty-five times fast, at about thirty-five seconds a rep. The whole drill runs a quarter of an hour, and somewhere around rep eight the domains stop registering. Two situations arrive from domains that share nothing at all, and turn out to be one sentence in two sets of clothes. Once you have heard that, the costume stops being information. Written out as prose instead, these twenty-five would have been the catalogue this course exists to beat. Nobody has ever learned to reach for something by reading a list of places other people reached. Twenty-five costumes, one shape, and you were only ever asked to name a key and pick a payload.

13What you are carrying out of the room

You can now hear a sentence and answer it with a key, a shape and a cost before opening an editor. Three of them, quickly. We keep emailing the same person twice gives you a normalised email, a set, and one pass over the list. The invoice page fetches a supplier row for every line gives you supplier_id, a map, and one pass to build it. Finance wants it per region per month gives you the pair as the key and a counter as the shape. Then there is the harder sentence, and saying it is what separates an engineer from a catalogue. That one is about neighbours rather than sameness. Here is what I would reach for instead, and here is the word in your own request that told me.

The first of four things you are carrying out of this room is that the reach is one act. Not a structure you select from a shelf, not a name you recall. You name the key. The second is that the key carries a coarseness as well as an identity. Your judgement enters the program there and nowhere else, at a fineness nobody else in the codebase ever states. So every hash-table bug you will ever ship is a disagreement between the key you chose and the same you meant. The count is not wrong. It answered the key.

The third is that a key has a scope. The draw at startup is free inside one process, and a bug the moment the key gets written down anywhere. A shard id, a cache filename, a manifest checksum: each of those has to name its digest out loud. The fourth is that the flat constant is a policy somebody maintains, not a property the structure owns. It fails on a curve that is flat until it is not, and which curve you get was decided by your language rather than by you. Under open addressing the miss side goes first, which is the opposite of the way everyone reads a cache dashboard.

And the fraction gains its entry. What the answer requires, over what one probe returns — this tool works on the bottom half. That is also how the page's two halves fit together: the key sets the question, and the machine sets what one probe costs to ask it. Twenty-five situations turned out to be twenty-five costumes on one shape. This lever moves the denominator further than anything else in the course — one probe stops returning a comparison and starts returning the answer. That is exactly why it can only ever answer "is this the same one".