考虑对抗性输入将积分插入 Python dict() 的最坏情况时间复杂度

Question

我们都知道在哈希集中插入一些东西的时间复杂度平均O(1)。然而，我关注的是最坏的行为。我的意思是，一定存在一个特定的整键序列，当元素连续插入时，它会引发许多哈希冲突，这是"最坏情况"。我指的是。

更具体:

• 在字典中插入键值对的最坏情况复杂度是多少?相对于字典中现有项的数量N ?
• 对应的对抗性输入是什么?

这是我到目前为止的工作

from time import time
from math import log2

dummy = {}
elapsed = float('inf')
for k in range(20, 38):
tic = time()
dummy[1<<(1<<k)] = k
elapsed, last = time() - tic, elapsed
print(f"{k=}, {elapsed=:.4f}, {elapsed/last=:.4f}")

上面的对抗性输入显然导致了O(N^2)的时间复杂度…或者是O(N²*ln(N))我不知道。

k=20, elapsed=0.0002, elapsed/last=0.0000
k=21, elapsed=0.0004, elapsed/last=2.1508
k=22, elapsed=0.0007, elapsed/last=1.8340
k=23, elapsed=0.0013, elapsed/last=1.7360
k=24, elapsed=0.0024, elapsed/last=1.9031
k=25, elapsed=0.0048, elapsed/last=1.9879
k=26, elapsed=0.0086, elapsed/last=1.8034
k=27, elapsed=0.0182, elapsed/last=2.1088
k=28, elapsed=0.0361, elapsed/last=1.9787
k=29, elapsed=0.0730, elapsed/last=2.0242
k=30, elapsed=0.1419, elapsed/last=1.9442
k=31, elapsed=0.2844, elapsed/last=2.0040
k=32, elapsed=0.5733, elapsed/last=2.0154
k=33, elapsed=1.1388, elapsed/last=1.9865
k=34, elapsed=3.5476, elapsed/last=3.1152
k=35, elapsed=8.3034, elapsed/last=2.3405
k=36, elapsed=16.0347, elapsed/last=1.9311
k=37, elapsed=35.1934, elapsed/last=2.1948

Answer 1

最坏情况下，字典插入需要O(n)个元素比较，其中n是表中已占用条目的数量。此外，单个插入可能需要重新构建哈希表，这可能涉及每个元素再次与其他元素碰撞，并进行O(n^2)个元素比较。

哈希冲突并不是导致测试速度变慢的原因——你的测试把所有的时间都花在构建和哈希大得荒谬的整数上。例如，1<<(1<<33)是一整gb的整数。

构造对抗性输入相当容易。例如,

In [4]: for i in range(20): 
...:     print(hash(i*(2**61-1))) 
...:                                                                                                                                                                                                                          
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

你可以取2**61-1的倍数