YHK - yet another hacker news clone

Python sets and dictionaries can have quadratic-time performance

28 points ibobev 2 days ago 9 comments

0xa2 1 day ago | parent

The map is not the territory.

javcasas 1 day ago | parent

Java's HashMap also has O(log(N)) complexity on hash collision, and that is before memory/cache details.

https://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)).

emil-lp 36 minutes ago | parent

Expected

aw1621107 13 minutes ago | parent

> Java's HashMap also has O(log(N)) complexity on hash collision

Only for keys that implement Comparable.

brudgers 19 hours ago | parent

But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory.

At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.

Engineering is hard work, not naive math.

[0] Data might be arbitrary but it is never random. Not being random is what makes it data.

emil-lp 34 minutes ago | parent

> To put it differently, saying that a hash table is O(1) or constant time is a model

Nobody really says that, nor is it a model. It is the expected time complexity.

robertlagrant 4 minutes ago | parent

I think people do say a hash table is O(1). It's the average time complexity (for some value of average) though, not the worst case.

juancn 6 minutes ago | parent

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.