(data structure)
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.)
direct chaining.
Aggregate parent (I am a part of or used in ...)
hash table.
Aggregate child (... is a part of or used in me.)
linked list.
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]
Author: PEB
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 Black.
Entry modified 3 November 2010.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "separate chaining", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 3 November 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/separateChaining.html