"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)."
Lemire's example uses a case where all of the keys hash to the same value:
>>> M = (1 << 61) - 1
>>> [hash(M*i) for i in range(10)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Comments
Yes, the Python documentation at https://docs.python.org/3/library/time-complexity.html#dict describes it:
"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)."
Lemire's example uses a case where all of the keys hash to the same value: