Python中整数哈希映射的哈希洪水攻击

Question

为什么Python还没有修复整数哈希表的哈希洪水攻击问题呢？举个例子，我可以创建一个很长的数字列表，让每个数字和前一个数字发生冲突，这样就会导致哈希表的碰撞，结果是时间复杂度变成了o(n**2)。而对于字符串来说就没这个问题，因为Python使用了“SipHash”算法，这种算法设计得能抵抗哈希洪水攻击。

看看这段代码

import time
m = 2**61 - 1  
n = 10000  
from collections import Counter

collide = [m * i for i in range(1, n + 1)]
s = time.time()
c = Counter(collide)
e = time.time()
print(e-s)

another = [k for k in range(n)]
s = time.time()
c = Counter(another)
e = time.time()
print(e-s)

在这个例子中，碰撞数组的处理时间是1.4420311450958252秒，而正常数组的处理时间只有0.0005929470062255859秒。有没有什么办法可以缓解这个问题，因为Python不允许自定义哈希实现？

Answer 1

好吧，如果你确定自己处理的整数大多属于特殊情况，那么你可以考虑在把它们放进字典之前先进行一些处理。

• 转换成字符串 - 在我的测试中，这个简单的办法能让你速度提升很多。

import time
m = 2**61 - 1
n = 10000
from collections import Counter

collide = [str(m * i) for i in range(1, n + 1)]
s = time.time()
c = Counter(collide)
e = time.time()
print(e-s)

another = [k for k in range(n)]
s = time.time()
c = Counter(another)
e = time.time()
print(e-s)

结果是：

0.0013701915740966797
0.0009481906890869141

• 对整数进行一些简单的变换，然后记得在使用之前再变回来。例如，由于Python的整数哈希函数希望低位有变化，你可以在把整数放进字典之前先做个位旋转，然后在使用时再旋转回来。

这实际上就相当于你自己写了一个哈希函数。我想你可以在这里应用任何逻辑，把整数变成更适合哈希的形式。

比如：

from collections import Counter
import time

m = 2**61 - 1
n = 10000
# This will determine the maximum int you can safely rotate and the speed of your rotation operation
bit_format_string = "{:080b}"
bit_shift = 62


# TODO: Figure out a better way to do rotations
def rotate_left(x, n):
    return int(bit_format_string.format(x)[n:] + bit_format_string.format(x)[:n], 2)


def rotate_right(x, n):
    return int(bit_format_string.format(x)[-n:] + bit_format_string.format(x)[:-n], 2)


collide = [m * i for i in range(1, n + 1)]
shifted = [rotate_right(i, bit_shift) for i in collide]
s = time.time()
c = Counter(shifted)
e = time.time()
print(e-s)

# This restores the original values and gets you your counts
counts = [(rotate_left(k, bit_shift), v) for (k, v) in c.items()]

another = [k for k in range(n)]
s = time.time()
c = Counter(another)
e = time.time()
print(e-s)

这个方法也很快，并且能得到正确的输出。结果是：

0.0010600090026855469
0.0006046295166015625

而且这个测试通过了：assert set(t[0] for t in counts) == set(collide)