(algorithm)
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 ...)
hash table.
Aggregate child (... is a part of or used in me.)
clustering.
See also chaining, coalesced chaining, expandable hashing, perfect hashing.
Note:
After [CLR90, page 232]. Chaining, the use of external data structures to resolve collisions, has no clustering in the usual sense.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 3 July 2006.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "open addressing", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 3 July 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/openAddressing.html