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 Black.
Entry modified 12 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "coalesced chaining", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/coalescedChaining.html