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

At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.

Engineering is hard work, not naive math.

[0] Data might be arbitrary but it is never random. Not being random is what makes it data.

Nobody really says that, nor is it a model. It is the expected time complexity.

The O(1) is the expected average case, which usually holds.

Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.

Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.

And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:

> dict

> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.

> ...

> set, frozenset

> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.

  +--------------------------------------+------------+
  | Operation                            | Complexity |
  +--------------------------------------+------------+
  | x in s                               | O(1)       |
  | Copy (s.copy()) [6] [7]              | O(n)       |
  | Add (s.add(x)) [1]                   | O(1)       |
  | Discard (s.discard(x), s.remove(x))  | O(1)       |
  | ...                                  | ...        |
  +--------------------------------------+------------+

The discussion of CPU cache is good though, so why hide that behind this clickbait.