Suppose that a hash table contains hash_size = 13 entries indexed from 0 through
ID: 3911654 • Letter: S
Question
Suppose that a hash table contains hash_size = 13 entries indexed from 0 through 12 and that the following keys are to be mapped into the table:
10 100 32 45 58 126 400
(a) Assume that the hash table uses “key % hash_size” as the hash function and that linear probing is used, present the content of the hash table using the following table. Also answer how many collisions occur when these keys are inserted into the table. (10 pts)
0
1
2
3
4
5
6
7
8
9
10
11
12
(b) Assume that the hash table uses “key % hash_size” as the hash function and that quadratic probing is used, present the content of the hash table using the following table. Also answer how many collisions occur when these keys are inserted into the table. (10 pts)
0
1
2
3
4
5
6
7
8
9
10
11
12
(c) Assume that the hash table uses “(sum of all digits of the key) % hash_size” as the hash function and that quadratic probing is used, present the content of the hash table using the following table. Also answer how many collisions occur when these keys are inserted into the table. (10 pts)
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
Explanation / Answer
Solution:
We need to insert
10 100 32 45 58 126 400
hash_size = 13
(a) In linear probing we insert an element at index value returned by hash function. If that index is already filled we insert in next empty slot.
Total collisions = 6
(b) In Qudratic probing we insert an element at index value returned by hash function. If that index is already filled we insert in (hash(x) + i*i) % 13 where i=1,2,3,...
Total collisions = 6
(c)
Total collisions = 2
32 45 58 100 10 126 400 0 1 2 3 4 5 6 7 8 9 10 11 12Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.