6. Hash Table a) Draw the contents of the hash table in the boxes below given th
ID: 3713320 • Letter: 6
Question
6. Hash Table a) Draw the contents of the hash table in the boxes below given the following conditions: The size of the hash table is 12 Open addressing and double hashing is used to resolve collisions The hash function used is H(k)-k mod 12 The second hash function is: H2(k)-7-(k mod 7) What values will be in the table after the following sequences of insertions? Draw the values in the boxes below, and show your work for partial 33, 10, 9, 13, 12, 45, 26, 17 b) Pick a new table size which will solve the issues in part a). Show your work. 10Explanation / Answer
Size of the hash table = 12
Open addressing and double hashing will be used
First hash function: H(k) = k mod 12
Second hash function: H2(k) = 7 – (k mod 7)
0
1
2
3
4
5
6
7
8
9
33
10
10
11
H(33) = (33 mod 12) = 9 Make entry of 33 at 9th index in hash table
H(10) = (10 mod 12) = 10 Make entry of 10 at 10th index in hash table
0
12
1
13
2
9
3
4
5
6
7
8
9
33
10
10
11
H(9) = (9 mod 12) = 9 collision occurs as at 9th index we already have a entry of 33 so lets use double hashing to solve this.
H2(9) = 7 – (9 mod 7) = 7 – 2 = 5 - So the final index of hash table will be obtained as:
(H(9) + H2(9)) mod Hash table Size i.e
(9 + 5) mod 12 = 2
H(13) = (13 mod 12) = 1 Make entry of 13 at 1st index in hash table
H(12) = (12 mod 12) = 0 Make entry of 12 at 0th index in hash table
0
12
1
13
2
9
3
4
26
5
45
6
7
8
9
33
10
10
11
H(45) = (45 mod 12) = 9 collision occurs as at 9th index we already have a entry of 33 so lets use double hashing to solve this.
H2(45) = 7 – (45 mod 7) = 7 – 3 = 4 So the final index of hash table will be obtained as:
(H(45) + H2(45)) mod Hash table Size i.e
(9 + 4) mod 12 = 1 Collision occurs as as 1st index we already have a entry of 13 so lets find the next empty index i.e.
(H(45) + H2(45) + H2(45)) mod 12 = (9+4+4) mod 12 = 5 Make entry of 45 at 5th index in hash table.
H(26) = (26 mod 12) = 2 collision occurs as at 2nd index we already have a entry of 9 so lets use double hashing to solve this.
H2(26) = 7 – (26 mod 7) = 7 – 5 = 2 So the final index of hash table will be obtained as:
(H(26) + H2(26)) mod Hash table Size i.e
(2+2) mod 12 = 4 Make entry of 45 at 4th index in hash table.
0
12
1
13
2
9
3
4
26
5
45
6
7
8
9
33
10
10
11
H(17) = (17 mod 12) = 5 collision occurs as at 5th index we already have a entry of 45 so lets use double hashing to solve this.
H2(17) = 7 – (17 mod 7) = 7 – 3 = 4 So the final index of hash table will be obtained as:
(H(17) + H2(17)) mod Hash table Size i.e
(5 + 4) mod 12 = 9 Collision occurs as as 9th index we already have a entry of 33 so lets find the next empty index i.e.
(H(17) + H2(17) + H2(17)) mod 12 = (5+4+4) mod 12 = 1 Collision occurs as as 1st index we already have a entry of 13 so lets find the next empty index i.e.
(H(17) + H2(17) + H2(17) + H2(17)+H2(17)) mod 12 = (5+4+4+4+4+4) mod 12 = 9 Collision occurs as as 9th index we already have a entry of 33. Also now we know that we cannot insert this element into the hash table as we have reached 9 again after a complete cycle. Hence this element cannot be inserted into the hash table.
To solve the above issues let’s use hash table size of 10.
Size of the hash table = 10
Open addressing and double hashing will be used
First hash function: H(k) = k mod 10
Second hash function: H2(k) = 7 – (k mod 7)
0
10
1
2
3
33
4
13
5
6
7
8
9
9
H(33) = (33 mod 10) = 3 Make entry of 33 at 3rd index in hash table
H(10) = (10 mod 10) = 0 Make entry of 10 at 0th index in hash table
H(9) = (9 mod 10) = 9 Make entry of 10 at 9th index in hash table
H(13) = (13 mod 10) = 3 collision occurs as at 3rd index we already have a entry of 33 so lets use double hashing to solve this.
H2(13) = 7 – (13 mod 7) = 7 – 6 = 1 So the final index of hash table will be obtained as:
(H(17) + H2(17)) mod Hash table Size i.e
(3 + 1) mod 10 = 4 Make entry of 13 at 4th index in hash table
0
10
1
2
12
3
33
4
13
5
45
6
26
7
17
8
9
9
H(12) = (12 mod 10) = 2 Make entry of 12 at 2nd index in hash table
H(45) = (45 mod 10) = 5 Make entry of 45 at 5th index in hash table
H(26) = (26 mod 10) = 6 Make entry of 26 at 6th index in hash table
H(17) = (17 mod 10) = 7 Make entry of 17 at 7th index in hash table
0
1
2
3
4
5
6
7
8
9
33
10
10
11
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.