Draw the 11-entry hash table that results from using the hash function, h(i)=(3i

Question

Draw the 11-entry hash table that results from using the hash function, h(i)=(3i+5) mode 11, to hash the ksys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by linear probing, this is what I got, not sure if it is correct:

h(12) = (3*12+5) mod 11 = (36+5) mod 11 = 41 mod 11 = 8

h(44) = (3*44+5) mod 11 = (132+5) mod 11 = 137 mod 11 = 5

h(13) = (3*13+5) mod 11 = (39+5) mod 11 = 44 mod 11 = 0

h(88) =(3*88+5) mod 11 = (264+5) mod 11 = 269 mod 11 = 5

h(23)=(3*23+5) mod 11 = (69+5) mod 11 = 74 mod 11 = 8

h(94)=(3*94+5) mod 11 = (282+5) mod 11 = 287 mod 11 = 1

h(11)=(3*11+5) mod 11 = (33+5) mod 11 = 38 mod 11 = 5

h(39)=(3*39+5) mod 11 = (117+5) mod 11 = 122 mod 11 = 1

h(20)=(3*20+5) mod 11 = (60+5) mod 11 = 65 mod 11 = 10

h(16)=(3*16+5) mod 11 = (48+5) mod 11 = 53 mod 11 = 9

h(5) =(3*5+5) mod 11 = (15+5) mod 11 = 20 mod 11 = 9

0 -> 13

1 -> 94   

2 -> 39

3 -> 5

4 -> 20

5 -> 44

6 -> 88

7 ->11

8 -> 12

9 -> 23

10 -> 16

Explanation / Answer

The indexes of the array are:

And the given hash function is: H(i) = (3*i + 5) % 11.

H(12) = 8. Now place 12 at index 8.

H(44) = 5. Now place 44 at index 5.

H(13) = 0. Now place 13 at index 0.

H(88) = 5. As position 5 is already filled, there is a collision. Now check with position 6. Its empty, so insert 88 at index 6.

H(23) = 8. As position 8 is already filled, there is a collision. Now check with postion 0. This is also filled, and there is another collision. Now check with position 1. Its empty, so insert 23 at index 1.

H(94) = 1. As position 1 is already filled, there is a collision. Now check with position 2. Its empty, so insert 94 at index 2.

H(11) = 5. As position 5 is already filled, there is a collision. Now check with position 6. This is also filled, and there is another collision. Now check with position 7. Its empty, so insert 11 at index 7.

H(39) = 1. As position 1 is already filled, there is a collision. Now check with position 2. This is also filled, and there is another collision. Now check with position 3. Its empty, so insert 39 at index 3.

H(20) = 10. Now place 20 at index 10.

H(16) = 9. Now place 16 at index 9.

H(5) = 9. As position 9 is already filled, there is a collision. Now check with position 10. This is also filled, and there is another collision. Now check with position 0. This is also filled, and there is another collision. Now check with position 1. This is also filled, and there is another collision. Now check with position 2. This is also filled, and there is another collision. Now check with position 3. This is also filled, and there is another collision. Now check with position 4. Its empty, so insert 5 at index 4.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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