Consider inserting the keys 5,23,2,54.15.42,35 into a hash table of length m = 1
ID: 3676298 • Letter: C
Question
Consider inserting the keys 5,23,2,54.15.42,35 into a hash table of length m = 10 with the hash function h(k) = k mod 10. Illustrate the result of inserting these keys using linear probing to resolve collisions. Illustrate the result of inserting these keys using chaining to resolve collisions. Consider inserting the keys 15,1,11 into a hash table of length m = 8 with the hash function h(k) = lm(kA - where A = 0.625. Illustrate the result of inserting these keys. Now compute the hash function of the key 11 using the implementation we described in our notes. You can assume we have a word size w = 4. Since m = 8 = 2^3 , p = 3. Since >1 = 0.625 = 10/2^4 = 10/2^W, s = 10. (Compute ks and convert it to a binary number. This number will consist of 2w bits. The largest p bits of the smaller w bits is the hash value of our key.)Explanation / Answer
so we can have 10 outcomes of the hash function here.
0,1,2,3,4,5,6,7,8,9
The data will be inserted
Key 0
Key 1
Key 2 2
Key 3 23
Key 4 54
Key 5 5
Key 6 15
Key 7 42
Key 8 35
Key 9
Key 10
In linear probing case if there is a collision then the next empty slot will be taken.
b)
Key 0
Key 1
Key 2 2,42
Key 3 23
Key 4 54
Key 5 5,15,35
Key 6
Key 7
Key 8
Key 9
Key 10
In chaining the chain are made for each collision for the hash table.
2)
for 15 it will be 8*(15*0.625 - 15*0.625) = 8*0.375=3
for 1 it will be 8*(0.625) = 5
for 11 it will be 8*(11*0.625 - 11*0.625) = 8*0.875 = 7
so they will use the keys and there is no collision here.
b)
It will be same as above.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.