Monday, October 12, 2009

Quadratic Probe

Primary clustering can be eliminated by adding a value other than 1 to the current address. One easily implemented method is to use the quadratic probe. In the quadratic probe, the increment is the collision probe number squared. Thus for the first probe we add 12, for the second collision probe we add 22, for the third collision probe we add 32, and so forth until we either find an empty element or we exhaust the possible elements. To ensure that we don’t run off the end of the address list, we use the modulo of the quadratic sum for the new address. This sequence is shown in Table 1, which for simplicity assumes a collision at location 1 and a list size of 100. From table, we can see quadratic probing causes secondary clustering on a collision resolution path.

Address = H(K)+C i2

Where we take C=1 and i is collision probe number.

No comments:

Post a Comment