Robin Hood Hashing: Let the Farthest Key Sit First

Robin Hood hashing is an open-addressing technique built around a simple fairness rule: when two entries meet during insertion, the entry that has traveled farther from its ideal bucket gets priority. The entry with the shorter journey is displaced and continues searching for another slot.

This is the source of the name. Instead of allowing a few unlucky keys to become extremely far from their preferred locations while other keys remain close to theirs, Robin Hood hashing attempts to distribute displacement more evenly. In practical terms, it tries to make probe distances more predictable.

That goal matters because an open-addressed hash table stores entries directly in one array. A lookup may need to inspect several positions before it finds the requested key or determines that the key is absent. The more uneven the probe distances are, the more variable lookup costs can become. Robin Hood hashing uses probe distance during insertion and, when its invariants are preserved, during lookup as well.

This article develops the technique from first principles. It covers hash positions, collisions, chaining, open addressing, linear probing, double hashing, probe distance, displacement swaps, early termination, load factor, resizing, rehashing, deletion, complexity, and practical uses such as frequency counting, deduplication, two-sum lookups, grouping, caching, and prefix-sum maps.

1. From a key to an initial bucket​

A hash table stores key-value entries or keys in an array of slots. A hash function converts a key into a hash value. The table then maps that value to an initial bucket, also called the key’s ideal position.

Suppose a table has $m$ slots numbered from $0$ through $m-1$. A simplified bucket calculation is:

Here, $h(\\text{key})$ is the hash value produced for the key. The modulo operation maps a potentially large integer into the table’s valid index range.

For a table with $7$ slots, suppose three keys produce the following hash values:

key A -> 10
key B -> 17
key C -> 24

Their initial buckets are:

All three keys prefer bucket $3$. This is a collision: different keys map to the same initial position.

A hash function does not normally guarantee that every key receives a unique bucket. Collision resolution is therefore a central part of every hash-table design. Two broad approaches are chaining and open addressing.

2. Chaining and open addressing​

With chaining, each bucket refers to a separate collection of entries. If several keys map to bucket $3$, that bucket might contain a linked list, dynamic array, or another collection holding those entries.

The conceptual layout could be:

bucket 0: empty
bucket 1: empty
bucket 2: empty
bucket 3: A, B, C
bucket 4: empty
bucket 5: empty
bucket 6: empty

A lookup computes bucket $3$ and then searches the collection attached to that bucket. If the collection is short, the operation is efficient. If many keys accumulate in one bucket, the search becomes longer.

Open addressing uses a different strategy. Every entry is stored directly in the main table array. When the preferred bucket is occupied, the table follows a probe sequence to search for another slot.

For the same collision, an open-addressed layout might be:

bucket 0: empty
bucket 1: empty
bucket 2: empty
bucket 3: A
bucket 4: B
bucket 5: C
bucket 6: empty

The precise locations depend on the probing rule. The important difference is that the entries remain inside the table rather than being placed in an external chain.

Robin Hood hashing belongs to the open-addressing family. Its distinctive feature is not simply that it probes another slot. During insertion, it compares how far entries have traveled and may exchange them.

3. Probe distance​

An entry’s probe distance describes how far its current position is from its initial bucket along the table’s probe sequence. With circular linear probing, the distance can be represented as:

The initial position has distance $0$. The next position in the probe sequence has distance $1$, then $2$, and so on.

For a table with $7$ slots, a key that initially belongs at bucket $3$ but is stored at bucket $5$ has distance:

The key has moved two probe steps from home.

Wraparound is handled in the same way. If a key begins at bucket $6$ but is stored at bucket $1$, its distance is:

The numerical index difference is negative, but the circular probe distance is still two steps.

Probe distance is not necessarily the same as the arithmetic difference between array indexes. It is the number of steps taken along the probe sequence. This distinction becomes especially important when the table wraps around or uses a non-linear sequence such as double hashing.

4. The Robin Hood insertion rule​

The central insertion rule is:

If the incoming entry has a greater probe distance than the entry occupying the candidate slot, swap them. The incoming entry settles at that slot, and the displaced entry continues probing.

