Hacker News Reader

Comment by robrenaud | Hacker News Reader

The part where he chooses his inputs to hit worst case behavior in Python's hash function.

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).

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

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

Ouch, that's a big footgun. Why was the lack of randomization considered a vulnerability, but not this?

I haven’t looked into the history, but my understanding from the comments is that it exists to preserve `x == y -> hash(x) == hash(y)` for `x` and `y` with different numeric types (int, float, decimal) – which seems like it should be solvable, but isn’t a constraint I’d want to be working under, so I sympathize.

Reply on news.ycombinator.com