Open addressing. Consider a double hashing open addressing scheme with hash func

Question

Open addressing. Consider a double hashing open addressing scheme with hash functions

h1(k) = k mod 17 if (k mod 17) >0 and = 17 if (k mod 17) = 0; and

h2(k) = k mod 5, except that if k(mod 5) = 0, h2(k) = 5.

Assume the memory into which the keys are hashed has size 17 with addresses 1, 2, …,17.

In succession, insert the following keys in this memory via this hashing scheme. Display what is in the memory after each step of that process.

Keys to be hashed in this order.

k= 54;

k= 73;

k=139;

k = 107;

k=122

Explanation / Answer

k = 54

h1(k) = 54 mod 17 = 3

so

k = 73

h1(k) = 73 mod 17 = 5

k = 139

h1(k) = 139 mod 17 = 3

which is collapsing

so we check h2(k) = 3 mod 5 = 3

so 3 + 3 = 6

k = 107

h1(k) = 107 mod 17 = 5

h2(k) = 5 (as 5 mod 5 is 0)

so key will go to h1(k) + h2(k) = 10

k = 122

h1(k) = 122 mod 17 = 3

h2(k) = 3 mod 5 3

so we will put on 3 + 3 but as it is already filled we will try

3 + 3*2 = 9

so

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.