Definition: A class of collision resolution schemes in which all items are stored within the hash table. In case of collision, other positions are computed, giving a probe sequence, and checked until an empty position is found. Some ways of computing possible new positions are less efficient because of clustering. Typically items never move once put in place, but in Robin Hood hashing and other techniques, previously placed items may move.
Generalization (I am a kind of ...)
collision resolution scheme.
Specialization (... is a kind of me.)
Probe sequences: linear probing, quadratic probing, double hashing, uniform hashing Placement techniques: Robin Hood hashing.
Aggregate parent (I am a part of or used in ...)
Aggregate child (... is a part of or used in me.)
See also chaining, coalesced chaining, expandable hashing, perfect hashing.
After [CLR90, page 232]. Chaining, the use of external data structures to resolve collisions, has no clustering in the usual sense.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 3 July 2006.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "open addressing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 3 July 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/openAddressing.html