Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Hash collision — where it appears

Two distinct keys given the same hash value, which costs an exact check wherever a hash is used as a cheap filter in front of one. Its rate is a property of the hash family rather than of the keys, provided the family was drawn from at random and not chosen once.

Named by 4 essays across 4 fields — each of them below, with the objects they name alongside it.

hash rowh1h2h3h4h1 → cell 30: 10,433h2 → cell 29: 10,624h3 → cell 19: 10,575h4 → cell 4: 10,895key 0 occurred 9,579 times · the minimum of the four is 10,433 · over by 854the additive bound at this width is e/w × N = 5,0974×32 counters · 4,096 bits · Zipf s = 1.1exact would take 162,288 bits

A count that is never under

The Count-Min sketch holds four rows of counters and answers how often a key occurred. Its error is one-sided with no probability attached — the estimate is never below the truth on any stream — and the probabilistic half of its guarantee is only about how far above.

streaming · Sketch 1,00010,000110100modulus qverifications in one searchq = 257: 693measuredn / qchosen text: 6%one unit = one character comparison · base 2568 colliding blocks at q = 1,009, none at q = 1,000,003

A match decided by a number

Rabin–Karp replaces a comparison of two strings with a comparison of two integers, and pays for it only when the integers agree by accident. On 65,521 windows at a modulus of 1,009 it verified 79 times against a predicted 64.9. On a text of 1,024 characters chosen with the modulus in hand it verified at 64 windows out of 64 possible, each one costing fifteen of the pattern's sixteen characters — and the closed form is silent about that, because it assumes nobody chose the text.

randomness · Symbol column height = keys in that bucket · line = threshold of 8a well-spread hashlongest 44 → 4worst lookupthe low bits onlylongest 3131 → 5worst lookupevery key collideslongest 192192 → 8worst lookup192 keys, 256 buckets, seed 20260811threshold 8, 64 buckets shown

A bucket that becomes a tree

Java's HashMap converts a chained bucket into a red-black tree once it holds eight entries. The comment in the source computes the probability of that happening under a decent hash at about six in a hundred million, so the mechanism is written never to run. Under a hash that fails, the worst lookup falls from 192 comparisons to 8 — and the whole value of the tree is in a case its author does not control.

structures · Structure 1001000entries in the cacheshare of the repeats it catches0%25%50%75%100%256 entries, one a pair asked in a passSelection sortBubble sortdashed: collisions alonerule at 100%: the table ofevery pair256 random elements · direct-mapped, one pair a slotoccupancy, not distance

The record that forgets on purpose

A table of every pair selection sort might ask is 131,072 bits at 256 elements and catches every repeated question. A direct-mapped cache of 1,024 pairs is 16,384 bits and catches 91% of them, at a break-even of 3.53 word operations a comparison against the table's 3.12. What decides the cache is not how long the sort waits before asking again — 98% of its repeats come within one pass — but how many other questions it asks meanwhile, and a model with nothing in it but collisions predicts every measured share to within 2.6%.

counting · Count

Named alongside it

The objects these essays reach for when they reach for this one.

ThresholdAdditive errorAdversarial inputCacheChained hashingClosed formComparison countCost modelCount-Min sketchCrossoverDeterministic algorithmDistribution

All concepts