考虑到对抗性输入，将积分插入 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^2*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

Dict 插入在最坏情况下进行 O(n) 次元素比较，其中 n 是 table 中占用的条目数。此外，单个插入可能需要重建散列 table，这可能涉及每个元素再次与其他所有元素发生冲突并进行 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 的倍数。

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

Worst-case time complexity of inserting an integral into Python's dict() considering adversarial input

python

algorithm

hash

dictionary

time-complexity