6 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 7d 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 7d 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 7d 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).
Good4boothee 6d 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 7d ago

taeric 7d 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 7d 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).

Good4boothee 6d 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.