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

Question

我从python3文档中读取，该python将hash表用于dict（）。因此，搜索时间复杂度应为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轴是用作键的字符串的长度，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

您还需要注意，字典中的键不是通过其哈希查找的[[only：当哈希匹配时，它仍然需要测试您查找的键是否等于在字典中使用的键。字典，以防哈希匹配为假阳性。在最坏的情况下，测试字符串的相等性需要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

仅当您使用int作为键时。如果使用长度为L的字符串作为键，则搜索时间复杂度为O（L）

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

为什么人们经常说哈希表的插入，查找或擦除是O（1）操作。

对于哈希表的许多实际应用，无论存储多少个密钥，密钥的典型长度都不会增加。例如，如果您制作了一个哈希集以将姓名存储在电话簿中，则前100个人的平均姓名长度可能非常接近绝对每个人的平均姓名长度。因此，当您拥有一千万个名称时，查找名称所花的时间并不比最初的100个更糟（这种分析通常会忽略CPU缓存大小以及RAM与磁盘速度的性能影响，如果您的程序开始交换）。您可以对程序进行推理而不必考虑名称的长度：插入一百万个名称可能比插入一千个名称花费大约一千倍的时间。

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