Python2 散列值分布不均

Question

当我在字符串上使用 Python 内置的 hash() 函数时，我只是在玩弄它时发现了一些奇怪的东西。通常，一个普通的散列函数应该是不相关的，从某种意义上说，从 hash(A)，hash(B) 应该是完全不可识别的(对于不相关的充分定义/无法识别)。

但是，这个快速的小脚本却显示了其他情况

In [1]: for i in range(15):
...:     print hash('test{0}'.format(i))
...:
-5092793511388848639
-5092793511388848640
-5092793511388848637
-5092793511388848638
-5092793511388848635
-5092793511388848636
-5092793511388848633
-5092793511388848634
-5092793511388848631
-5092793511388848632
5207588497627702649
5207588497627702648
5207588497627702651
5207588497627702650
5207588497627702653

我理解 Python 的 hash() 函数不应该在任何方面都是加密安全的，为此您可以使用 hashlib 库，但为什么testX 的值如此有规律地分布？在我看来，它的碰撞行为可能很差。

Answer 1

哈希是一个接一个地计算的。这就是哈希值如此相似的原因。

在计算过程中，"test0" 和 "test1" 具有完全相同的哈希值，直到 "test"。最后一个字符只有一点点不同。在安全散列中，在任何地方改变一位应该完全改变整个散列(例如，多亏了多次传递)。

您可以通过计算“0test”和“1test”的哈希值来检查此行为:

>>> for i in range(15):
...     print hash('{0}test'.format(i))
... 
-2218321119694330423
-198347807511608008
-8430555520134600289
1589425791872121742
-6642709920510870371
-4622800608552147860
8038463826323963107
2058173137418684322
-8620450647505857711
-6600477335291135136
8795071937164440413
4111679291630235372
-765820399655801141
2550858955145994266
6363120682850473265

这就是您所期望的那种广泛分布，对吧？顺便说一句，Python 3 似乎对字符串有不同的哈希计算。

有关 Python2 字符串哈希的更多信息，请查看 "Python Hash Algorithms" :

class string:
    def __hash__(self):
        if not self:
            return 0 # empty
        value = ord(self[0]) << 7
        for char in self:
            value = c_mul(1000003, value) ^ ord(char)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

顺便说一下，这个问题与 Python 无关。在 Java 中，"Aa" 和 "BB" 共享相同的散列。