1. Suppose that a hash table contains HASHSIZE = 13 entries indexed from 0 throu
ID: 3733971 • Letter: 1
Question
1. Suppose that a hash table contains HASHSIZE = 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, 3, 29, 200, 400, 0 (a) Determine the hash addresses and find how many collisions occur when these keys are reduced modulo 13 (no insertion, just count colliding hash values) (b) Determine the hash addresses and find how many collisions occur when these keys are first folded by adding their digits together (in ordinary decimal notation) and then reducing modulo HASHSIZE,Explanation / Answer
Given hash size is 13.
hash function h(k)=key%13
for example if the key is 10 then h(10)=10%13=10. So 10 is mapped to location 10.
The hash function values for the remaining keys are calculated in the following table.
a)
Key value
10
100
32
45
58
126
3
29
200
400
0
Hash function
h=key%13
10
9
6
6
6
9
3
3
5
10
0
for 45 there is collision , 58 collison, 126 collison, 29, 400 ..So total there are 5 collisons
b) Hash function is given as first folding and adding the decimal numbers in the key and then reducing to modulo 13
for example if key is 32 then first we add 3+2 =5
then 5%13=5
32 is mapped to index number 5 in hash table
given keys are 10,100,32,45,58,126,3,29,200,400,0
hash function h(k)=(bind and fold key)%13
Key value
10
100
32
45
58
126
3
29
200
400
0
h(k)
1
1
5
9
0
9
3
11
2
4
0
for 126 collison, 0, 100 ..So total there are 3 collisons
Key value
10
100
32
45
58
126
3
29
200
400
0
Hash function
h=key%13
10
9
6
6
6
9
3
3
5
10
0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.