Computer Science Topic: Hashing The keys 28, 5, 15, 19, 10, 17, 33, 12, 20, 6, 9
ID: 3573362 • Letter: C
Question
Computer Science Topic: Hashing
The keys 28, 5, 15, 19, 10, 17, 33, 12, 20, 6, 9, 23, 34, 22 and 21 are to be inserted in order into a hash table of length 9.
Show the result of inserting the keys into a hash table of length 9 where collisions are resolved by open addressing, with hash function: h ( k , i ) = ( k mod 9 + 5i ) mod 9
Note that in this case there are more keys than slots, so you won't be able to insert all the keys. Just insert the keys in the given order until there is no more room in the table. Please draw a picture of the array and its contents. Show your work for each key.
Solution should be: | 20 | 28 | 19 | 33 | 12 | 5 | 15 | 10 | 17 | But I am just not getting the same solution.
Explanation / Answer
Let us take i=0, then
Keys=28,5,15,19,10,17,33,12,20,6,23,34,22 and 21
Initially empty hash table (array)
h(k,i)=(k mod 9 + 5i) mod 9
=>28mod9+5(0) mod9=1mod9=1
28
Next 5mod9+5(0)mod9=5
28
5
15mod9+5(0)mod9=6mod9=6
28
5
6
19mod9+5(0)mod9=1mod9=1
As index 1 has 28, this is collision. And we have to use open addressing i.e. linear probing. =>1+1=2
28
19
5
6
10mod9+5(0)mod9=1mod9=1
Again collision=>1+1=2. As in index 2we have 19, it is again a collision=>2+1=3
28
19
10
5
6
17mod9+5(0)mod9=8mod9=8
28
19
10
5
6
17
33mod9+5(0)mod9=6mod9=6
Collision, as already at index 6 element 6 is their=>6+1=7
28
19
10
5
6
33
17
12mod9+5(0)mod9=3mod9=3
Collision, as already at index 3 we got 10=>3+1=4
28
19
10
12
5
6
33
17
20mod9+5(0)mod9=2mod9=2
Collision, 2+1=3 (collision), 3+1=4(collision), 4+1=5(collision), 5+1=6(collision), 6+1=7(collision), 7+1=8 (collision), 8+1=9mod9=0
20
28
19
10
12
5
6
33
17
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.