12 points | by ibobev a day ago ago
3 comments
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)).
The map is not the territory.
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)).
The map is not the territory.