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.