Python sets and dicts are not O(1)

Daniel Lemire's September 2026 post takes the belief that Python's dict and set are constant-time and breaks it two different ways. The first is adversarial and makes the textbook bound fail. The second needs no adversary at all and is the more useful one.

Collisions on purpose

A hash table assumes collisions are rare. Picking keys carefully makes them universal:

M = (1 << 61) - 1
values = [i * M for i in range(1, n + 1)]
s = set(values)                       # insertions
count = sum(v in s for v in values)   # checks

The post does not spell out why this constant works. The reason is that CPython hashes integers modulo the Mersenne prime 2^61 - 1 on 64-bit builds, so every multiple of M hashes to zero and all n keys land in the same probe sequence. Unlike strings, integers are not covered by hash randomization, so this collision set is the same on every run.

On an Apple M4 Max with Python 3.14, median of three runs, building the set took 4.8 ms at n = 1,000, 15.5 ms at 2,000, 65.5 ms at 4,000, 257 ms at 8,000 and 1,072 ms at 16,000. Each doubling roughly quadruples the time. Membership checks follow the same curve (1,066 ms at 16,000), and at 100,000 elements construction takes 45 seconds.

No collisions, still not constant

The second experiment builds a dict from a million random sixteen-character strings to integers and looks every key up in shuffled order. Lemire compares it against fastconstmap, an immutable map for keys known in advance, queried in bulk with get_many_into, which writes values into a caller-owned array("Q") so no Python object is allocated per key.

The comparison is tilted toward the dict. The probe strings are the same objects used to build it, and a Python string caches its hash after the first computation, so the dict pays nothing for hashing while fastconstmap rehashes every key.

The dict gets nine times slower per key between the smallest and largest map, with no change in algorithm and no unusual collisions. Lemire's accounting is memory: the keys, their string objects and their integer objects cost about 116 bytes per entry, so at a million entries lookups miss the cache. fastconstmap needs about 9 bytes per key and stays in cache much longer.

The point

O(1) is a model of a hash table, and the machine underneath has a memory hierarchy the model leaves out. A table that fits in CPU cache is fast; one that spills into RAM is slower; one that spills to disk is slower again. No hash table can be truly constant-time for that reason alone. Lemire's warning is less about Python than about how a useful teaching model turns into a belief that survives contrary evidence.

The same gap between the model and the memory shows up in golang-maps-swiss-tables, where Golang's map rewrite is a locality argument first and an algorithm change second, and where 30% microbenchmark wins shrink to 1.5% once cache behaviour in real programs dominates. golang-green-tea-gc shows how easy it is to measure that kind of effect at the wrong cache level, and false-sharing-alignment-128 is the concurrent version of the same lesson: performance lives in where the bytes land.