THE ROBIN HOOD HASHING — a dart

THE ROBIN HOOD HASHING steal from the rich, give to the poor

An open-addressing twist that equalizes probe lengths: on insert, if the key you are placing has probed farther than the key already in a slot, evict the richer (shorter-probe) key and carry it onward. This robs from entries close to home to help entries far from it, shrinking the variance of probe distances — and the worst-case lookup. The map is identical to plain probing; only the layout is fairer.

THE TECHNIQUE on collision, the poorer (farther) key wins the slot

The demo shows Robin Hood’s max probe distance below linear probing’s on the same keys; the probe-distance metric itself is computed: live demo

HISTORY & CREDIT Celis, Larson & Munro · 1985

“Robin Hood lowers the average probe length.” — the mean is unchanged (same keys, same slots); it lowers the variance and thus the worst case. cited

the rule · the entry that has traveled farther keeps the slot; the richer one moves on.
the variance · mean probe length fixed, spread shrunk — tight worst case.
1985 · Pedro Celis, Per-Åke Larson & J. Ian Munro — “Robin Hood hashing.”

Fairness lowers the worst case, not the mean. data structure

RECOMMEND FOR I-13 probe distance, on the compiler

On i-13, the probe-distance metric is computed (a slot 0 with home 5, m=7, is distance 2); the RH-vs-linear max-distance comparison is illustrative of the property, not a full insertion simulation:

$ i13 run hs_robinhood.i13 RUN OK · 26 step(s) · peak stack 4 lin_maxdist = 3 -- illustrative rh_maxdist = 2 -- illustrative rh_lower_variance = 1 d_example = 2 -- dist(slot 0, home 5, m 7) computed

Recommend as a NULL — resource/variance (B40) + a pinned map (B39). Robin Hood re-orders where equal-valued entries sit to cut probe-length variance; the stored key→value map is unchanged, and the reordering is a coordinate-dependent tie-break (B44). A worst-case-cost property, not a keeper. NULL.