当键很长时获取值的时间复杂度

Question

假设字典的键很长，长度在M左右，M是一个很大的数。

那么在M方面是不是意味着像

这样的操作的时间复杂度

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

是 O(M)？不是 O(1)?

它是如何工作的？

Answer 1

如果您谈论的是具有 M 个字符的字符串键，是的，它可以是 O(M)，并且在两个方面：

计算哈希码可能需要 O(M) 时间。
如果传入的键的哈希码与 table 中的键的哈希码匹配，则实现必须继续计算它们是否相等（__eq__() returns)。如果它们相等，则需要恰好 M+1 次比较来确定（每个字符对 M，并在开始时进行另一次比较以验证（整数）字符串长度是否相同）。

在极少数情况下，它可以是恒定时间的（与字符串长度无关）：那些传入的键是与 [=40 中的键相同的对象=].例如，在

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

计时，并与时间进行比较，例如，在结束前添加此行：

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

此更改构建了另一个键等于到原始 k，但不是同一个对象。因此内部指针相等性测试没有成功，需要进行全面的逐字符比较。

Time Complexity of getting value when key is very long