Searching Algorithms Questions Medium
Quadratic probing is a technique used in hashing to resolve collisions that occur when two or more elements are mapped to the same index in a hash table. It is a variation of linear probing, where instead of incrementing the index by a fixed amount, the index is incremented by a quadratic function of the number of collisions.
In quadratic probing, when a collision occurs, the algorithm calculates a new index by adding the square of an incrementing variable (usually starting from 1) to the original hash index. This incrementing variable is commonly referred to as the probe sequence.
The formula to calculate the new index in quadratic probing is:
newIndex = (originalIndex + (probeSequence^2)) % tableSize
If the new index is already occupied, another collision has occurred, and the process is repeated by incrementing the probe sequence and recalculating the new index until an empty slot is found or the entire hash table is traversed.
Quadratic probing has the advantage of reducing primary clustering, a phenomenon where consecutive collisions tend to form clusters and increase the average search time. By using a quadratic function to calculate the new index, the algorithm spreads out the elements more evenly across the hash table, reducing the likelihood of clustering.
However, quadratic probing can still suffer from secondary clustering, where elements that initially collided continue to collide with other elements, forming new clusters. This can lead to decreased performance if the hash table becomes densely populated.
In summary, quadratic probing is a collision resolution technique that uses a quadratic function to calculate new indices when collisions occur in a hash table. It helps reduce primary clustering but may still be susceptible to secondary clustering.