I am reading about hopscotch hashing
The algorithm says when we run into colision during insert:
Otherwise, j is too far from i. To create an empty entry closer to i, find an
item y whose hash value lies between i and j, but within H − 1 of j, and
whose entry lies below j. Displacing y to j creates a new empty slot closer
to i. Repeat. If no such item exists, or if the bucket already i contains H
items, resize and rehash the table.
I am not sure how this works.
Example. Assume H = 3 and that a,b,c all map to 0 and d,e map to 1
We have:
0 1 2 3 4 5
[a, b, c, d, , ] the table with 2 slots empty
i j
b,c are within H - 1 (2) places away of their position (0) in locations 1,2 of the table and d is within 2 positions from its location 1.
If I try to insert e that also maps to 1 I would start from index 4 (an empty slot found with linear probing) and would work backwards towards 1.
According to the algorithm index 3 (which has now d) is between i and j (which are 1 and 4 respectively) and within H - 1 i.e. 2 positions of j.
So we can swap and have:
0 1 2 3 4 5
[a, b, c, , d , ] the table with 2 slots empty
i j
so now the empty slot is 3 and we can insert e since it is 2 positions away from i.
But now d whose hash value maps to 1 is more than 2 positions from 1 and can no longer be found.
So how does this algorithm work?
Note: My assumption and understanding is that the hop value is only an optimization trick for not having to run the equality over all H elements belonging to the bucket and not related with the core algorithm per se.
It says find an item whose hash value lies between i and j, but within H-1 of j. It doesn't say find an item whose current location lies between i and j, but within H-1 of j. The d at index 3 has a hash value of 1, which doesn't lie within 2 positions of 4.
In your example, there are no suitable slots, so the following sentence takes effect and the table should be resized and rehashed.