Python Data Structures and Algorithms

Chaining

Chaining is a strategy for resolving conflicts and avoiding the limit to the number of elements in a hash table. In chaining, the slots in the hash table are initialized with empty lists:

When an element is inserted, it will be appended to the list that corresponds to that element's hash value. That is, if you have two elements that both have the hash value 1167, these two elements will both be added to the list that exists in slot 1167 of the hash table:

The preceding diagram shows a list of entries with hash value 51.

Chaining then ...