Linear probing

From Wikipedia, the free encyclopedia

Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions 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 either the entire table is traversed, or until a free space is found. This algorithm, which is used in open-addressed hash tables, provides good memory caching, 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.

Given an ordinary hash function h(k), a linear probing function would be h(k,i) = (h(k) + i)mod m. Here h(k)is the starting value, m the size of the hash table, and the stepsize is i in this case.

[edit] See also

• Double hashing
• Hash collision
• Hash function
• Quadratic probing