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

Question

我从 python3 文档中读到，python 对 dict() 使用散列 table。所以搜索时间复杂度应该是 O(1)，最坏情况是 O(N)。但是，最近在上课时，老师说只有当您使用 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-axis 是用作键的字符串的长度，y-axis 是查询字典中所有 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

您还需要注意字典中的键不是仅通过它的散列查找：当散列匹配时，它仍然需要测试您的键looked up 等于字典中使用的键，以防散列匹配为误报。在最坏的情况下，测试字符串是否相等需要 O(L) 时间：

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

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

如果键不存在于字典中，并且它的散列已经被缓存，那么平均需要 O(1) 时间来确认它不存在。
如果键不存在且其哈希值未被缓存，则计算哈希值平均需要 O(L) 时间。
如果密钥存在，平均需要 O(L) 的时间来确认它存在是否需要计算哈希值，因为相等性测试。
最坏的情况总是 O(nL)，因为如果每个散列都发生冲突并且字符串除最后几处外都相等，则必须进行 n 次慢速相等测试。

Answer 2

only when you use int as the key. If you use a string of length L as keys the search time complexity is O(L)

只是为了解决 kaya3 的答案未涵盖的问题....

为什么人们常说哈希 table 插入、查找或擦除是 O(1) 操作。

对于哈希 table 的许多实际应用程序，无论您存储多少个密钥，密钥的典型长度都不会增加。例如，如果您制作了一个散列集来存储电话簿中的姓名，那么前 100 个人的平均姓名长度可能非常接近所有人的平均姓名长度。出于这个原因，当你有一组一千万个名字时，寻找名字所花费的时间并不比最初的 100 个更糟（这种分析通常忽略 CPU 缓存大小和 RAM 的性能影响vs 磁盘速度，如果你的程序开始交换）。您可以在不考虑名称长度的情况下对程序进行推理：例如插入一百万个名字可能比插入一千个名字花费的时间大约长一千倍。

其他时候，应用程序有一个散列 tables，其中的密钥可能会有很大差异。想象一下一个哈希集，其中的键是二进制数据编码视频：一个数据集是旧的标清 24fps 视频剪辑，而另一个是 8k UHD 60fps 电影。插入这些密钥集所花费的时间不会简单地与此类密钥的数量成比例，因为在密钥散列和比较中涉及大量不同的工作量。在这种情况下——如果您想推断不同大小键的插入时间，没有相关因素的大 O 性能分析将毫无用处。仅考虑正常散列 table 性能特征，您仍然可以描述具有相似大小键的数据集的相对性能。当密钥散列时间可能成为问题时，您可能需要考虑您的应用程序设计是否仍然是一个好主意，或者是否您可以使用一组文件名而不是原始视频数据。

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

What is the time complexity of searching in Dict if very long strings are used as keys?

python

hash

dictionary

hashtable

python-3.x

为什么人们常说哈希 table 插入、查找或擦除是 O(1) 操作。