What is the time complexity of hash table with chaining?

Average case O(1 + α). Worst case O(n). Space complexity is O(n + m). Every key hashing to one bucket turns the table into a linked list.

Hash table with chaining

medium

A collision is not an error - with more keys than buckets it is unavoidable. Chaining keeps a list per bucket, so lookup costs O(1 + α) where α is the average chain length.

Average O(1 + α)Worst O(n)Space O(n + m)

Loading the hash table with chaining engine…

Where to go next

Open addressing

medium

No chains - probe for the next free slot.

Resizing and rehashing

medium

Why one insert in a thousand costs O(n).

LRU cache

hard

A hash map and a doubly linked list, covering each other's weakness.