Hash table (dict and set)

Why it costs this much

The hash function jumps straight to a bucket, so a lookup does not scan other keys. Resizing keeps buckets short, which keeps the expected cost constant.

Code

seen = set()
for x in items:
    if x in seen:       # expected O(1): hash, then check one short bucket
        return True
    seen.add(x)         # expected O(1)
return False            # whole loop: expected O(n)

Python is the baseline example used across the site.

Common pitfalls

Many colliding keys push a bucket toward O(n). Keys must be hashable and immutable. Iteration order and memory overhead differ between languages.

Operation by operation

Hash table lookup, insert, delete. A hash function that spreads keys evenly, and a bounded load factor. Resizing makes one insert O(n), amortized O(1). Adversarial keys can force collisions. Iteration order is not sorted.