0
639views
Quadratic Probing 28 55 71 67 11 10 90 44
0
6views

Quadratic Probing: 28 55 71 67 11 10 90 44

Let h(k) = k mod m, m = 10, lets take $c_1 \ = \ 1 \ and \ c_2 \ = \ 3$

Initially the hash table can be given as: We have, $h(k,i) \ = \ (h(k) \ + \ c_1 \ i \ + \ c_2 \ i \ 2)$ mod m

Step 1: Key = 28

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

Since T 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 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 is occupied , consider i = 1

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

Since T is occupied , consider i = 2

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

Since T is occupied , consider i = 3

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

Since T is occupied , consider i = 4

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

Since T 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 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 is occupied , consider i = 1

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

Since T 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 is vacant, insert key 44 at this location. 