Khi nào là băm (n) == n bằng Python?

Question

Tôi đã chơi với số hash function của Python. Đối với các số nguyên nhỏ, nó luôn xuất hiện hash(n) == n. Tuy nhiên, điều này không mở rộng đến số lượng lớn:

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

Tôi không ngạc nhiên, tôi hiểu rằng hàm băm có một phạm vi giá trị hữu hạn. Phạm vi đó là gì?

tôi đã cố gắng sử dụng binary search để tìm số nhỏ nhất 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 

Có gì đặc biệt về 2305843009213693951? Tôi lưu ý đó là ít hơn sys.maxsize == 9223372036854775807

Chỉnh sửa: Tôi đang sử dụng Python 3. Tôi chạy tìm kiếm nhị phân cùng trên Python 2 và nhận được một kết quả khác nhau 2147483648, mà tôi lưu ý là sys.maxint+1

Tôi cũng chơi với để ước tính phạm vi hàm băm. Giá trị tối đa luôn dưới n ở trên. So sánh phút, có vẻ như hàm băm Python 3 luôn được đánh giá tích cực, trong khi băm Python 2 có thể có giá trị âm.

Answer 1

Dựa trên tài liệu python trong pyhash.c file:

Đối với các loại số, các hash của một số x được dựa trên việc giảm của x modulo thủ P = 2**_PyHASH_BITS - 1. Nó được thiết kế sao cho hash(x) == hash(y) bất cứ khi nào x và y có số lượng bằng nhau, ngay cả khi x và y có các loại khác nhau.

Vì vậy, đối với một máy 64/32 bit, giảm sẽ là 2 ^_PyHASH_BITS-1, nhưng là những gì _PyHASH_BITS?

Bạn có thể tìm thấy nó trong pyhash.h tệp tiêu đề cho máy 64 bit đã được định nghĩa là 61 (bạn có thể đọc thêm giải thích trong tệp pyconfig.h).

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

Vì vậy, trước hết tất cả nó dựa trên nền tảng của bạn ví dụ như trong 64bit nền tảng Linux của tôi giảm là 2 -1, đó là 2305843009213693951:

>>> 2**61 - 1 
2305843009213693951 

Ngoài ra Bạn có thể sử dụng math.frexp trong để nhận được phần mềm và số mũ của sys.maxint cho máy tính 64 bit cho thấy rằng tối đa int là 2 :

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

Và bạn có thể thấy sự khác biệt bằng một xét nghiệm đơn giản:

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

Đọc tài liệu đầy đủ về thuật toán băm python https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Như đã đề cập trong bình luận của bạn có thể sử dụng sys.hash_info (trong python 3.x) sẽ cung cấp cho bạn một chuỗi các tham số cấu trúc được sử dụng để tính toán băm .

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

Cùng với mô đun mà tôi đã mô tả trong trước dòng, bạn cũng có thể nhận được giá trị inf như sau:

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

Answer 2

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

Nó chỉ trả về giá trị, trừ -1, hơn nó trả -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 3

chức năng Hash trả đồng bằng int đó có nghĩa là giá trị trả về là lớn hơn -sys.maxint và thấp hơn sys.maxint, có nghĩa là nếu bạn vượt qua sys.maxint + x thì kết quả sẽ là -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 

Trong khi đó 2**200 lớn hơn sys.maxint một n lần - tôi đoán là băm sẽ đi qua phạm vi -sys.maxint..+sys.maxint n lần cho đến khi nó dừng lại trên số nguyên đơn giản trong phạm vi đó, giống như trong đoạn mã trên ..

vì vậy, nói chung, đối với bất kỳ n < = sys.maxint:

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

Lưu ý: điều này đúng với python 2.

Answer 4

2305843009213693951 là 2^61 - 1. Đó là nguyên tố Mersenne lớn nhất phù hợp với 64 bit.

Nếu bạn phải băm chỉ bằng cách lấy giá trị mod một số, thì một nguyên tố Mersenne lớn là một lựa chọn tốt - dễ tính toán và đảm bảo phân phối đồng đều các khả năng. (Mặc dù cá nhân tôi sẽ không bao giờ thực hiện băm theo cách này)

Đặc biệt thuận tiện để tính toán mô đun cho số dấu phẩy động. Chúng có một thành phần theo cấp số mũ nhân số nguyên theo 2^x. Kể từ 2^61 = 1 mod 2^61-1, bạn chỉ cần xem xét (exponent) mod 61.

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