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 12 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Paul E. Black, "separate 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/separateChaining.html