Concept: expected O(1) for distributed keys
On average, the hash function distributes keys across buckets so each bucket holds a constant number of entries. Lookup hashes the key and walks the bucket - **O(1)** expected. (Worst case is O(n) when every key collides into one bucket - see the related problem.)