Python sets and dictionaries can have quadratic-time performance

    import timeit
    def test(M,n):
        values = [i * M for i in range(1, n + 1)]
        s = set(values)
        sum(v in s for v in values)
    M = (1 ", timeit.timeit(lambda: test(M,n), number=3))
    for n in [1000, 2000, 4000, 8000, 16000]:
        print(f"M=1,      {n=:5d} ->", timeit.timeit(lambda: test(1,n), number=3))

    M=2^61-1, n= 1000 -> 0.13144792200182565
    M=2^61-1, n= 2000 -> 0.48016051898594014
    M=2^61-1, n= 4000 -> 2.058760045998497
    M=2^61-1, n= 8000 -> 7.843778470996767
    M=2^61-1, n=16000 -> 40.01485426299041
    M=1,      n= 1000 -> 0.000748768012272194
    M=1,      n= 2000 -> 0.0015750699967611581
    M=1,      n= 4000 -> 0.003037029004190117
    M=1,      n= 8000 -> 0.006664915999863297
    M=1,      n=16000 -> 0.012693285010755062

It's not super clear from the article that the choice of key was specifically chosen to generate these hash collisions (though it is more evident on a re-read). The article leads one to believe that the likelihood of this collision is common:

> "I can ‘easily’ make my version of Python crumble"

> "To put it differently, saying that a hash table is O(1) or constant time is a model. It can be true, maybe even often, but it is not reality."

It feels very misleading to say that "Python sets and dictionaries can have quadratic-time performance", as though this may be a common occurrence in the wild. Perhaps if this behaviour had been accidentally discovered in the wild, that would make for an interesting anecdote? It feels like the lesson is more accurately put: "hash tables are susceptible to hash collisions".

I guess ultimately I come to a different conclusion than the original blog post. They say: "Some models are useful but none of them is reality. Be mindful of cognitive biases." It reads to me as having an air of "you can't trust anything." I think I would describe this conclusion more like "abstractions are leaky, and it is helpful to have a basic understanding of what's happening under the hood. Even for something as elemental as a dict."

And in that sense, if I were making this point with regards to computer science I might lean on a more common false assumption like "the network is reliable". (Or establish early-on in the article that we're identifying a similar false assumption about dicts.)

Anyway, I think I'm sensitive to articles picking on python.. but perhaps the title was clickbait. Is there another language with a clearly superior approach that python should emulate?