The word incoming is relative to the current step. At the beginning, it refers to the key being inserted. After a swap, it refers to the displaced entry that must keep searching.

A simplified insertion process is:

1. Compute the key’s initial bucket.
2. Start with probe distance $0$.
3. Inspect the current slot.
4. If the slot is empty, place the entry there.
5. If the slot contains the same key, update or handle the existing entry according to the map or set operation.
6. If the resident entry has a smaller probe distance than the incoming entry, swap the two entries.
7. Move to the next position and increase the distance of the entry still being inserted.
8. Continue until the displaced or original entry reaches an available slot.

The comparison is often expressed as a strict greater-than rule. Equal distances do not require a swap, although a particular implementation can define a different tie-breaking policy.

Ordinary linear probing usually leaves an occupied entry in place and keeps moving the new entry forward. Robin Hood insertion may move the resident entry so that the larger displacement is assigned to the entry that needs it more.

5. A concrete displacement example​

Consider a table with $7$ slots and circular linear probing. Suppose the table contains the following entries:

bucket 0: empty
bucket 1: empty
bucket 2: empty
bucket 3: A, initial bucket 3, distance 0
bucket 4: B, initial bucket 4, distance 0
bucket 5: C, initial bucket 3, distance 2
bucket 6: empty

Now insert key $D$, whose initial bucket is $3$.

At bucket $3$, key $D$ has distance $0$. The resident key $A$ also has distance $0$, so $D$ does not displace $A$. It advances to bucket $4$.

At bucket $4$, $D$ has distance $1$, while $B$ has distance $0$. The incoming key has traveled farther, so Robin Hood insertion swaps them:

before:
slot 4 -> B, distance 0
incoming -> D, distance 1

after:
slot 4 -> D, distance 1
incoming -> B, distance 0

The displaced key $B$ now continues from the next probe position. It retains its own initial bucket and its own distance, adjusted as it moves through the sequence. If it reaches another occupied position whose resident has an even shorter distance, another swap may occur.

The purpose is not to minimize the distance of the new key at every step. The purpose is to prevent the table from developing a highly uneven distribution in which some entries are nearly at home while others have traveled through a long run of occupied slots.

6. Why balancing probe distances helps​

An unsuccessful lookup is especially revealing in an open-addressed table. To determine that a key is absent, the algorithm normally follows the key’s probe sequence until it finds an empty position or reaches another valid stopping condition.

A successful lookup also depends on displacement. If the desired key is close to its initial bucket, the search ends quickly. If it has been pushed far away by collisions, the lookup must inspect more positions.

Without a balancing policy, a table can contain a mixture of very short and very long probe distances. Average performance may still be acceptable, but individual operations can be less predictable. Robin Hood hashing attempts to reduce the spread by allowing entries with shorter distances to give way to entries with longer distances.

This does not eliminate collisions or make every search take the same number of probes. A poor hash distribution, a high load factor, or a nearly full table can still produce long searches. Robin Hood hashing changes how the table organizes collided entries; it does not change the fact that collisions are possible.

The practical goal is a more even displacement distribution. When extreme probe distances become less common, lookup behavior can become more predictable, particularly in workloads where the cost of the longest searches matters.

7. Early termination during lookup​

Probe distance can provide useful information during lookup, not just during insertion. Suppose a search for key $Q$ starts at its initial bucket and follows the same probe sequence used during insertion.

At each occupied position, the search can compare two things:

• whether the resident key is $Q$; and
• whether the resident key’s probe distance is smaller than the distance already traveled by the search.

If the resident entry has a smaller distance than the search distance, the lookup may terminate unsuccessfully, provided the table maintains the ordering invariant required by the implementation.

The intuition is that if $Q$ had been present during insertion, it would have had enough displacement to move past an entry with a shorter distance. Therefore, encountering such an entry can show that $Q$ should not appear farther along that probe sequence.

A conceptual lookup is:

start at the key's initial bucket
search distance = 0

