Question:
Draw the hash table from Exercise using a table size of 17 and open addressing using linear probing.
Exercise
Draw the hash table that results from adding the following integers (34 45 3 87 65 32 1 12 17) to a hash table of size 11 using the division method and linked chaining.
Answer:
Step: 1 of 5
The hash function using division method is defined as:
Hashcode(key) = Math.abs (key) % p
Where p is the size of the table, 17.
The open addressing method uses linear probing for handling collisions. When an element hashes to a position x that is already occupied, then the position (x + 1) % s is tried. Here, s indicates the size of the table (17). If the obtained position has also been occupied then the position (x + 2) % s is tried. The hashing continues by adding the numbers in a series to the position x until an empty cell is obtained.
Step: 2 of 5
Following are the hash codes for the keys (34 45 3 87 65 32 1 12 17)
Hashcode(34) = Math.abs(34) % 17
= 0
Hashcode(45) = Math.abs(45) % 17
= 11
Hashcode(3) = Math.abs(3) % 17
= 3
Hashcode(87) = Math.abs(87) % 17
= 2
Hashcode(65) = Math.abs(65) % 17
= 14
Hashcode(32) = Math.abs(32) % 17
= 15
Hashcode(1) = Math.abs(1) % 17
= 1
Hashcode(12) = Math.abs(12) % 17
= 12
Hashcode(17) = Math.abs(17) % 17
= 0
Position 0 is occupied, so hash code is calculated for next position.
Hashcode(17) = Math.abs(0 + 1) % 17
= 1
Step: 3 of 5
Position 1 is occupied, so hash code is calculated for next position.
Hashcode(17) = Math.abs(0 + 2) % 17
= 2
Position 2 is occupied, so hash code is calculated for next position.
Hashcode(17) = Math.abs(0 + 3) % 17
= 3
Position 3 is occupied, so hash code is calculated for next position.
Step: 4 of 5
Hashcode(17) = Math.abs(0 + 4) % 17 = 4
Step: 5 of 5
Hash table obtained by adding the keys to the hash table using linear probing:
I’m sourav, from Kolkata. A tech lover and love to answer any tech-related queries. I just try answering all questions like my problem.