Python2 散列值分布不均

Question

当我在字符串上使用 Python 的内置 hash() 函数时，我只是在玩弄它时发现了一些奇怪的东西。通常，正常的哈希函数应该是不相关的，从 hash(A) 开始，hash(B) 应该是完全无法识别的（对于 uncorrelated/unrecognizable 的充分定义）。

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

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

python hash 函数不是加密散列（即不得防止冲突或显示雪崩效应等）；它只是对象的标识符（例如用作字典键）。

阅读文档中有关 __hash__ and hash 的更多信息。

如此处所述：

dict. __hash__() should return an integer. The only required property is that objects which compare equal have the same hash value

并且 - 正如 Jean-François Fabre 在评论中指出的那样 - python 哈希必须很快（即构建字典）。加密哈希很慢，因此无法使用。

顺便说一句：在 python 3 中，分布看起来更加随机。

Answer 2

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

在计算过程中，"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" 中共享相同的散列。

Answer 3

解释可以在Python2.7的Objects/dictobject.c:

的源码注释中找到

Major subtleties ahead: Most hash schemes depend on having a "good" hash function, in the sense of simulating randomness. Python doesn't: its most important hash functions (for strings and ints) are very regular in common cases:
>>> map(hash, (0, 1, 2, 3)) 
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]
This isn't necessarily bad! To the contrary, in a table of size 2**i, taking the low-order i bits as the initial table index is extremely fast, and there are no collisions at all for dicts indexed by a contiguous range of ints. The same is approximately true when keys are "consecutive" strings. So this gives better-than-random behavior in common cases, and that's very desirable.

Python2 散列值分布不均

Python2 hash values badly distributed

python

python-2.7

hash

language-design