3 ms·

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

by juancn 16d ago

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.

taeric 16d ago
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.
- afdbcreid 16d ago
  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).
  - taeric 12d ago
    Amortized is a bit different, though? It largely implies that there is a heavy cost periodically. Average just implies that it varies. Which, fair that "massive cost periodically" is compatible with that. Just seems to have a very different context, to me. With hashtables, it was more that it was not guaranteed to be the minimal cost. Just, depending on statistics of the data that you feed to it, it shouldn't be the worst case.
Good4boothee 15d ago
> 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.

by juancn 16d ago

taeric 16d ago

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.

afdbcreid 16d ago
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).
- taeric 12d ago
  Amortized is a bit different, though? It largely implies that there is a heavy cost periodically. Average just implies that it varies. Which, fair that "massive cost periodically" is compatible with that. Just seems to have a very different context, to me. With hashtables, it was more that it was not guaranteed to be the minimal cost. Just, depending on statistics of the data that you feed to it, it shouldn't be the worst case.

Good4boothee 15d ago

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