Hopscotch Hashing

Write a program that implement an efficient hopscotch hash table using C++ that improves on the classic linear probing algorithm.

- Use Table_size = 17. (constant)

- Use single prob hash function h(x) = x mod Table_size

- You shall resolve collisions using linear probing where the maximal length of the probe sequence is bound by the hopscotch hashing algorithm where max_distance = 4.

- You must keep an item array containing the elements

- as well as an associated hop array that indicates positions in the item array that are occupied with items that hash to the same value.****

Can you explain using code or psedo code on how to do the last step? ****

From my understanding the array is called a bitmap array, that uses 0000 as its intial value and when an item is inserted in itself it changes to 1000 using Xor, or when inserted one ahead its 0100 using Xor again, and so on for the 3 places infront. How do I set this kind of array up? specifically explain how I would initiate the array so its intitial value is 0000, and what kind of math I would use to change its value in either of the 4 places.