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" 共享相同的哈希值。