I wrote the first comment, thinking it's bignums, but no, it is hash collisions. It's quadratic because that's what hash collisions mean for a closed hash. The

I wrote the first comment, thinking it's bignums, but no, it is hash collisions. It's quadratic because that's what hash collisions mean for a closed hash. The worst cast scenario is that every item has the same hash value, thus goes in the same bucket, so to insert 40,000 unique items, you have to check against 0, 1, 2, 3, ... 40,000 existing items in a linear list (800,000,000 equality tests) to avoid inserting duplicates. To then do an inclusion test for all those items, you have to scan the list 40,000 times, stopping at element 0, 1, 2, ... 40,000, so another 800,000,000 equality tests. It turns out that Python's hash value for integers is the integer itself, modulo (1<<62)-1, which is why he makes all his values multiples of that number, so they're all unique integers with the same hash value. Other than this very narrow case (or more likely creating unique objects whose __hash__ method deliberately/accidentally returns the same value), you'd find it hard to make this situation happen in normal code.