Robin Hood Hashing and the Distribution of Probe Lengths

Linear probing’s average probe count is acceptable at moderate load and its worst case is not. The tail is what hurts: a single insertion that lands in the middle of a long run walks the whole run, and as the table fills, the longest run grows much faster than the average. Robin Hood hashing attacks the tail directly by changing which key wins a contested slot, without changing the probe sequence at all.

Displacement as the quantity to equalize

Every key has a home slot, the index its hash selects. Its displacement is the number of slots between its home and where it currently sits, counted cyclically. In linear probing, displacement is also the number of probes a lookup for that key performs, so the displacement distribution is the probe-length distribution.

Plain linear probing lets displacement vary enormously. A key inserted early into a region claims a slot near its home; a key arriving later is pushed to the end of the run. Nothing prevents a key from sitting twenty slots from home while another sits at home, and the run’s shape is determined by arrival order rather than by any structural property.

Robin Hood insertion adds one rule. When a new key’s displacement exceeds the displacement of the key currently occupying the slot, the two swap: the richer key (longer displacement) takes the slot, and the poorer one continues probing, now with its own displacement incremented. In effect, the insertion “steals” from a key that is closer to home and gives the slot to the key that needs it more.

The consequence is that displacement is equalized greedily across the table. A key cannot sit far from home while a better-placed key occupies a slot it needs, because the insertion rule hands the slot to the needier key. The distribution of probe lengths tightens around the mean, and the mean stays close to the linear-probing average rather than falling.

Why the spread collapses while the mean stays put

The result that gives the scheme its reputation is that the whole distribution of displacement collapses. In plain linear probing, the unsuccessful-search cost is the length of the cluster a probe lands in, and cluster lengths are heavy-tailed: the mean is bounded but there is no useful bound on any single operation. Equalizing displacement replaces cluster length with the maximum displacement in the table, which grows far more slowly than the worst cluster, and it makes the spread of probe counts around the mean narrow. The maximum displacement still grows with the number of keys, but the tail is short enough that a bound on it is meaningful.

That matters because the average was never the problem. A linear-probed table at α = 0.9 has an expected miss cost of about 50 probes under uniform hashing, and the spread around that average is wide: some misses terminate in two probes and some in far more. A latency-sensitive caller cares about the tail. Reducing the spread while keeping the mean roughly constant converts an unpredictable operation into a predictable one.

The cost of the rule is paid on insertion. A Robin Hood insert may swap several times, and each swap moves a full key-value pair, so an insertion writes more memory than the same insertion into a plain linear-probed table. The swap count is bounded by the probe sequence length, and the equalized distribution keeps that length in the same range as before, so the extra work is a constant factor on the update path rather than a change in the asymptotics.

Early termination on lookup

The displacement ordering gives lookups a termination test that plain linear probing lacks. While probing forward, the searcher tracks its own displacement d, the number of slots advanced from the key’s home. If it encounters an occupied slot whose stored displacement is less than d, the sought key cannot be further along, because any key beyond that point has displacement at least d and the key being sought would have displaced the poorer key on insertion.

This turns many unsuccessful lookups into short ones. In a miss, the search stops at the first slot that is better placed than the query would be, which on average happens well before the end of the run. It also means a lookup never has to scan an entire cluster just because the cluster is long: the cluster’s tail consists of keys with high displacement, and the searcher’s displacement only exceeds theirs after a comparable number of steps.

/* Returns the slot holding key, or SIZE_MAX. dist[] holds each key's displacement. */
size_t find(struct table *t, uint64_t h, const char *key)
{
    size_t m = t->mask + 1;
    size_t i = h & t->mask;
    uint32_t d = 0;

    for (;;) {
        if (t->slot[i].state == EMPTY)
            return SIZE_MAX;                     /* absence proven */
        if (t->dist[i] < d)
            return SIZE_MAX;                     /* key would have stolen this slot */
        if (t->slot[i].hash == h && key_eq(&t->slot[i], key))
            return i;
        i = (i + 1) & t->mask;
        d++;
    }
}

The stored displacement can be a small integer, since it is bounded in practice, and it costs a byte or two per slot; some implementations store it implicitly by deriving it from the slot index and the home index, which saves the array at the cost of a subtraction per probe. Grouping slots so that a whole group is examined at once, as SwissTable control bytes do, flattens the tail by a different mechanism.

Deletion, backward shift, and the ordering invariant

Tombstones work in a Robin Hood table but they destroy the early-termination property, because a deleted slot has no meaningful displacement and the search cannot decide whether to stop. The invariant that makes the scheme useful is an ordering property over the whole cluster, and a hole in the middle breaks it.

Backward-shift deletion, described in linear probing, preserves the property. Removing a key and pulling the following entries back one slot each keeps every entry’s displacement consistent with its position, and the cluster remains ordered by displacement. The scan stops at the first empty slot, exactly as before. The difference is that a shifted entry’s displacement decreases by one when it moves back, and the stored counter must be decremented along with it.

The invariant to maintain is worth stating exactly: within any run of occupied slots, displacements are non-decreasing from the run’s start to its end. That is a direct consequence of the insertion rule, which only lets a key displace a neighbour with a strictly lower displacement. An insertion that swaps maintains it because it only moves a higher-displacement key earlier. A deletion with backward shift maintains it because each moved key keeps its relative order. A deletion with a tombstone does not, which is why implementations that choose tombstones must forgo early termination and fall back to scanning to the first empty slot.

Where the scheme loses

Robin Hood hashing does not improve the asymptotic load-factor limit. The table still degrades as α approaches 1, and the probe count still grows without bound; the equalization changes the shape of the distribution, not its mean. A table at α = 0.95 is still a bad table.

Insertion becomes more expensive in the common case and cheaper in the worst case, which is a good trade for read-heavy workloads and a bad one for write-heavy workloads where every insertion is a new key. A bulk load of a million keys into an empty table pays the swap cost on nearly every insert, and the ordering provides no benefit until lookups begin.

The swap also touches more memory. Each swap writes a key-value pair and its displacement, so an insertion that displaces twenty entries writes twenty slots. In a linear-probed table the same insertion would write one. When the table is larger than cache, that difference shows up as extra memory traffic, and it is why the scheme is often combined with a bucketized layout or a fingerprint byte rather than used in its pure form.

Finally, the scheme assumes linear probing. The displacement ordering is meaningful only when the probe sequence is a contiguous walk, because otherwise “distance from home” does not correspond to the number of slots that must be crossed. Applying the idea to double hashing would require a per-key notion of progress that the stride does not provide.

Robin Hood hashing is best understood as a refinement of linear probing rather than a replacement for it: same array, same probe rule, one extra comparison on insert and one extra byte per slot. The refinement buys a bounded tail, and the bounded tail is what makes a hash table usable under a latency requirement rather than only under an average-case argument.