(data structure)
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.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "linear probing", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/linearprobng.html