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 ...)
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 leaves the search list intact.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 16 November 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "coalesced chaining", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/coalescedChaining.html