Time Complexity of getting value when key is very long

Question

Let's assume that keys of dictionary are very long, and their length is around M where M is a very large number.

Then does it mean in terms of M, the time complexity of operations like

 x=dic[key]
 print(dic[key])

is O(M)? not O(1)?

How does it work?

Answer 1

If you're talking about string keys with M characters, yes, it can be O(M), and on two counts:

1. Computing the hash code can take O(M) time.
2. If the hash code of the key passed in matches the hash code of a key in the table, then the implementation has to go on to compute whether they're equal (what __eq__() returns). If they are equal, that requires exactly M+1 comparisons to determine (M for each character pair, and another compare at the start to verify that the (integer) string lengths are the same).

In rare cases it can be constant-time (independent of string length): those where the passed-in key is the same object as a key in the table. For example, in

k = "a" * 10000000
d = {k : 1}
print(k in d)

Time it, and compare to when, e.g., adding this line before the end:

k = k[:-1] + "a"

The change builds another key equal to the original k, but is not the same object. So an internal pointer-equality test doesn't succeed, and a full-blown character-by-character comparison is needed.