Question: Quadratic Probing 28 55 71 67 11 10 90 44
0

Quadratic Probing: 28 55 71 67 11 10 90 44

Let h(k) = k mod m, m = 10, lets take c1 = 1 & c2 = 3

Initially the hash table can be given as:

We have, h(k,i) = (h(k) + c1 i + c2 i 2) mod m

Step 1: Key = 28

h(28,0) = [28 mod 10 + 1 * 0 + 3 * 0] mod 10 = 8

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

Step 2: Key = 55

h(55,0) = [55 mod 10 + 1 * 0 + 3 * 0] mod 10 = 5

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

Step 3: Key = 71

h(71,0) = [71 mod 10 + 1 * 0 + 3 * 0] mod 10 = 1

Step 4: Key = 67

h(67,0) = [67 mod 10 + 1 * 0 + 3 * 0] mod 10 = 7

Step 5: Key = 11

h(11,0) = [11 mod 10 + 1 * 0 + 3 * 0] mod 10 = 1

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

h(11,1) = [11 mod 10 + 1 * 0 + 3 * 0] mod 10 = 5

Since T[5] is occupied , consider i = 2

h(11,2) = [11 mod 10 + 1 * 2 + 3 * 4] mod 10 = 5

Since T[5] is occupied , consider i = 3

h(11,3) = [11 mod 10 + 1 * 3 + 3 * 9] mod 10 = 1

Since T[1] is occupied , consider i = 4

h(11,4) = [11 mod 10 + 1 * 4 + 3 * 16] mod 10 = 3

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

Step 6: Key = 10

h(10,0) = [10 mod 10 + 1 * 0 + 3 * 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 + 1 * 0 + 3 * 0] mod 10 = 0

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

h(90,1) = [90 mod 10 + 1 * 0 + 3 * 1] mod 10 = 4

Since T[4] is vacant, insert key 90 at this location.

Step 8: Key = 44

All the locations of hash table are occupied for i = 1, 2 and 3, so consider i = 4

h(44,4) = [44 mod 10 + 1 * 4 + 3 * 16] mod 10 = 6

Since T[6] is vacant, insert key 44 at this location.

renu • 17 views