repeat:
    if the slot is empty:
        report absent
    if the slot contains the key:
        report present
    if the resident distance is smaller than the search distance:
        report absent
    move to the next probe position
    increase search distance

The exact condition depends on how distances are stored, how ties are handled, and how deletion is implemented. Early termination is safe only when insertion and deletion preserve the ordering assumptions behind it.

This is an important distinction. Robin Hood hashing does not merely rearrange entries during insertion. It can make the arrangement itself meaningful during lookup. A search may be able to conclude that a key is absent before reaching an empty slot.

8. Linear probing​

Linear probing is the simplest open-addressing sequence. If the initial bucket is $b$, the table examines:

With $m=8$ and initial bucket $6$, the sequence is:

6, 7, 0, 1, 2, 3, 4, 5

Linear probing is attractive because it is simple and usually examines nearby memory locations. However, consecutive occupied slots can form a run. Once a run exists, later insertions and lookups may have to inspect much of the same region. This tendency is often called clustering.

Robin Hood hashing is commonly explained with linear probing because the distance calculation is straightforward. An entry’s probe distance is simply the number of forward steps from its initial bucket, including wraparound.

The Robin Hood rule does not replace linear probing’s sequence. It changes what happens when the probe reaches an occupied slot. A standard linear-probing insertion keeps the incoming key moving. Robin Hood insertion first compares the two distances and may move the resident key instead.

9. Double hashing​

Double hashing uses a second hash calculation to determine the step size. If the first hash gives an initial position $h_1(\\text{key})$ and the second gives a step value $h_2(\\text{key})$, a typical probe position is:

The first probe uses $i=0$, the next uses $i=1$, and so forth. For example, with $m=11$, an entry might have $h_1=3$ and $h_2=4$. Its probe sequence begins:

3, 7, 0, 4, 8, 1, ...

Double hashing can spread probes through the table in a pattern different from adjacent linear positions. It is another way to resolve collisions within open addressing.

Robin Hood hashing is a displacement policy rather than a particular hash function. A probe sequence may be linear or based on another open-addressing strategy, but the distance must be defined consistently with that sequence. With double hashing, distance means the number of steps in the sequence, not necessarily the arithmetic distance between indexes.

Insertion and lookup must use the same sequence. If insertion uses one sequence and lookup uses another, a stored key may not be found. If early termination uses resident distances, those distances must describe the same sequence followed by the lookup.

10. Load factor​

The load factor measures how full an open-addressed table is. If $n$ slots are occupied in a table with capacity $m$, the load factor is:

For a table with $7$ slots and $5$ occupied positions:

As $\\alpha$ increases, fewer empty slots remain available. Insertions have fewer places to stop, and lookups are more likely to pass through occupied positions before finding either the target or an empty slot.

Robin Hood hashing can balance the distribution of distances, but it still needs available capacity. A nearly full table can produce long probe sequences under any open-addressing policy.

Implementations therefore choose a capacity policy and a threshold at which the table grows. The exact threshold is an implementation decision, not a universal property of Robin Hood hashing. A conceptual policy looks like this:

if the next insertion would make the table too full:
    allocate a larger table
    rehash every existing entry
    insert the new entry

The threshold should leave enough empty space for the intended performance characteristics. The right value depends on the implementation, memory layout, hash distribution, and desired trade-off between memory use and probe length.

11. Resizing and rehashing​

When the capacity changes, the modulo operation changes as well. An entry that belonged at bucket $3$ in a table of size $7$ may belong somewhere else in a table of size $13$.

For a key with hash value $24$:

The old slot cannot simply be copied into the new table as the key’s permanent position. The table must recompute the initial bucket using the new capacity and insert the entry according to the probing and Robin Hood rules.

This process is rehashing. Existing entries are visited, their new initial positions are computed, and they are placed into the new array. Their old probe distances are not necessarily valid because both the capacity and the surrounding layout have changed.

A resize can take $O(n)$ time for $n$ stored entries. That cost is paid occasionally rather than on every insertion. If the table grows sufficiently, the total cost of these occasional rebuilds can be spread over many operations, producing average or amortized $O(1)$ insertion under the usual assumptions.

