Definition: A hash table in which a collision is resolved by putting the item in the next empty place in the array following the occupied place. Even with a moderate load factor, primary clustering tends to slow retrieval.
Aggregate parent (I am a part of or used in ...)
linear probing sort.
See also double hashing, quadratic probing.
Note: Deletion may be hard because finding collisions again relies on not creating empty spots. One solution is to mark an entry as deleted so it can be reused for insertion, but the search list is still intact.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 16 November 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "linear probing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/linearprobng.html