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

Program / 글쓴이

저는 파이썬의 해시 함수를 가지고 놀았습니다 . 작은 정수의 경우 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 61 -1입니다 2305843009213693951.

>>> 2**61 - 1
2305843009213693951

또한 64 비트 시스템의 경우 최대 int가 2 63 임을 나타내는 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 비트에 맞는 가장 큰 메르 센 프라임입니다.

값 mod를 가져 와서 해시를 만들어야한다면 큰 Mersenne 소수를 선택하는 것이 좋습니다. 계산이 쉽고 가능성의 균등 한 분포를 보장합니다. (개인적으로는 이런 식으로 해시를 만들지 않지만)

부동 소수점 숫자에 대한 계수를 계산하는 것이 특히 편리합니다. 그들은 정수에를 곱하는 지수 성분을 가지고 있습니다 2^x. 때문에 2^61 = 1 mod 2^61-1, 당신은 단지를 고려할 필요가있다 (exponent) mod 61.

참조 : https://en.wikipedia.org/wiki/Mersenne_prime

답변

해시 함수는 반환 일반 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에 n시간이 더 큽니다 . 위의 코드 스 니펫과 같이 해당 범위의 일반 정수에서 멈출 때까지 sys.maxint해시가 범위 -sys.maxint..+sys.maxintn 번을 넘어가는 것 같습니다.

따라서 일반적으로 n <= sys.maxint의 경우 :

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

참고 : 이것은 python 2에 해당됩니다.

답변

CPython과의 INT 유형에 대한 구현은 여기에서 찾을 수 있습니다.

다음을 반환하는 것보다을 제외한 값 -1을 반환합니다 -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;
}

답변