Question

10) Using Hopscotch hashing with a max hop of 4, hash the following keys.

Use a table of size 13 (indexes 0-12).

A: 6
B: 7
C: 9
D: 7
E: 6
F: 7
G: 8

Answer 1

Hopscotch hashing is applied to a set of keys with a max hop of 4. The resulting hash table is: IndexKey5G (8)6A (6)7B (7)8D (7)9C (9)10E (6)11F (7). The resulting hash table is shown below.

Step-by-step explanation:

An example of Hopscotch hashing with a max hop of 4 and a table size of 13 is as follows:

• Key A (6) is hashed to index 6, which is empty.
• Key B (7) is hashed to index 7, which is also empty.
• Key C (9) is hashed to index 9, which is empty.
• Key D (7) causes a hop of 1 to index 8, which is empty.
• Key E (6) causes a hop of 2 to index 10, which is also empty.
• Key F (7) causes a hop of 1 to index 11, which is empty.
• Key G (8) causes a hop of 4 and wraps around to index 5, which is empty.

The resulting hash table is:

IndexKey5G (8)6A (6)7B (7)8D (7)9C (9)10E (6)11F (7)