Robin Hood Hashing is an alternative hashing collision resolution technique similar to the Coalesced, Cuckoo and Hopscotch techniques.
The idea is that a new key may displace a key already inserted, if its probe count is larger than that of the key at the current position.
The probe count of a value is the distance between its current position and its real position. For example, if a value $v$ must be put in the cell $i$ (real position) but as the cell is not empty, it is put in cell $j$ (current position), the number of probes is equal to the $j-i$.
In such a hash table, the rich elements are the values that are closest to their index; the poor elements are further away. In Robin Hood hashing, each new addition results in the following task:
- If the cell $T[H(v)]$ is empty, put $v$ in $T[H(v)]$. Otherwise, if the cell is not empty, use the linear probing method to search for an empty cell to put $v$ or a cell $c$ with fewer probes than $v$. In the latter case, put $v$ in $c$.
- If $v$ has replaced another value, add the replaced value in table following the same process.
The insertion fails if there are no more places in the array.
The algorithm uses a single array of $\texttt{N}$ elements of type $\texttt{char}$.
Given the following:typedef char element;typedef element hash[N];
- Write a function that inserts an element $\texttt{val}$ of type $\texttt{char}$ into such hash table using the Robin Hood hashing algorithm.
Prototype: $\texttt{int insert(hash h, element val)}$
Example
Let $N=11$, $H(k)=((int)k)\%N$.
Let the keys be the following, along with their hashing values:
\begin{array}{| c | c |c |c |c |c |c |c |c |c | }\hline
k & D& r &X &F &h &a &S &v &g \\ \hline
H(k) & 2 &4 &0 &4 &5 &9 &6 &8 &4 \\ \hline
\end{array}
Insertion of D of hash value = 2, add in index 2 since empty cell:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & & &D&&&&&&& & \\ \hline
\end{array}
Insertion of r of hash value = 4, add in index 4 since empty cell:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & & &D&&r&&&&& & \\ \hline
\end{array}
Insertion of X of hash value = 0, add in index 0 since empty cell:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r&&&&& & \\ \hline
\end{array}
Insertion of F having the hash value = 4.
Index 4 is occupied by r, having the same hash value. The probe count is for both r and F is 0. We keep r in its place. By linear probing, we check the next cell of value 5. Since it's empty, we add F there, the probe count for F is now equal to 1.
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r& F&&&& & \\ \hline
\end{array}
Insertion of h of hash value = 5. Index 5 is occupied by F, having the hash value of 4, its probe count is thus 1 while the probe count of h is 0. Thus F should stay closer to its probing value (i.e. the "poor" value), while h needs to be placed elsewhere (i.e. the "rich" value). By linear probing, we check the next cell of value 6. Since it's empty, we add h there.
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r& F&h&&& & \\ \hline
\end{array}
Insertion of a of hash value = 9, add in index 9 since empty cell:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r&&&&& a & \\ \hline
\end{array}
Insertion of S of hash value = 6. Similar to the insertion of h.
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r& F&h&S&& a & \\ \hline
\end{array}
Insertion of v of hash value = 8, add in index 8 since empty cell:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r& F&h&S&v& a & \\ \hline
\end{array}
Insertion of g of hash value = 4.
Index 4 is occupied by r, having the same hash value, both prob counts are thus 0. Since both elements hash to the same hashing value, the probe length will be the same for both, r stays in its position, and by linear probing, we check the next cell of value 5, the probe count of g is now equal to 1.
Index 5 is occupied by F, having the same hash value, both probe counts are thus 1. Since both elements hash to the same hashing value, the probe count will be the same for both, F stays in its position, and by linear probing, we check the next cell of value 6.
Index 6 is occupied by h, having the hash value of 5, its probe count is thus 1 while the probe count of g is now 2. Thus g (i.e. the "poor" value) should stay closer to its probing value, while h needs to be placed elsewhere. g takes the place of h and we resume the adding process with h. We iterate the same process till we reach the following table:
\begin{array}{|c |c|c|c|c|c|c|c|c|c|c|c|c|}\hline
index & 0 & 1&2&3&4&5&6&7&8&9 &10 \\ \hline
T & X & &D&&r& F&g&h&S&v&a \\ \hline
\end{array}
Difficulty level
This exercise is mostly suitable for students
No solutionBack to the list of exercises
Looking for a more challenging exercise, try this one !!
Automata