Consider a hash table of size 7 with hash function hk k mod

Consider a hash table of size 7 with hash function h(k) = k mod 7. Draw the hash table after inserting in it, in the given order, the following values into the table: 14, 28, 2, 26, and 70: when linear probing is used to resolve collisions when double hashing with secondary hash function h\'(k) = 5 - (k mod 5) is used to resolve collisions.

Solution

a)

h(k) = k mod 7
key = 14
h(14) = 14 %7 = 0 ( 14 will go to location 0)

key =28
h(28) = 28 % 7 = 0 (Collision so with linear probing 28 will go to next free loc i:e 1)

key = 2
h(2) = 2% 7 = 2 (2 will go to slot 2)

key =26
h(26) = 26 % 7 = 5 (26 will go to slot 5)

key = 70
h(70) = 70%7 = 0 (Collision so 70 will goto next free slot which is 3)

b) h\'(k) = 5- (kmod5)

h(k) = k mod 7
key = 14
h(14) = 14 %7 = 0 (14 will go to location 0)

key =28
h(28) = 28 % 7 = 0 (Collision )

h\'(28) = 5-(28%5) = 2 (2 positions from 0 i:e 2)

key = 2
h(2) = 2% 7 = 2 (collision)
h\'(2) = 5-(2%5) = 3 (3 positions from 2 i:e 5)

key =26
h(26) = 26 % 7 = 5 (collision)
h\'(26) = 5-(26 % 5) = 4 (4 positions from 5 i:e 2,6,)

key = 70
h(70) = 70%7 = 0 (Collision )
h\'(70) = 5-(70 % 5) = 5 (5 positions from 0 i:e 5,3)

14

28

2

70

26