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

Solution:

3)

1)

21 mod 11= 10

1 mod 11= 1,

15 mod 11= 4

32 mod 11= 10, collision so chaining will be done

13 mod 11= 2

2)

at i= 0

h(21, 0)= (21 + 0 * (1+21 mod 3))= 21

h(1, 0)= 1

h(15, 0)= 4

h(32, 0)= 10, collision

now at i= 1

h(32, 1)= 32 + 1 * (32 mod 3) mod 11= 32 + 2= 33 mod 11= 0

h(13, 0)= 2

Please upvote and raise your doubts within the comment.

Hash Key 0 1 1 2 13 3 4 15 5 6 7 8 9 10 21--> 32

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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