저는 파이썬의 해시 함수를 가지고 놀았습니다 . 작은 정수의 경우 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.h
64 비트 머신의 경우 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.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에 해당됩니다.
답변
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;
}