Python 中的 hash(n) == n 是什么时候？

Question

我一直在玩 Python 的 hash function。对于小整数，它总是出现 hash(n) == n。但是，这不会扩展到大量：

>>> hash(2**100) == 2**100
False

我并不感到惊讶，我知道哈希采用有限的运行ge 值。那是什么运行ge？

我尝试使用 binary search 找到最小的数字 hash(n) != n

>>> import codejamhelpers # pip install codejamhelpers
>>> help(codejamhelpers.binary_search)
Help on function binary_search in module codejamhelpers.binary_search:

binary_search(f, t)
    Given an increasing function :math:`f`, find the greatest non-negative integer :math:`n` such that :math:`f(n) \le t`. If :math:`f(n) > t` for all :math:`n \ge 0`, return None.

>>> f = lambda n: int(hash(n) != n)
>>> n = codejamhelpers.binary_search(f, 0)
>>> hash(n)
2305843009213693950
>>> hash(n+1)
0

2305843009213693951有什么特别之处？我注意到它小于 sys.maxsize == 9223372036854775807

编辑：我正在使用 Python 3。我运行在 Python 2 上进行了相同的二进制搜索，得到了不同的结果 2147483648，我注意到它是 sys.maxint+1

我还玩过 [hash(random.random()) for i in range(10**6)] 来估计散列函数的运行ge。最大值始终低于上面的 n。比较min，似乎Python 3的哈希总是正值，而Python 2的哈希可以取负值。

Answer 1

implementation for the int type in cpython can be found here.

它只是 returns 值，除了 -1，比它 returns -2:

static long
int_hash(PyIntObject *v)
{
    /* XXX If this is changed, you also need to change the way
       Python's long, float and complex types are hashed. */
    long x = v -> ob_ival;
    if (x == -1)
        x = -2;
    return x;
}

Answer 2

Hash function returns plain int 表示返回值大于-sys.maxint小于sys.maxint，这意味着如果你将 sys.maxint + x 传递给它结果将是 -sys.maxint + (x - 2).

hash(sys.maxint + 1) == sys.maxint + 1 # False
hash(sys.maxint + 1) == - sys.maxint -1 # True
hash(sys.maxint + sys.maxint) == -sys.maxint + sys.maxint - 2 # True

同时 2**200 是 sys.maxint 的 n 倍 - 我的猜测是散列会超过范围 -sys.maxint..+sys.maxint n 次，直到它停止在普通整数上这个范围，就像上面的代码片段一样..

所以一般来说，对于任何 n <= sys.maxint:

hash(sys.maxint*n) == -sys.maxint*(n%2) +  2*(n%2)*sys.maxint - n/2 - (n + 1)%2 ## True

注意： python 2.

Answer 3

2305843009213693951 是 2^61 - 1。它是适合 64 位的最大梅森素数。

如果您必须通过取值 mod 某个数字来进行散列，那么大的梅森素数是一个不错的选择——它易于计算并确保可能性的均匀分布。（虽然我个人永远不会这样做）

计算浮点数的 modulus 特别方便。它们有一个指数分量，将整数乘以 2^x。由于2^61 = 1 mod 2^61-1，你只需要考虑(exponent) mod 61.

参见：https://en.wikipedia.org/wiki/Mersenne_prime

Answer 4

基于 pyhash.c 文件中的 python 文档：

For numeric types, the hash of a number x is based on the reduction of x modulo the prime P = 2**_PyHASH_BITS - 1. It's designed so that hash(x) == hash(y) whenever x and y are numerically equal, even if x and y have different types.

因此对于 64/32 位机器，减少量为 2 ^_PyHASH_BITS - 1，但是 _PyHASH_BITS 是多少？

您可以在 pyhash.h 头文件中找到它，该文件对于 64 位机器被定义为 61（您可以在 pyconfig.h 文件中阅读更多解释）。

#if SIZEOF_VOID_P >= 8
#  define _PyHASH_BITS 61
#else
#  define _PyHASH_BITS 31
#endif

所以首先它基于您的平台，例如在我的 64 位 Linux 平台中，减少量是 2⁶¹-1，即 2305843009213693951 :

>>> 2**61 - 1
2305843009213693951

您还可以使用 math.frexp 来获取 sys.maxint 的尾数和指数，对于 64 位机器显示最大整数为 2⁶³：

>>> import math
>>> math.frexp(sys.maxint)
(0.5, 64)

你可以通过简单的测试看出区别：

>>> hash(2**62) == 2**62
True
>>> hash(2**63) == 2**63
False

阅读有关 python 哈希算法的完整文档 https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

如评论中所述，您可以使用 sys.hash_info（在 python 3.X 中），这将为您提供用于计算的参数结构序列哈希。

>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>>

除了我在前几行中描述的模数外，您还可以获得 inf 值，如下所示：

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159

Python 中的 hash(n) == n 是什么时候？

When is hash(n) == n in Python?

python

python-2.7

python-3.x

hash

python-internals