Dict

Python dict/set operations can degrade to O(n) time under crafted hash collisions

A technical analysis by Valentin Ignatev, discussed by a Python performance blogger, shows that Python's set and dict data structures, though usually treated as constant-time O(1) for lookups and insertions, can be forced into quadratic-time behavior. By constructing integers that share the same hash value (using a Mersenne prime modulus), it's possible to trigger repeated hash collisions that slow insertion and lookup dramatically as the collection grows.