Python dicts and sets can hit quadratic time: the O(1) assumption breaks down
lemire · x · 2026-09-04
Daniel Lemire publishes an article examining the widely believed claim that Python's dict and set are strictly O(1) for insertions and lookups — and shows why it doesn't hold.
Starting from hash functions (random-like mappings from objects to integers) and bucket arrays, he explains how adversarial or degenerate inputs cause collisions to pile up, degrading operations to quadratic time. The takeaway: O(1) is an average-case expectation, not a hard guarantee, and understanding hashing behavior is key to avoiding the trap.
More from coding & agent
- 700+ x402-Paid API Endpoints Go Live, Letting Agents Pay Per Search Call With a Wallet — PolarBearby · 2026-09-04
- Screenshot and layout of the Claude-built MMORPG dragon lair dungeon in Blender — majidmanzarpour · 2026-09-04
- Dev uses Claude + Blender to build an MMORPG dragon lair dungeon, rendered in three.js — majidmanzarpour · 2026-09-04
- Queue vs Pub/Sub: one message, one consumer vs one message, every subscriber — _jaydeepkarale · 2026-09-04
- Open-source KeibiDrop adds MCP so agents can work on remote datasets as if local — Secret-Employer282 · 2026-09-04
- Google AI Pro at $5/mo vs GPT Plus vs OpenCode Go: a coder's comparison — Old-Dish-7104 · 2026-09-04