logoalt Hacker News

progval • yesterday at 9:17 PM • 2 replies • view on HN

He doesn't. Inputs are:

    M = (1 << 61) - 1
    values = [i * M for i in range(1, n + 1)]
which are effectively random from the hash function's point of view, especially with a randomized seed (the default on current versions).

Replies

minitech • yesterday at 10:22 PM

CPython has the unfortunate property that ints aren’t covered by hash randomization, and `hash(x) == x % ((1 << 61) - 1)` always.

amiga386 • yesterday at 10:10 PM

His inputs are large numbers that don't fit in a standard integer. Bigints. The set inclusion test not only has a hash lookup but an equality test, which will be a bigint comparision rather than integer comparison, and bitint comparison is itself O(n) based on the size of the bignum. And the code that tests each bignum is in the set also _sums_ those bignums, which itself is an O(n) operation based on the size of the bignums being summed.

So he's not testing dict/set performance, he's testing bignum performance, because of the inputs he deliberately chose

https://news.ycombinator.com/item?id=49650737