Solved

# Quadratic Probing

Posted on 2006-11-17

I'm trying to implement quadratic probing to resolve hash table collisions. Usually I use a linked-list method, but I want to try out quadratic probing.

My basic "get" function uses a loop like:

for (unsigned n = 1; table_space[idx] != EMPTY; ++n) {

if (memcmp( table_space[idx].key, key, strlen(key)) == 0)

return table_space[idx].value;

idx += ( (n+1)*(n+1) ) - (n*n);

if (idx >= Capacity) idx %= Capacity;

}

I'm not sure if I'm implementing the quadratic function properly. If the idx value exceeds the capacity of the table, I reset it to the beginning of the table with a modulo/assignment. However, I've seen some implementations which use the hash value itself for the quadratic function, rather than the table index. Is there any difference, and is the above implementation adequate?