7 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 7d 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 7d 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 7d agoCPython has the unfortunate property that ints aren’t covered by hash randomization, and `hash(x) == x % ((1 << 61) - 1)` always.
- progval 6d agoOuch, that's a big footgun. Why was the lack of randomization considered a vulnerability, but not this?