Linear Probing

Linear probing is a technique to resolve collisions in hash tables by sequentially searching the hash table for a free location. This is accomplished using two values - one as a starting value and one as an interval between successive values in modular arithmetic. The second value, which is the same for all keys and known as the stepsize, is repeatedly added to the starting value until a free space is found, or the entire table is traversed. (In order to traverse the entire table the stepsize should be relatively prime to the arraysize, which is why the array size is often chosen to be a prime number.)

This algorithm, which is used in open-addressed hash tables, provides good memory caching (if stepsize is equal to one), through good locality of reference, but also results in clustering, an unfortunately high probability that where there has been one collision there will be more. The performance of linear probing is also more sensitive to input distribution when compared to double hashing, where the stepsize is determined by another hash function applied to the value instead of a fixed stepsize as in linear probing. Given an ordinary hash function H(x), a linear probing function (H(x, i)) would be:

bsimage

Here H(x) is the starting value, n the size of the hash table, and the stepsize is i in this case. Wikipedia (opens new window)

Collided and deleted buckets are marked purple, they need to be included in the collision path newLocation = (startingValue + stepSize) % arraySize