In fact, some studying on data structures probably leads to the conclusion that it is impossible to guarantee that an unbounded set/map to have access performance under O(log(N)).
You cannot guarantee that from a hash map since an adversary who knows the hash function (unless it's cryptographic) could game the data structure to their advantage.
One get can O(1) expected time on any set of keys if one uses "universal hashing": choosing the hash function at random from a universal set of hash functions. The expectation is now over this random choice, not over some random distribution of key inputs. So even if an adversary gets to choose the keys the expected behavior is good.
I think the point is that once it becomes a crypto key, stock price, weather observation, whatever, the datum ceases to be random and becomes arbitrary.
O(1) insertion is the amortized worst-case time complexity, actually. (Amortized in the sense that the O(n) cost of copying is paid only during the n-th insertion). Average complexity is a slightly different thing.
It is not “worst-case” (as the post demonstrates, you can get worse results by using specifically crafted data that exploits hash collisions). There are algorithms that can get you O(logN) instead of O(N) even on such data.
People … say that all the time. *I* say that all the time. It’s true enough to be accurate in 99.9% of the cases; and we put barriers in place when implementing code (like configuring the hashing algorithm) to keep it that way.
That's usually true of all common hash table implementations (when objects don't have a defined order, if they have you can get O(1) average and O(log N) worst case), regardless of language.
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
I used to think of it more as O(1) being the expected average of the cases. My guess is I'm probably thinking of it more as an amortized cost, in that framing? (That is, not that it is the average case. Is the average of all cases.)
To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.
It is both amortized and average, because the map may need to grow. But the complexity without growing is average, not amortized (it's possible to build hash functions for which the probability will mean O(1) for all accesses, and hash functions which will be O(N) for all accesses).
> but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
That "rarely" contains most sites/webservices. Before programming languages started defending against it by applying randomization (and sometimes replacing degraded maps/buckets with treemaps) it was a real threat. I remember people were able to trigger DoS either by specially crafted query string params or HTTP headers. After all both are shoved into some kind of map by frameworks, before request is even passed to application code.
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
This "quadratic-time performance" is incredibly disingenuous. First, it's doing n operations that are each O(n), so it's more like "can have linear time performance, but done n times so I can give you a scary title".
Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.
And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:
> dict
> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.
> ...
> set, frozenset
> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.
The discussion of CPU cache is good though, so why hide that behind this clickbait.
Time complexity is something that applies to algorithms, and is determined analytically. I don't think it's useful to equivocate the definition with performance of implementations of algorithms determined through real world data. Both of these things are important, but they are not the same. The fact that they differ is not very surprising and does not necessarily mean that a misunderstanding has occurred.
That is why I like to use __slots__ when defining a class. Unlike dicts, using __slots__ is a tuple so using it to store class attributes is much faster.
Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?
Part of the secret explained elsewhere on this HN post is that the OP is selecting values that all collide. Most hash tables handle collisions with linked lists that would be linear insert. It's O(1) average case but O(n) if you pull an "oops all collisions on the same bucket" stunt.
Raymond Hettinger has a great talk about how much python's dict has improved over the years. So this is super interesting and will probably just make the builtin dict better eventually.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
Most algorithm analyses don't incorporate memory hierarchies. I'm not sure what the point of this post was.
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
Because complexity models that involve memory hierarchy are an active research area and are super complex. Also, "plain" complexity is still useful: despite the constant factor, at large N (and this is sometimes a real possibility) the complexity will still win. For example, despite binary search being less cache-friendly (it can be made more with some tricks but not the same), it still defeats linear search most of the time.
O(1) doesn't mean constant, it means bounded by a constant. An algorithm can be faster with small n and converge to a horizontal asymptote as n goes to infinity, and it would still be O(1).
In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.
I'm surprised that even a CS professor confuses this.
[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.
>Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why?
>>You may, yes.
Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"
It's true you can. Just as you can say that you can enumerate all memory states in a real computer it can be modelled as a finite state machine. These asymptotic models aren't real (our world as we experience it is finite and bounded) and exist as models from which to gain insights which we can transfer back. I love this argument BTW a classic that usually comes up in these discussions.
import timeit
def test(M,n):
values = [i * M for i in range(1, n + 1)]
s = set(values)
return sum(v in s for v in values)
M = (1 << 61) - 1
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=2^61-1, {n=:5d} ->", 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))
Magically, when you stop using BIGINTS as the set members and just use regular ints, there is no such quadratic explosion.
The runtime is being spent hashing bigints, comparing candidate bigint(s) against reference bigints, and summing bigints. And there's also some set lookups.
Actually, as the Google AI just taught me [1], the bad performance results from hash _collisions_, not from using bigints (which the author also mentions):
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 << 61) - 1 # This is a bigint and also a Mersenne prime number
N = (1 << 61) + 42 # This is a bigint, but not a Mersenne prime number
# This runs slow
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"M=2^61-1, {n=:5d} ->", timeit.timeit(lambda: test(M,n), number=3))
# This runs with normal performance
for n in [1000, 2000, 4000, 8000, 16000]:
print(f"N=2^61+42, {n=:5d} ->", timeit.timeit(lambda: test(N,n), number=3))
(1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers. When multiplying numbers with this prime number, hash collisions become common, and this slows down the performance.
This is not completely theoretical; hash-DoS attacks make use of that. For this reason, there is hash salting since Python 3.3 for strings, bytes, and datetime objects [2], but not for integers, because the most common attack surface is JSON, but JSON keys are strings, and hash salting would slow down the performance of math operations.
> (1 << 61) - 1 is a Mersenne prime number, which Python uses internally on 64-bit systems for the hash algorithm for big integers.
So this hinges on a contrived set of integer keys, which python's hashing algorithm is susceptible to?
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?
I wrote the first comment, thinking it's bignums, but no, it is hash collisions.
It's quadratic because that's what hash collisions mean for a closed hash. The worst cast scenario is that every item has the same hash value, thus goes in the same bucket, so to insert 40,000 unique items, you have to check against 0, 1, 2, 3, ... 40,000 existing items in a linear list (800,000,000 equality tests) to avoid inserting duplicates. To then do an inclusion test for all those items, you have to scan the list 40,000 times, stopping at element 0, 1, 2, ... 40,000, so another 800,000,000 equality tests.
It turns out that Python's hash value for integers is the integer itself, modulo (1<<62)-1, which is why he makes all his values multiples of that number, so they're all unique integers with the same hash value. Other than this very narrow case (or more likely creating unique objects whose __hash__ method deliberately/accidentally returns the same value), you'd find it hard to make this situation happen in normal code.
65 comments
[ 3.7 ms ] story [ 26.3 ms ] threadhttps://docs.oracle.com/javase/8/docs/api/java/util/HashMap....
In fact, some studying on data structures probably leads to the conclusion that it is impossible to guarantee that an unbounded set/map to have access performance under O(log(N)).
Granted, one can technically call that O(log(n)), but that's not a helpful categorization.
Only for keys that implement Comparable.
https://en.wikipedia.org/wiki/Universal_hashing
Counterexamples: crypto keys, stock price history, weather observations, radio telescope recordings
Nobody really says that, nor is it a model. It is the expected time complexity.
It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.
That "rarely" contains most sites/webservices. Before programming languages started defending against it by applying randomization (and sometimes replacing degraded maps/buckets with treemaps) it was a real threat. I remember people were able to trigger DoS either by specially crafted query string params or HTTP headers. After all both are shoved into some kind of map by frameworks, before request is even passed to application code.
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
Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.
And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:
> dict
> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.
> ...
> set, frozenset
> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.
You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.The discussion of CPU cache is good though, so why hide that behind this clickbait.
Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?
`values = [str(i * M) for i in range(1, n + 1)]`
or
`values = [i * M % 1_000_000_000_000_000 for i in range(1, n + 1)]`
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
https://www.youtube.com/watch?v=npw4s1QTmPg
Def worth a watch as he is funny but also super cool to see someone use a REPL this way:
https://www.youtube.com/watch?v=lyDLAutA88s
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
By a constant factor no less (until we get into theoretical physics)
Next, he will teach us doubles have finite precision.
In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.
I'm surprised that even a CS professor confuses this.
[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.
Also hashmaps (python Dicts) have amortized O(1) and not O(1) big-O.
>Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why?
>>You may, yes.
Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"
>
Mmmmm. Yep. There's yer trouble.
This is not completely theoretical; hash-DoS attacks make use of that. For this reason, there is hash salting since Python 3.3 for strings, bytes, and datetime objects [2], but not for integers, because the most common attack surface is JSON, but JSON keys are strings, and hash salting would slow down the performance of math operations.
[1] https://share.google/aimode/cXQyw0SDPr5FnhBc5, available for seven days
[2] See the grey info box here: https://docs.python.org/3/reference/datamodel.html#object.__...
So this hinges on a contrived set of integer keys, which python's hashing algorithm is susceptible to?
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?
I know you asked an AI later and it told you about hash collisions but I'm wondering where this first comment came from. Was it also AI?
That was two different people.
The first comment probably comes from finding the 1<<61-1 constant suspicious, running a micro-benchmark, and then not thinking about it too hard.
It's quadratic because that's what hash collisions mean for a closed hash. The worst cast scenario is that every item has the same hash value, thus goes in the same bucket, so to insert 40,000 unique items, you have to check against 0, 1, 2, 3, ... 40,000 existing items in a linear list (800,000,000 equality tests) to avoid inserting duplicates. To then do an inclusion test for all those items, you have to scan the list 40,000 times, stopping at element 0, 1, 2, ... 40,000, so another 800,000,000 equality tests.
It turns out that Python's hash value for integers is the integer itself, modulo (1<<62)-1, which is why he makes all his values multiples of that number, so they're all unique integers with the same hash value. Other than this very narrow case (or more likely creating unique objects whose __hash__ method deliberately/accidentally returns the same value), you'd find it hard to make this situation happen in normal code.
https://news.ycombinator.com/item?id=49553744