问题描述:

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.

相关阅读:
Top