> Java's HashMap also has O(log(N)) complexity on hash collision

Only for keys that implement Comparable.