Definition: A scheme in which each position in the hash table has a list to handle collisions. Each position may be just a link to the list (direct chaining) or may be an item and a link, essentially, the head of a list. In the latter, one item is in the table, and other colliding items are in the list.
Also known as external chaining.
Generalization (I am a kind of ...)
chaining, collision resolution scheme.
Specialization (... is a kind of me.)
Aggregate parent (I am a part of or used in ...)
Aggregate child (... is a part of or used in me.)
See also coalesced chaining.
Note: The items in the list may be searched and maintained with any list search algorithms. Any searchable data structure may be used instead of a list.
After [GBY91, pages 74-77]
Francis A. Williams, Handling Identifiers as Internal Symbols in Language Processors, CACM, 2(6):21-24, June 1959. Each location in Williams' table is an item and a list head.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 3 November 2010.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "separate chaining", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 3 November 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/separateChaining.html