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 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.