Question

[Algorithm Question]

Consider inserting the keys 12, 28, 31, 7, 15, 17, 66, 59, 21, 3, 1 into a hash table of length m = 5 using seperate chaining where h(k) = k mod m. Illustrate the result of inserting these keys.

Answer 1

Keys:  12, 28, 31, 7, 15, 17, 66, 59, 21, 3, 1

Lenght or size of the table m = 5

h(k) = k mod m

We have 5 empty slots in our hash table initially.  We will apply a separate chaining when we have a collision.

Key = 12

12 mod 5 = 2.

Therefore, 12 is inserted at 2

Key = 28

28 mod 5 = 3.

28 is inserted at 3

Key = 31

31 mod 5 = 1.

31 is inserted at 1

Key = 7

7 mod 5 = 2.

We have a collision. We will create a list at 2

Key = 15

15 mod 5 = 0.

15 is inserted at 0

Key = 17

17 mod 5 = 2.

Therefore, a collision.

Key = 66

66 mod 5 = 1.

Therefore, a collision

Key = 59

59 mod 5 = 4

59 is inserted at 4

key = 21

21 mod 5 = 1. Therefore, collision at 1

Key = 3

3 mod 5 = 3. Therefore, collision at 3

Key = 1

1 mod 5 = 1. Therefore, collision at 1

The final table is

Please don't forget to give a positive rating to the answer. Your rating motivates experts to help other students also. Thank you :)