I found an interesting story about Robin Hood when I first learned about Robin Hood Hashing(and there is another RobinHood that provides financial services, which I don’t believe is a coincidence). Robin Hood was a bandit, but he was a good guy who robbed the rich in order to give to the poor. And that implies the basic idea behind Robin Hood Hashing.
Basically, hash table has two different ways to store the values. The one is closed adressing(e.g., separate chaining) and the other is open addressing. Robin Hood Hashing is a variation of open addressing in hash tables. It aims to minimize the variance in probe sequence lengths by ensuring that elements with longer probe sequences “steal” slots from elements with shorter probe sequences. This approach helps balance the load and reduces clustering, improving overall performance.
Algorithm #
Probe Sequence Length #
Above we said robin hood hashing aims to minimize the probe sequence lengths. How we calculate the length? If we can found value just by looking in the bucket to which they hash, then we say the psl of this slot is 0. But if we need move on next bucket to find the slot, then the psl of this slot is 1. There is where “robbed the rich in order to give to the poor” happens. There might be a hugo difference psl among those values. What we want to do is balance them.
Insertion #
b = {};
void insert(v) {
p = hash(v) % b.length;
slot = {v, vpsl = 0}
while (b[p] != null) {
if (slot.vpsl > b[p].psl) {
swap(v, b[p])
}
p = (p + 1) % b.length
slot.vpsl = slot.vpsl + 1;
}
b[p] = slot
}
Removal #
Robin hood hashing use backward shifting to remove a slot. It works as follows:
- clear the slot which holding the key.
- shifting the keys in the following slots back one step to fill the gap until a key is encoutered with PSL 0 or an empty slot is found.
b = {};
void remove(v) {
p = hash(v) % b.length;
b[p] = null;
n = (p + 1) % b.length;
while (b[n] != null and b[n].psl != 0) {
b[p] = b[n];
b[n] = null;
p = n;
}
}