In separate chaining every cell of the hash table (a bucket) is a list. All keys that land in the same bucket are kept in that list. A collision stops being a problem: the chain just gets longer. Hash functions are familiar from the previous topic.

An array and chains: keys 1, 5, 9 land in the same bucket
An array and chains: keys 1, 5, 9 land in the same bucket

Operations

  • Insert (put): the bucket number is hash(key) % m. If the key is in the chain, update the value, otherwise append.
  • Lookup (get): find the same bucket and walk the chain comparing with ==.
  • Delete (remove): remove the element from the chain.

Comparison uses ==, so the __eq__/__hash__ contract of the keys matters.

Implementation

python
class HashMap:
    def __init__(self, capacity=8):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0

    def _bucket(self, key):
        return self._buckets[hash(key) % len(self._buckets)]