number of slots in hash table = 7 (from 0 to 6)
hash function is h(k)=((10k+4)mod c) mod 7
we want no collision hence hash function should point us to unique slots of hash table for each key
we know that if we do mod 7 then result will be between (0,1,2,3,4,5,6)
first necessary condition for no collision is that for each key (10k+4) mod c should give unique result so we want 7 unique result and it is only possible if c>6 because if c=6 then we will get only 6 unique result(0,1,2,3,4,5)but we want seven unique results as we have 7 keys who wants 7 unique slots.
assume
H=(10k+4) mod c
so our final hash function is h(k)= H mod 7
so take c = 7 and firstly do find H for each key(k)
if for each key it is unique then only go and do mod 7 which is outside
i used gate calculator to do that
so i did for c=7 but not got unique slots for each key
so i tried one by one for c= 8,9,10,11,12 but i got some duplicate slots in each c value till now,
now when i did with c=13 i got all unique slots
then i did final mod 7 and got that if c=13 then all keys went to different slots and hence no collision.
so our hash function must be
h(k)=((10k+4)mod 13) mod 7 in order to avoid any collision while inserting given keys in hash table.
hence using this hash function finally our hash table is :
Hash Table
Index |
keys |
0 |
36 |
1 |
92 |
2 |
33 |
3 |
61 |
4 |
52 |
5 |
56 |
6 |
47 |