Hacker News Reader

Comment by juancn | Hacker News Reader

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.

View on HN

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

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

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.

Reply on news.ycombinator.com