NIST

open addressing

(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, LCFS 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, LCFS 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, or keeping one special overflow area have no clustering in the usual sense.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 September 2015.
HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "open addressing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/openAddressing.html