3 ms·

So why is it quadratic? Hashing 1<<61-1 should be a constant factor slower than hashing 1. I know you asked an AI later and it told you about hash collisions b

• zahlman 2mo ago
  > I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI? That was two different people. The first comment probably comes from finding the 1<<61-1 constant suspicious, running a micro-benchmark, and then not thinking about it too hard.
• amiga386 2mo ago
  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.