2. (15 x 2 = 30 points) Let A = {9,11,10, 5,4), show the hash tables (with the s

Question

2. (15 x 2 = 30 points) Let A = {9,11,10, 5,4), show the hash tables (with the size m-5) for these 5 numbers 1. For chaining hash table, use the hash functionh)mod 5. 2. For open addressing hash table, use the hash function h(r, i-(x'h'(x)) mod5, where h'(x)-1+(x mod 3). The variable i counts the number of trials from0 to m- 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 (z) = z mod 11. 2. For open addressing hash table, use the hash function h(r, i-(x''(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

2. For A={9,11,10,5,4}

Let T be the array representing hash table

1. For chaining hash table, array T will link to list of entries associated with each location

using h(x)= x mod 5

h(9) = 9 mod 5 = 4 , thus T[4] link to 9

h(11)= 11 mod 5 = 1, thus T[1] link to 11

h(10)= 10 mod 5 = 0, thus T[0] link to 10

h(5) = 5 mod 5 = 0, T[0] already contains 10, so further link from 10 to 5 will be added. Thus T[0] link to 10,5

h(4) = 4 mod 5= 4, Since T[4] contains 9, so further link from 9 to 4 will be added. Thus T[4] link to 9,4

T[0] = {10,5}

T[1] = {11}

T[2] = {}

T[3] = {}

T[4] = {9,4}

2. For open addressing hash table, for h(x,i), where i counts the number of trials, for the first entry at any location, i =0

using h(x,i)=(x+i*h'(x))mod 5 and h'(x)=1+(x mod 3)

h(9,0)=(9+0*h'(9))mod 5 = 9 mod 5 =4, T[4]=9

h(11,0)=(11+0*h'(11))mod 5= 11 mod 5 = 1, T[1]=11

h(10,0)=(10+0*h'(10))mod 5 = 10 mod 5= 0, T[0]=10

h(5,0)=(5+0*h'(5))mod 5= 0, since T[0] is already occupied, so i=1, h(5,1)=(5+h'(5))mod 5= (5+(1+5 mod 3))mod 5= 8 mod 5=3

So, T[3]=5

h(4,0)=(4+0*h'(4))mod 5= 4 mod 5=4, since T[4] already contains 9, so h(4,1)=(4+1*h'(4))mod 5= (4+(1+4 mod 3))mod 5 =6 mod 5=1

T[1] also contain 11, so h(4,2)=(4+2*h'(4))mod 5 = (4+2*2)mod 5

= 3, T[3] is already occupied, so h(4,3)=(4+3*h'(4))mod 5 = 10 mod 5=0, Since T[0] is occupied, h(4,4)=(4+4*h'(4))mod 5 = 12 mod 5 = 2. T[2] was empty. So T[2]=4

Thus array T={10,11,4,5,9}

3.  

1. Using h(x)=x mod 11, new array to add is {21,1,15,32,13}

h(21)= 21 mod 11=10. Since 10 is not the index range. 10 mod 10 =0 will map to this index. T[0] will link to 10,5,21

h(1)= 1 mod 11=1. T[1] already contain 11, will add new link after 11 to 1. So T[1] will link to 11,1

h(15)= 15 mod 11=4 .T[4] already link to 9 and 4 will additionally link to 15. So T[4] link to 9,4,15

h(32)= 32 mod 11=10 and 10 mod 10=0. So T[0] will link to 10,5,21,32

h(13) = 13 mod 11=2. T[2] will link to 13

T[0] = {10,5,21,32}

T[1] = {11,1}

T[2] = {13}

T[3] = {}

T[4] = {9,4,15}

T[5]= {}

T[6] = {}

T[7] = {}

T[8] ={}

T[9] = {}

2. Using open addressing

h(21,0)=(21+0*h'(21)) mod 11= 10.Index 10 does not exist.

h(21,1)=(21+1*h'(21)) mod 11= 22 mod 11= 0. Since T[0] contain 10

h(21,2)= (21+2*h'(21)) mod 11= 23 mod 11=1. Since T[1] contain 11

h(21,3)=(21+3*h'(21)) mod 11= 24 mod 11=2. T[2] contain 4

h(21,4)= 25 mod 11=3. T[3] contain 5

h(21,5) = 26 mod 11= 4. T[4] contain 9

h(21,6) = 27 mod 11= 5. So T[5]=21

h(1,0)=(1+0*h'(1))mod 11=1 Since T[1] contains 11.

h(1,1)=(1+1*h'(1))mod 11=3 Since T[3] contains 5

h(1,2)=(1+2*h'(1))mod 11=5. T[5] contains 21

h(1,3) = 7 mod 11 = 7. T[7]=1

h(15,0)=(15+0*h'(15))mod 11= 4. Since T[4] contain 9 So

h(15,1)=(15+1*h'(15))mod 11= 16 mod 11 =5. Since T[5] contains 21 So

h(15,2)=(15+2*h'(15))mod 11= 6. T[6]=15

h(32,0) = 32 mod 11= 10 and index 10 does not exist

Since h'(32) = 1+32 mod 3 = 3. So index will increment by 3 each time from index 0.

h(32,1)= 35 mod 11 =2. h(32,2)= 38 mod 11= 5. h(32,3)= 41 mod 11= 8. So T[8]=32

h(13,0)= 13 mod 11= 2. h'(13)=2. So index will increment by 2 starting from index 2.

h(13,1) = 4, h(13,2)= 6, h(13,3) = 8, h(13,4)= 10, h(13,5)=1, h(13,6)=3,h(13,7)=5

h(13,8)=7,h(13,9)=9. So T[9]=13

So T={10,11,4,5,9,21,15,1,32,13}

4. No we can not put h'(x)= x mod 3, because if x is divisible by 3 then we will not be able to increment h(x,i) by incrementing i on collision.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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