问题描述:

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.

您可能感兴趣的文章：

- javascript - Reach main viewport from controller
- c++ - Demo code is throwing a out_of_range exception but I don't know why
- SQLitedb implementation for android messaging
- angularjs - Angular changes values in all arrays
- Grouping by multiple fields in MongoDB
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**