0
639views
Quadratic Probing 28 55 71 67 11 10 90 44
1 Answer
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[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.

Please log in to add an answer.