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 1², for the second collision probe we add 2², for the third collision probe we add 3², 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 i²

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