Description
Implement a Hopscotch hash table. Your implementation should utilize the provided
HopScotchHash.h file as is, without any edits.
Each Hopscotch table entry consists of an item represented as a string, a key that is
used to determine the hash value, a hop bitmap field, and a Boolean value
determining if the entry contains a value, or if it is empty.
The MAX_DIST constant defines the maximum number of probes in a prove
sequence, and the hash function for the table is defined as a basic division hash (i.e.
(key) mod (table size)).
The HopScotchHash class contains the following members:
• table – A vector of hash entries, as described above
• myHash – Accepts a hash key, and returns its hash value, using division hash:
(key) mod (table size))
• HopScotchHash – Constructor of an empty hopscotch hash table of a given
size
• Insert – Inserts a given hash entry x to the hash table
• shiftDown – accepts a hash entry x, the desired location for x in the hash table
EC330 Applied Algorithms and Data Structures for Engineers, Fall 2019
(e.g. the hash value of x), and the closest open location available, makes room
for a new hash entry x by moving other elements
• printContent – prints the content of the hash table, as described below
Your program should read an input file, input.txt, consisting of one input per line,
each input represented as a pair: a string (item name) and an integer (key), separated
by a space. The inputs should be inserted to the table one after the other in order, and
the final content of the hash table should be printed out in the provided format below.
Note that you are not allowed to access the key of the hash entries directly. All hash
values of table elements should be computed from the corresponding Hop fields.
Sample input.txt file content (provided):
A 7
B 9
C 6
D 7
E 8
F 12
G 11
H 9
I 6
Expected output for the above input, with MAX_DISTANCE of 4, and table size 17:
Index Item Hop
0 – 0000
1 – 0000
2 – 0000
3 – 0000
4 – 0000
5 – 0000
6 C 1001
7 A 1100
8 D 0010
9 I 0011
10 E 0000
11 H 0001
12 B 0100
13 F 0000
14 G 0000
15 – 0000
16 – 0000
