A hash function hash(k) = k mod 11 an incremental hash function is d(k) = (k mod 7) + 1.
Question
A hash table has a size of 11. And a hash function hash(k) = k mod 11 an incremental hash function is d(k) = (k mod 7) + 1. Inserting the following numbers in sequence: [7, 23, 29, 15, 34], how many key comparisons are done when each of these records is searched for after they are all inserted?
Summary
Here in the given question, there is a hash table with the size 11. And also we have given a function. We have to insert the given number in the sequence. And have to find how many key comparisons are done.
Explanation
We will insert the number in the sequence of [7, 23, 29, 15, 34]
Inserting of 7
Hash(7)= 7 mod 11=7 (insert at 7 position)
Inserting of 23
Hash(23)= 23 mod 11= 1 (insert at 1 position)
Inserting of 29
Hash(29)= 29 mod 11= 7 (collision)
D(29)= (29 mod 7)+1= 2
Position= Hash(29)+D(29)= 9 (insert at 9 position)
Inserting of 15
Hash(15)= 15 mod 11= 4 (insert at 4 position)
Inserting of 34
Hash(34)= 34 mod 11= 1 (collision)
D(34)= (34 mod 7)+1= 7
Position=Hash(34)+ d(34)=8 (insert at 8 position)
And then we have
| Value | Number of Comparisons | Explanation |
| 7 | 1 | Can get position directly using hash function. |
| 23 | 1 | Can get position directly using a hash function. |
| 29 | 2 | Using hash function the value is not found, so we use incremental hash function formula to get the position. |
| 15 | 1 | Can get position directly using a hash function |
| 34 | 2 | Using hash function the value is not found, so we use incremental hash function formula to get the position. |
Also read, Find the output of the given code in python
