1 Define a simple hash function on strings c c1c2cn to be h

1. Define a simple hash function on strings c = c1c2...cn to be h(key) = mod 10 where the position in the alphabet is a = 1, b = 2... So h(\'\'cat\'\') = (3 + 1 + 20) mod 10 = 4. a) If we try to populate the table in the following key order, using linear searching in case of collisions, what will the final table look like? (\'\'hat\'\', \'\'sat\'\', \'\'rat\'\', \'\'cat\'\', \'\'mat\'\', \'\'bat\'\') b) Suppose we wanted to speed computation by using a hash function that only used the index of the first character in a key, rather than summing all indices in the key. Would this affect the rate of collisions? Why?

Solution

h(hat) = (8+1+20) mod 10 = 9

h(sat) = (19+1+20) mod 10 = 0

h(rat) = (18+1+20) mod 10 = 9

h(cat) = (3+1+20)mod 10 = 4

h(mat) = (13+1+20) mod 10 = 4

h(bat) = (2+1+20) mod 10 = 3

________________________________________________________

when only first character is used so we get

h(hat) = (8) mod 10 = 8

h(sat) = (19) mod 10 = 9

h(rat) = (18) mod 10 = 8

h(cat) = (3)mod 10 = 3

h(mat) = (13) mod 10 = 3

h(bat) = (2) mod 10 = 2

here we get 2 collosions.

this will surely effect rate of collosion.suppose i take sat,sbt,sct,sdt.

then i got 4 collisions.but if i used sum of all the keys then i get no collosions.