21–30 of 67 posts
> 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.
> 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.
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.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
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)).
https://en.wikipedia.org/wiki/Universal_hashing
For hashing with chaining, the hash function just has to make the hash values of keys pairwise independent to achieve O(1) expected time per operation; higher order independence is not needed.
Which statement in this article applies only to Python?
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.
Next, he will teach us doubles have finite precision.