Concept

Displacement — where it appears

How far an item sits from where it belongs — a key from the slot its hash names, or an element from its place in sorted order. Totals and maxima of it measure how disordered a table or a sequence is, and neither says how many memory blocks that disorder spans.

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

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

The probe nobody waits for

Robin Hood hashing makes an inserting key steal a slot from a key that has probed less far. The mean number of probes afterwards is 4.817, and before it was 4.817 — identical, and it cannot be otherwise, because the total displacement is fixed by the hash. What changes is the worst case, from 114 slots from home to 19, and a table reported by its average lookup cost shows no difference at all.

structures · Structure

The permutation that moves almost nothing

Two ways to scramble sixteen thousand elements. Shuffling them inside windows of five hundred and twelve puts two million pairs out of order and costs 3,095 block transfers to carry out. Swapping a thousand pairs across the whole array puts seven million out of order and costs 1,189. Inversions are the textbook measure of disorder, and on a disk they rank these two backwards.

applied · Transfer

Named alongside it

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

Hash table Load factor Trade off Access pattern Block transfer Bucket load Cache Crossover Cuckoo hashing Distribution External-memory model Failure mode

All concepts