Define a simple hash function on strings c = c_1c_2...c_n to be h(key) = (n sigm

Question

Define a simple hash function on strings c = c_1c_2...c_n to be h(key) = (n sigma i=1 position in alphabet(C_i) mod 10 where the position in the alphabet is a = l, b = 2.... So h("cat") = (3 + 1 + 20) mod 10 = 4. 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") 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?

Explanation / Answer

Ans;

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.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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