30 points) Let A = {9,11, 10, 5,4), show the hash tables (with the size m = 5) f

Question

30 points) Let A = {9,11, 10, 5,4), show the hash tables (with the size m = 5) for these 5 2. (15 × 2 numbers: 1. For chaining hash table, use the hash function h(z) = z mod 5. 2. For open addressing hash table, use the hash function h(, i)(xi*h'(x)) mod 5, where h'(x)-1+x mod 3). The variablei counts the number of trials from 0 to m-1. 3. (15 x 2 30 points) Following Problem 2, we continue to input another 5 numbers 21,1, 15, 32, 13) and double the sizes of the hash tables (since 10 is not a prime number, we update m to be 11). Please show the new hash tables: 1. For chaining hash table, use the hash function h(x)- r mod 11. 2. For open addressing hash table, use the hash function h(,i) (xi*h'x)) mod 11, where h'(x)-1+(x mod 3). The variable i counts the number of trials from 0 to m-1. 4. (20 points) In Problem 2 & 3, we set h'(x)-1+x mod 3) for open addressing hash table. Can we simply set h'(x)-x mod 3 instead? Why?

Explanation / Answer

No we can not use h'(x) = x mod 3 as this will retunr 0 for number divisible by 3 and hence turning h(x, i) into h(x) which is not what we wanted. It is essnetial to always have different h(x, i) function for different x and i

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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