solution

Revisit the aforementioned exercise. Robin Hood hashing (RHH) is slightly modified variant of an open-addressing hash map [6]. We augment each key–value pair with an additional counter that stores the number of hops performed during the linear probing phase. Note that RHH can also be used with other probing schemes such as quadratic or chaotic probing. A “rich” key–value–count triple has performed less hops during the insertion than a “poor” one. RHH introduces the following modification of the probing scheme: whenever a poor triple encounters a rich triple during probing,
the poor triple is stored at the position of the rich one. Afterwards, the probing is continued with the rich triple until it finds an empty slot or an even richer triple. RHH performs better for higher load factors (number of stored elements/capacity) since it automatically equalizes the probing lengths during insertion.
a. Can you exploit the counter stored in a triple in order to accelerate the querying step?
b. Implement a lock-free version of a Robin Hood hash map that uses 128 bits for the key–value–counter triple.
c. Extend your implementation to support key, values, and counters of arbitrary width, e.g. 20 bits for the key, 20 bits for the value, and 24 bits for the counter.