python - 如果使用很长的字符串作为键，在 Dict 中搜索的时间复杂度是多少？

Question

我从 python3 文档中读到，python 使用哈希表来表示 dict()。所以搜索时间复杂度应该是 O(1)，最坏的情况是 O(N)。但是，最近在我参加类(class)时，老师说只有当您使用 int 作为键时才会发生这种情况。如果使用长度为 L 的字符串作为关键字，则搜索时间复杂度为 O(L)。

我写了一段代码来测试他的诚实

import random
import string
from time import time
import matplotlib.pyplot as plt

def randomString(stringLength=10):
    """Generate a random string of fixed length """
    letters = string.ascii_lowercase
    return ''.join(random.choice(letters) for i in range(stringLength))

def test(L):
    #L: int length of keys

    N = 1000 # number of keys
    d = dict()
    for i in range(N):
        d[randomString(L)] = None

    tic = time()
    for key in d.keys():
        d[key]
    toc = time() - tic

    tic = time()
    for key in d.keys():
        pass
    t_idle = time() - tic

    t_total = toc - t_idle
    return t_total

L = [i * 10000 for i in range(5, 15)]
ans = [test(l) for l in L]

plt.figure()
plt.plot(L, ans)
plt.show()

结果非常有趣。如您所见，x 轴是用作键的字符串的长度，y 轴是查询字典中所有 1000 个键的总时间。



谁能解释这个结果？

请对我温柔点。如您所见，如果我问这个基本问题，那意味着我无法阅读 python 源代码或等效复杂的内部文档。

Answer 1

由于字典是一个哈希表，在哈希表中查找键需要计算键的哈希值，那么在字典中查找键的时间复杂度不能小于哈希函数的时间复杂度。

在当前版本的 CPython 中，长度为 L 的字符串需要 O(L) 时间来计算哈希，如果它是您第一次对特定字符串对象进行哈希处理，如果该字符串对象的哈希具有 O(1) 时间已经被计算(因为哈希被存储):

>>> from timeit import timeit
>>> s = 'b' * (10**9) # string of length 1 billion
>>> timeit(lambda: hash(s), number=1)
0.48574538500002973 # half a second
>>> timeit(lambda: hash(s), number=1)
5.301000044255488e-06 # 5 microseconds

所以这也是你在字典中查找键需要多长时间:

>>> s = 'c' * (10**9) # string of length 1 billion
>>> d = dict()
>>> timeit(lambda: s in d, number=1)
0.48521506899999167 # half a second
>>> timeit(lambda: s in d, number=1)
4.491000026973779e-06 # 5 microseconds

您还需要注意，字典中的键不是仅通过其哈希值查找的:当哈希值匹配时，它仍然需要测试您查找的键是否等于字典中使用的键，以防万一哈希匹配是误报。在最坏的情况下，测试字符串的相等性需要 O(L) 时间:

>>> s1 = 'a'*(10**9)
>>> s2 = 'a'*(10**9)
>>> timeit(lambda: s1 == s2, number=1)
0.2006020820001595

所以对于长度为 L 的键和长度为 n 的字典:

如果字典中不存在键，并且它的散列已经被缓存，那么确认它不存在平均需要 O(1) 时间。

如果键不存在并且它的散列没有被缓存，那么由于计算散列平均需要 O(L) 时间。

如果 key 存在，则需要 O(L) 平均时间来确认它是否存在，是否需要计算散列，因为相等性测试。

最坏的情况总是 O(nL)，因为如果每个散列都发生冲突并且字符串除了最后一个地方之外都相等，那么慢的相等性测试必须进行 n 次。