2 ms·
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/Ha
by javcasas 25d ago
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.html 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 23d agoExpected
- marcosdumay 23d agoNowadays I expected an opaque dictionary to be amortized O(1). Granted, one can technically call that O(log(n)), but that's not a helpful categorization.
- emil-lp 23d agoYou cannot guarantee that from a hash map since an adversary who knows the hash function (unless it's cryptographic) could game the data structure to their advantage.
- aw1621107 23d ago> Java's HashMap also has O(log(N)) complexity on hash collision Only for keys that implement Comparable.
- pfdietz 23d agoOne 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 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.