Daniel Lemire takes apart the claim everyone absorbs in a first data structures course: that Python’s dict and set are O(1). His answer has two halves, and the second one is the part that touches normal code.

The first is adversarial. Generate keys as multiples of 2^61 - 1 and they collide in CPython’s hashing scheme, so the hash table degrades toward a linear scan per operation. On an M4 Max with Python 3.14, the runtime roughly quadruples every time n doubles:

  • n=1000: 4.8 ms
  • n=4000: 65.5 ms
  • n=16000: 1072 ms

That is quadratic, measured, with the code published. At 100,000 elements, building the set takes about 45 seconds.

But Lemire’s real point is that no hash table can be truly constant time, because a growing structure requires progressively slower memory — cache, then RAM, then disk. “Saying that a hash table is O(1) is a model. It can be true, maybe even often, but it is not reality.”

He makes that concrete with the most ordinary shape imaginable: a large immutable dict[str, int] built once and queried many times. Nanoseconds per key:

  • dict: 21.8 ns at 1K keys, 48.1 ns at 100K, 201.9 ns at 1M
  • fastconstmap: 4.3 ns, 5.2 ns, 11.8 ns at the same sizes

The dict gets 9x slower with no algorithm change and no collisions. It is purely memory layout — roughly 116 bytes per key for a million int keys plus their string and integer objects, versus about 9 bytes per key for the packed representation, which stays cache-resident. Notably, Lemire handicaps his own preferred library in the benchmark: he reuses the same string objects so their cached hashes are free, while fastconstmap re-hashes every key on every call.

The takeaway is epistemic rather than algorithmic. Models are useful teaching tools, and the O(1) model installs a bias that survives even after you read the paragraph telling you it is false — “even though you have read my paragraph that says that the dict data structure gets slower, you may not believe it.”