Quadratic Probing Example in Hashing
Quadratic probing is a collision resolution technique used in hash tables. When a collision occurs (i.e., two keys are mapped to the same slot in the hash table), quadratic probing searches for the next available slot by adding a quadratic function of the probe number to the hash value of the key. The function used is typically of the form f(i) = i^2.
Here's how quadratic probing works:
- When a key needs to be inserted into the hash table, its hash value is calculated using a hash function. The hash function determines the slot in the hash table where the key will be inserted.
- If the slot is empty, the key is inserted into that slot.
- If the slot is already occupied, quadratic probing is used to find the next available slot.
- To find the next slot, the hash value is incremented by a quadratic function of the probe number. The quadratic function used is typically of the form f(i) = i^2. So the next slot to be probed is (hash_value + f(i)) % table_size, where i is the probe number (starting from 1).
- If the next slot is empty, the key is inserted into that slot.
- If the next slot is occupied, the process is repeated by incrementing the probe number and calculating the next slot to be probed.
- The process continues until an empty slot is found, or until the maximum number of probes (usually the table size) has been reached.
Quadratic probing has the advantage of spreading out keys that would otherwise collide into different slots in the hash table. However, it can suffer from clustering, where keys tend to be grouped together, making the probing process more inefficient. To address this, other techniques like linear probing and double hashing are also used in practice.
Here's an example of how quadratic probing works:
Suppose we have a hash table of size 10, and we want to insert the following keys: 25, 36, 14, 5, 18, 7. Now, we will use a hash function that takes the modulo of the key with the table size.
Initially, the hash table is empty:
| | | | | | | | | | |
We'll start by inserting the key 25. The hash function gives us a hash value of 5 (25 % 10), so we'll insert the key in the 5th slot:
| | | | | |25| | | | |
Next, we insert the key 36. The hash function gives us a hash value of 6 (36 % 10), but slot 6 is already occupied. We'll use quadratic probing to find the next available slot. We start by adding 1^2 to the hash value, giving us 7. Since slot 7 is empty, we insert the key in that slot:
| | | | | |25|36| | | |
Next, we insert the key 14. The hash function gives us a hash value of 4 (14 % 10), but slot 4 is already occupied. We use quadratic probing again, adding 1^2 to the hash value to get 5. But slot 5 is also occupied, so we add 2^2 to the hash value to get 8. Slot 8 is empty, so we insert the key there:
| | | | |14|25|36| | | 8|
Next, we insert the key 5. The hash function gives us a hash value of 5 (5 % 10), but slot 5 is already occupied. We use quadratic probing again, adding 1^2 to the hash value to get 6. Slot 6 is occupied, so we add 2^2 to the hash value to get 9. Slot 9 is empty, so we insert the key there:
| | | | |14|25|36| | 5| 8|
Next, we insert the key 18. The hash function gives us a hash value of 8 (18 % 10), but slot 8 is already occupied. We use quadratic probing again, adding 1^2 to the hash value to get 9. Slot 9 is already occupied, so we add 2^2 to the hash value to get 2 (modulo 10). Slot 2 is empty, so we insert the key there:
| | |18| |14|25|36| | 5| 8|
Finally, we insert the key 7. The hash function gives us a hash value of 7 (7 % 10), but slot 7 is already occupied. We use quadratic probing again, adding 1^2 to the hash value to get 8. Slot 8 is already occupied, so we add 2^2 to the hash value to get 1 (modulo 10). Slot 1 is empty, so we insert the key there:
| 7| 1|18| |14|