The precise growth factor, load-factor threshold, and allocation strategy are implementation choices. The general rule is fixed: changing capacity changes bucket calculation, so entries must be rehashed rather than copied blindly.

12. Deletion requires care​

Deletion is more subtle in open addressing than insertion. Consider a key that begins at bucket $2$ but is stored at bucket $3$ after a collision. A later key may also begin at bucket $2$ and be stored at bucket $4$ because buckets $2$ and $3$ were occupied.

If the entry at bucket $3$ is removed by turning that slot into an ordinary empty slot, a lookup for the key at bucket $4$ might stop at bucket $3 and incorrectly report that the key is absent.

Open-addressed tables therefore need a deletion strategy that preserves the search structure. Common conceptual approaches include tombstones and backward shifting.

A tombstone marks a slot as previously occupied. A lookup must continue through a tombstone, but an insertion may eventually reuse it. Too many tombstones can lengthen future probes, so implementations may periodically clean them up by rebuilding the table.

Backward shifting removes a gap by moving later entries toward the deleted position when their placement remains valid. This can preserve a compact probe sequence without leaving a permanent tombstone, but the movement rules must maintain the table’s displacement invariant.

Robin Hood hashing does not make deletion automatically simple. Its ordering property must remain valid after an entry is removed. Early termination is safe only when the chosen deletion strategy preserves the assumptions that justify it.

13. Hash maps and hash sets​

A hash map stores associations between keys and values. A lookup hashes a key, follows the relevant probe sequence, and compares stored keys until it finds the requested entry or concludes that the key is absent.

A hash set stores keys without separate associated values. Its operations are similar: test membership, insert a key, or remove a key. Robin Hood hashing can support either structure because the core operation is locating keys. A map adds a value field to each entry.

Under favorable conditions, lookup, insertion, and deletion are commonly described as average $O(1)$. The assumptions include a suitable load factor, a sufficiently well-distributed hash function, a correct probe sequence, and appropriate resizing and deletion behavior.

The worst case for a single operation remains $O(n)$ for a table containing $n$ entries. A search may need to inspect a large portion of the table, especially when the table is nearly full or the hash distribution is poor.

Space usage is $O(m)$ for a table with capacity $m$, including unused slots and metadata for occupancy, distances, or deletion markers. The number of stored entries is $n$, with $n \\leq m$ for ordinary open addressing.

14. Frequency counting​

Frequency counting is a direct hash-map application. Given a sequence of words, the algorithm maintains a map from each word to its count.

for each word:
    if word is already in the map:
        increase its count
    otherwise:
        store count 1

The word is the key, and the frequency is the value. Robin Hood behavior matters when many keys occupy nearby probe regions: entries with greater displacement can displace entries with shorter displacement, and lookup can use distance information when the table’s invariants allow early termination.

If the input contains $n$ words and the table is maintained appropriately, the expected total time is commonly average $O(n)$. This follows from performing an average $O(1)$ map operation for each word. The worst-case total can be $O(n^2)$ if many operations repeatedly encounter long probe sequences.

The map’s storage depends on the number of distinct words and its capacity. If there are $u$ distinct words, the table stores $u$ entries and uses capacity $m$ selected to keep the load factor within the intended range.

15. Deduplication​

A hash set is useful for removing duplicates. Scan the input and insert each item into the set. If insertion reports that the item is already present, the item is a duplicate.

input:  apple, pear, apple, plum, pear
unique: apple, pear, plum

The set does not need a separate count when the goal is only membership. Robin Hood hashing supplies an open-addressed layout in which displacement information guides insertion and can guide lookup.

If there are $n$ input items and $u$ distinct items, average processing time is commonly $O(n)$ under suitable assumptions. The set stores $u$ keys, while its actual table space is $O(m)$ for capacity $m$. As with other hash-based methods, the worst-case processing time can be larger if operations encounter very long probe sequences.

16. Two-sum style lookups​

In a two-sum style problem, the algorithm scans values and asks whether a complementary value has already been seen. If the target is $T$ and the current value is $x$, the needed complement is:

