What is the difference between linear probing and quadratic probing?

The main difference between linear probing and quadratic probing is the way they handle collisions in a hash table.

In linear probing, when a collision occurs (i.e., when the desired hash index is already occupied), the algorithm checks the next available index in a linear manner until an empty slot is found. This means that the probing sequence is a simple linear progression, such as index + 1, index + 2, index + 3, and so on. Linear probing has the advantage of simplicity and easy implementation, but it can lead to clustering, where consecutive elements are placed in close proximity, causing longer search times.

On the other hand, quadratic probing uses a quadratic function to determine the next probing index after a collision. The probing sequence follows a quadratic progression, such as index + 1, index + 4, index + 9, and so on. This helps to reduce clustering and distribute the elements more evenly throughout the hash table. However, quadratic probing can still suffer from clustering, especially when the hash table is nearly full.

Overall, the main difference between linear probing and quadratic probing lies in the way they calculate the next probing index after a collision, with linear probing using a linear progression and quadratic probing using a quadratic progression.