Hashing Questions
Quadratic probing is a collision resolution technique used in open addressing hashing. It involves finding the next available slot in the hash table by incrementing the hash index using a quadratic function.
When a collision occurs and the initial hash index is occupied, quadratic probing calculates a new index by adding the square of an incrementing offset to the initial index. This process continues until an empty slot is found or the entire hash table is traversed.
The quadratic function used for probing is typically of the form:
new_index = (initial_index + c1 * i + c2 * i^2) % table_size
Here, i represents the number of probing attempts, c1 and c2 are constants, and table_size is the size of the hash table.
Quadratic probing helps to distribute the keys more evenly in the hash table and reduces clustering, which can occur with linear probing. However, it may still suffer from clustering when the table is nearly full.