alt Hacker NewsJava'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)).
Replies
aw1621107 • today at 4:59 PM
> Java's HashMap also has O(log(N)) complexity on hash collision
Only for keys that implement Comparable.
One get can O(1) expected time on any set of keys if one uses "universal hashing": choosing the hash function at random from a universal set of hash functions. The expectation is now over this random choice, not over some random distribution of key inputs. So even if an adversary gets to choose the keys the expected behavior is good.
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.