A set or map can answer whether that complement has appeared.

for each value x:
    needed = target - x
    if needed is in the set:
        report a matching pair
    insert x into the set

With average $O(1)$ lookup and insertion, the full scan is average $O(n)$ rather than the $O(n^2)$ behavior of checking every pair directly. The broad worst-case bound remains sensitive to hash-table behavior and can be $O(n^2)$.

A map is useful when the algorithm must remember an index, a count, or other information associated with each value. Robin Hood hashing affects how those key lookups are organized internally; the two-sum logic remains the complement calculation.

17. Grouping and caching​

Grouping uses a map from a group key to a collection of members. A program might map a category to all records belonging to that category. For each record, it computes the group key, looks up the corresponding collection, and adds the record.

Caching uses a map from a request key to a stored result. A lookup checks whether a result is already present. On a miss, the program computes the result and stores it under the key.

Both applications benefit from average constant-time equality lookup, but neither is guaranteed to be constant-time in every situation. Cache capacity, eviction policy, load factor, key equality, hash computation, and value-management costs all matter in a practical system.

Robin Hood hashing addresses the table’s internal probe behavior. It does not decide which cached value should be evicted, how long a value remains valid, or how expensive it is to compute a key’s hash.

18. Prefix-sum maps​

Prefix-sum algorithms often use a map from a prefix value to a count or index. Suppose a running prefix sum at one position is $p$ and a later prefix sum is $q$. The sum of the intervening range is:

To find a range with target sum $T$, a scan can ask whether an earlier prefix sum equal to $q-T$ exists:

A map makes this query efficient on average. The map may store how many times a prefix has appeared or the earliest index at which it appeared, depending on the problem.

For an input of length $n$, a typical prefix-sum map algorithm performs $O(n)$ total average work under the usual hash-table assumptions. It uses $O(n)$ auxiliary space when many prefix values are distinct. Robin Hood hashing can provide the underlying map implementation while the algorithmic idea comes from the relationship between two prefix sums.

19. Hashing compared with sorting​

Hashing and sorting solve different kinds of problems. A hash set can support equality-based membership checks while items arrive, with average $O(1)$ lookup and insertion under suitable assumptions. Comparison-based sorting generally requires collecting the items first and commonly takes $O(n \\log n)$ time.

For deduplication, hashing can process items without producing sorted output. Sorting can be preferable when the result must be ordered, when deterministic traversal is important, or when adjacent equal items after sorting make duplicate detection convenient.

Hashing does not naturally provide order. A hash table is organized by hash values, array positions, and probe sequences rather than by the numerical or lexicographic order of its keys. If an application needs predecessor, successor, range, or ordered traversal operations, sorting or a tree-based structure may be a better fit.

Hashing can also use more table capacity than the number of stored entries because it needs empty slots to keep probes short. Sorting may use different memory depending on the algorithm and data representation. The right choice depends on whether the primary need is fast equality lookup or ordered data.

20. Hashing compared with balanced trees​

Balanced search trees maintain an ordering relationship between keys. When the tree remains balanced, search, insertion, and deletion are typically $O(\\log n)$ in both average and worst-case asymptotic terms.

Hash tables offer average $O(1)$ operations but can have $O(n)$ worst-case behavior. Trees naturally support ordered traversal, predecessor and successor queries, and range operations. A hash table is usually better suited to direct equality lookup and key-to-value access, but it does not directly answer which key is next in sorted order.

The choice depends on the operation set. Use hashing when fast equality-based membership or lookup is the main requirement and average-case performance is acceptable. Consider a balanced tree when predictable logarithmic bounds, sorted iteration, or range queries matter more than average constant-time equality lookup.

Robin Hood hashing is not a replacement for every tree or every hash-table strategy. It is a policy for arranging entries in an open-addressed table so that probe distances are more balanced and lookup behavior can be more predictable.

21. Important implementation invariants​

A correct Robin Hood implementation must maintain consistent information about each entry. The implementation needs a way to determine the entry’s initial position or probe distance, either by storing distance metadata or by computing it from the key and current position.

