Python sets and dictionaries can have quadratic-time performance
summary
While Python's set and dict structures are taught as having O(1) constant-time performance, this is a simplified model that fails in reality. Performance can degrade to quadratic time due to hash collisions or become significantly slower as data grows and exceeds CPU cache limits. Understanding the physical reality of memory hierarchy and hash collisions is essential for high-performance software development.
key points
- Hash collisions can be intentionally or accidentally triggered, causing the time to insert or query keys to grow quadratically rather than linearly as the number of elements increases.
- Even without collisions, performance drops as data structures grow because they move from fast CPU caches to slower RAM and eventually to disk, increasing the nanoseconds per key lookup.
- Specialized immutable maps, like the fastconstmap library, can outperform standard dictionaries by reducing the memory footprint per key, keeping more data in the cache for longer.
who should read it
Software engineers and computer science students who want to understand the gap between theoretical big-O complexity and actual hardware performance.
discussion positive
consensus
Commenters generally agree that the observed quadratic performance in Python's sets and dictionaries is a worst-case scenario caused by hash collisions, rather than a general failure of the O(1) model. They argue that such behavior is rare in practice unless specifically engineered for a hash-DoS attack or triggered by using Mersenne primes as keys. The sentiment is largely analytical, with many users emphasizing that O(1) refers to expected average or amortized time complexity rather than a guaranteed absolute.
top insight
The performance degradation is specifically linked to the fact that CPython's integer hashing does not use randomization and follows the formula `hash(x) == x % ((1 << 61) - 1)`. When keys are multiples of this Mersenne prime, every entry collides in the same hash bucket, transforming the hash table into a linked list with O(n) lookup time. This explains why the performance is fine for other large integers that aren't multiples of that specific prime.
Generated by an LLM from the article and thread. Check the sources before relying on it.