Quadratic Probing

In quadratic probing, unlike in linear probing where the strides are constant size, the strides are increments form a quadratic series ($1^2, 2^2, 3^2, \dots$). Thus, the next value of index is calculated as:

int index = getIndex(key);
// if table[index] is occupied, then
for(int i = 0; i < M; i++) { 
  index = (getIndex(key) + i * i) % M; 
  // stop the loop when table[index] is available!
} 

This probing creates larger and larger gaps in the search sequence and avoids primary clustering.

A potential issue with quadratic probing is that not all positions are examined, so it is possible that an item can't be inserted even when the table is not full.

Secondary clustering effect

If a key is mapped to the same index as another key, the second key's prob sequence will follow the first one's footsteps. If this happens repeatedly (for example, due to a poorly implemented hash function), long chains will still form and cause performance to degrade. The phenomenon is called secondary clustering.