Python2 散列值分布不均
Python2 hash values badly distributed
当我在字符串上使用 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
的值如此有规律地分布?在我看来,它的碰撞行为可能很差。
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 中,分布看起来更加随机。
哈希是一个字符一个字符地计算的。这就是哈希值如此相似的原因。
在计算过程中,"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"
中共享相同的散列。
解释可以在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.
当我在字符串上使用 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
的值如此有规律地分布?在我看来,它的碰撞行为可能很差。
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 中,分布看起来更加随机。
哈希是一个字符一个字符地计算的。这就是哈希值如此相似的原因。
在计算过程中,"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"
中共享相同的散列。
解释可以在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.