Separate Chaining
Each bucket holds a list of all keys that hash there. Collisions simply grow the list — lookup degrades gracefully (proportional to the load factor α) rather than needing a probe sequence.
- Category
- Hashing
- Time complexity
- O(1 + α)
- Space complexity
- O(n)
Pseudocode
bucket = table[hash(key) % size] bucket.append(key) — on lookup, scan the bucket
Reference implementation
def insert(table, key):
i = hash(key) % len(table)
table[i].append(key) # table[i] is a list