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

Phase transition — where it appears

A sharp change in a random structure's behaviour at a critical value of a parameter, with little change on either side of it. A cuckoo table's construction goes from almost never failing to almost always failing across a narrow band of load, because a random graph's shape changes there.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

0%25%50%75%100%0.20.30.40.450.50.550.60.70.8keys per slotconstructions that failedconstructions that faileddisplacements, scaled to 36840 constructions per point, 256 slots per tablea lookup is two probes, whatever the keys are

An insertion that can fail

Every randomised structure in this field buys an expected cost and accepts a tail. Cuckoo hashing buys a worst case — a lookup examines exactly two slots, for any keys, always — and pays for it in the construction, which can fail outright. On a table of four thousand slots the construction never fails below 0.45 keys per slot and fails nineteen times in twenty above 0.55.

randomness · Randomness 0%25%50%75%100%0.30.40.50.60.70.80.850.90.95keys per slotconstructions that failed2 hashes, 1 slot3 hashes, 1 slot2 hashes, 2 slots2 hashes, 4 slots20 constructions a point, 256 bucketsa lookup reads hashes × slots, whatever the keys

More hashes or wider buckets

A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.

randomness · Randomness

Named alongside it

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

Cuckoo hashingHash tableLoad factorTrade offWorst case guaranteeBucket loadConstructionDisplacementFailure modeFailure probabilityFinite size effectHash function

All concepts