Given the numbers [5,-12,-72,69,32,25,-45,19] and a hash function h(k) = k mod 1

Question

Given the numbers [5,-12,-72,69,32,25,-45,19] and a hash function h(k) = k mod 13, show the contents of the hash table after insertion of each of the numbers 25 and 19 for (a) separate chaining (b) open addressing with linear probing (c) open addressing with quadratic probing. Hash table size is 13. Insertions are carried out as in the given sequence.

For the final hash tables in parts (a)-(c) above, compute the expected time for a successful lookup and unsuccessful lookup. Count a cost of 1 for computation of the hash function.

Explanation / Answer

a ) Hash table (Separate Chaining)

0
1
2
3 - -45
4 - 69
5 - 5
6 - 32->19
7 - (-72)
8
9
10
11
12 - -12 ->25

a ) Hash table (linear probing)

0 - 25
1
2  
3 - -45
4 - 69
5 - 5
6 - 32
7 - (-72)
8 - 19
9
10
11
12 - -12

a ) Hash table (Quadratic probing)

0 - 25
1
2  
3 - -45
4 - 69
5 - 5
6 - 32
7 - (-72)
8
9
10 - 19
11
12 - -12

Expected time for successful lookup - in sepatate chaining it O(1).There
is no case of unsuccessful lookup

Expected time for successful/Unsuccessful lookup will be O(n) as we need
to consider each index in linear/quadratic probing for successful as well
as unsuccessful look up.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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