The main invariants are conceptual:

• Every stored key lies on the probe sequence derived from its hash.
• An entry’s recorded or computed distance matches its current position in that sequence.
• A displacement swap moves the entry with the smaller distance out of the way of the entry with the larger distance.
• Lookup follows the same probe sequence used by insertion.
• An early-termination rule is used only when the current layout satisfies the ordering assumptions behind it.
• Resizing rehashes entries because changing capacity changes the initial bucket.
• Deletion preserves the ability to find entries that appear after a removed position.

These are correctness conditions, not merely performance preferences. If a stored distance is wrong, a swap can be made at the wrong time. If lookup uses a different sequence from insertion, an existing key may not be found. If deletion creates an invalid gap, an unrelated key may become unreachable.

22. What Robin Hood hashing does and does not promise​

Robin Hood hashing provides a strategy for distributing displacement more fairly among entries in an open-addressed table. It uses probe distance to decide when to swap, and that same information can support earlier unsuccessful lookup termination.

It does not make collisions disappear. Different keys can still have the same initial bucket. It does not guarantee that every operation is always $O(1)$. The worst case can still be linear in the number of stored entries. It does not remove the need for resizing, a suitable load factor, correct deletion handling, or a reasonably distributed hash function.

It also does not require every implementation to use exactly the same metadata, tie-breaking rule, deletion method, or resize threshold. Those are design choices. The stable idea is the displacement comparison: when two entries meet, the one that has traveled farther gets priority over the one that has traveled less.

The technique should therefore be understood as a policy layered on top of open addressing. The hash function chooses an initial position. The probe sequence identifies possible alternate positions. Robin Hood insertion decides which entry should occupy a contested position. Lookup uses the resulting organization, including early termination when the invariants justify it.

23. A compact mental model​

Imagine that every key has an ideal home bucket. Collisions force keys away from home. Probe distance measures the cost paid by each key.

Ordinary open addressing can allow that cost to become uneven. One key may remain nearly at home while another is pushed through a long run of occupied slots. Robin Hood hashing asks the key with the larger cost to take priority. The key with the smaller cost gives up its position and tries the next one.

During lookup, the same costs provide information. If the search has traveled farther than the resident key’s displacement, the desired key may not appear later in that probe sequence. When the table’s invariants support that conclusion, the search can terminate without waiting for an empty slot.

The result is not a new hash function and not a guarantee of identical lookup times. It is an insertion and lookup policy built on top of open addressing. Its objective is to reduce the unevenness of probe distances and make behavior easier to predict.

24. Final takeaways​

• A hash function maps a key to an initial bucket, commonly using $h(\\text{key}) \\bmod m$.
• A collision occurs when different keys choose the same initial bucket.
• Chaining stores colliding entries in a per-bucket collection, while open addressing searches for another slot in the table.
• Linear probing checks consecutive positions, while double hashing uses a second hash value to determine the step size.
• Probe distance measures how far an entry has traveled from its initial position along its probe sequence.
• Robin Hood insertion swaps entries when the incoming entry has traveled farther than the resident entry.
• The displaced entry continues probing from the next position.
• Probe-distance information can make unsuccessful lookups terminate earlier when the table’s ordering invariant allows it.
• The load factor is $\\alpha = n/m$; as the table fills, probe sequences become increasingly important.
• Resizing changes the capacity, so entries must be rehashed rather than copied blindly to their old positions.
• Average hash-table lookup, insertion, and deletion are commonly $O(1)$ under suitable assumptions, while worst-case operations can be $O(n)$.
• Hash sets and maps support frequency counting, deduplication, two-sum lookups, grouping, caching, and prefix-sum maps.
• Sorting and balanced trees remain useful when ordered output, range operations, or stronger worst-case guarantees are required.

Robin Hood hashing is best remembered as a fairness rule for open addressing: when two entries meet, let the one that has traveled farther sit first. By reducing the unevenness of probe distances and using those distances during lookup, the technique aims to make hash-table behavior more predictable without abandoning the fast average-case model that makes hash-based structures useful.