3 ms·
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 vie
by progval 16d ago
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).
- amiga386 16d agoHis 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 https://news.ycombinator.com/item?id=49650737
- minitech 16d agoCPython has the unfortunate property that ints aren’t covered by hash randomization, and `hash(x) == x % ((1 << 61) - 1)` always.
- progval 16d agoOuch, that's a big footgun. Why was the lack of randomization considered a vulnerability, but not this?
- minitech 6d agoI 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.