Python sets and dictionaries can have quadratic-time performance

0xa2

The map is not the territory.

javcasas

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)).