Question: Linear probing: 28 55 71 67 11 10 90 44
0

Linear Probing: 28 55 71 67 11 10 90 44

( 0 + hck) = k mod m, m = 10.

Initially the hash table can be given as:

we have h (k,i) = (h(k) + i) mod m

Step 1: Key = 28.

h(28, 0) = (28 mod 10 + 0 ) mod 10

= 8 mod 10

= 8

Since T[8] is vacant, insert key 28 at this location.

Step 2: Key = 55

h(55, 0) = (55 mod 10 + 0) mod 10

= 5 mod 10

= 5

Since T[5] is vacant, insert key 55 at this location.

Step 3: Key = 71

h(71, 0) = (71 mod 10 + 0) mod 10

= 1 mod 10 = 1

Since T[1] is vacant, insert key 71 at this location.

Step 4: Key = 67

h(67, 0) = (67 mod 10 + 0) mod 10 = 7

Since T[7] is vacant, insert key 67 at this location.

Step 5: key = 11

h(11, 0) = (11 mod 10 + 0) mod 10 = 1 mod 10 = 1

since T[1] is occupied, consider i = 1

h(11, 1) = (11 mod 10 + 1) mod 10 = 2 mod 10 = 2

Since T[2] is vacant, insert key 11 at this location.

Step 6: Key = 10

h(10, 0) = (10 mod 10 + 0) mod 10 = 0 mod 10 = 0

Since T[0] is vacant, insert key 10 at this location.

Step 7 : Key = 90

h(90, 0) = (90 mod 10 + 0) mod 10 = 0 mod 10 = 0

since T[0] is occupied, consider i = 1

h(90, 1) = (90 mod 10 + 1) mod 10 = 1 mod 10 = 1

since T[1] is occupied, consider i = 2

h(90, 2) = (90 mod 10 + 2) mod 10 = 2 mod 10 = 2

since T[2] is occupied, consider i = 3

h(90, 3) = (90 mod 10 + 3) mod 10 = 3 mod 10 = 3

since T[3] is vacant, insert key 90 at this location.

Step 8 : Key = 44

h(44, 0) = (44 mod 10 + 0) mod 10 = 4 mod 10 = 4

since T[4] is vacant, insert key 44 at this location.

renu • 18 views