파이썬에서 hash (n) == n은 언제입니까?

파이썬에서 hash (n) == n은 언제입니까?

---

저는 파이썬의 해시 함수를 가지고 놀았습니다 . 작은 정수의 경우 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 위보다 낮습니다. 최소값을 비교하면 Python 3의 해시는 항상 양의 값을 갖는 반면 Python 2의 해시는 음의 값을 취할 수 있습니다.

---

pyhash.c파일의 파이썬 문서를 기반으로 :

숫자 형의 경우 숫자 x의 해시는 x modulo the prime 감소를 기반으로합니다 P = 2**_PyHASH_BITS - 1. hash(x) == hash(y)x와 y가 서로 다른 유형을 가지더라도 x와 y가 수치 적으로 동일 할 때마다 설계되었습니다 .

따라서 64/32 비트 머신의 경우 감소는 2 ^_PyHASH_BITS -1이됩니다.하지만 무엇 _PyHASH_BITS입니까?

pyhash.h64 비트 머신의 경우 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

또한 64 비트 시스템의 경우 최대 int가 2 ⁶³ 임을 나타내는 math.frexp가수와 지수를 얻기 위해 사용할 수 있습니다 .sys.maxint

>>> 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

---

2305843009213693951입니다 2^61 - 1. 64 비트에 맞는 가장 큰 메르 센 프라임입니다.

If you have to make a hash just by taking the value mod some number, then a large Mersenne prime is a good choice -- it's easy to compute and ensures an even distribution of possibilities. (Although I personally would never make a hash this way)

It's especially convenient to compute the modulus for floating point numbers. They have an exponential component that multiplies the whole number by 2^x. Since 2^61 = 1 mod 2^61-1, you only need to consider the (exponent) mod 61.

See: https://en.wikipedia.org/wiki/Mersenne_prime

---

Hash function returns plain int that means that returned value is greater than -sys.maxint and lower than sys.maxint, which means if you pass sys.maxint + x to it result would be -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

Meanwhile 2**200 is a n times greater than sys.maxint - my guess is that hash would go over range -sys.maxint..+sys.maxint n times until it stops on plain integer in that range, like in code snippets above..

So generally, for any n <= sys.maxint:

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

Note: this is true for python 2.

---

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

It just returns the value, except for -1, than it 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;
}

참고URL : https://stackoverflow.com/questions/37612524/when-is-hashn-n-in-python