[解決済み] Pythonでhash(n) == nとなるのはいつですか？

質問

私はPythonの ハッシュ関数 . 小さな整数の場合、どうやら hash(n) == n と常に表示されます。しかし、これは大きな数には及びません。

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

私は驚きません、私はハッシュが有限の値の範囲を取ることを理解しています。その範囲とは何でしょうか？

私は バイナリサーチ を使って、最小の数 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)] を使って、ハッシュ関数の範囲を推定してみました。最大値は一貫して上記のn以下です。minを比較すると、Python3のハッシュは常に正の値をとるのに対し、Python2のハッシュは負の値をとることができるようです。

どのように解決するのですか？

のpythonドキュメントに基づき pyhash.c ファイルにあります。

数値型の場合、数値 x のハッシュは x の素因数分解に基づくものです。 xの素数に対する P = 2**_PyHASH_BITS - 1 . となるように設計されています。 hash(x) == hash(y) になるように設計されています。 x と y が異なる型を持っていてもです。

つまり、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 ビットマシンでは最大 int は 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