(data structure)
Definition: A scheme in which linked lists within the hash table handle collisions. An item that collides is put in the next empty place in the array and added to the end of a list embedded in the array items. Any open addressing method to compute possible new positions may be used to find the "next" empty place.
Generalization (I am a kind of ...)
chaining, collision resolution scheme.
Aggregate parent (I am a part of or used in ...)
hash table.
See also separate chaining, open addressing.
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 leave the search list intact.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 12:23:27 2004.
HTML page formatted Wed Oct 26 09:47:20 2005.
Cite this as:
Paul E. Black, "coalesced chaining", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/coalescdhash.html
