Hashing Questions Long
Quadratic probing is a collision resolution technique used in hashing to resolve collisions that occur when two or more keys are mapped to the same hash index. 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 searches for the next available slot by incrementing the index using a quadratic function. The quadratic function is typically of the form f(i) = i^2, where i represents the number of collisions.
To illustrate the process, let's assume we have a hash table with a fixed size of N and a hash function that maps keys to indices in the range of 0 to N-1. When a collision occurs at index h, the algorithm starts probing for the next available slot by incrementing the index using the quadratic function.
The probing sequence can be represented as follows:
1. h
2. h + 1^2
3. h + 2^2
4. h + 3^2
5. h + 4^2
6. h + 5^2
...
n. h + (n-1)^2
The algorithm continues this probing sequence until an empty slot is found or the entire hash table is traversed. If an empty slot is found, the key is inserted at that index. If the entire hash table is traversed without finding an empty slot, it means that the hash table is full and the key cannot be inserted.
When searching for a key using quadratic probing, the same probing sequence is followed until either the key is found or an empty slot is encountered. If an empty slot is encountered, it means that the key does not exist in the hash table.
Quadratic probing has some advantages over linear probing. It reduces primary clustering, which occurs when keys that hash to the same index tend to cluster together. Additionally, quadratic probing provides better distribution of keys and reduces the likelihood of long probe sequences.
However, quadratic probing also has some limitations. One major limitation is the possibility of secondary clustering, where keys that hash to different indices may still collide due to the quadratic function. This can lead to decreased performance and increased probe sequences.
In conclusion, quadratic probing is a collision resolution technique in hashing that uses a quadratic function to increment the index when collisions occur. It helps reduce primary clustering and provides better distribution of keys, but it may suffer from secondary clustering.