Chaining

  • Differentiate "chaining" collision resolution from "open addressing."

Store all colliding elements in an auxiliary data structure like a linked list.

Each position in the hash table can be seen as a bucket that stores multiple entries. Thus, this approach is sometimes called bucket hashing.

Other names for chaining include "separate chaining" (as in collisions are dealt with using separate data structures), "open hashing," "close addressing" (as opposed to open addressing).

Example
Resources