NIST

separate chaining

(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

Implementation

insert (C), search (C).

More information

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.


Go to the Dictionary of Algorithms and Data Structures home page.

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