băm nhỏ các tuple khác nhau trong python cho kết quả giống hệt nhau

Question

Tôi đang làm việc với các bộ ma trận nguyên, và tôi nghĩ rằng chúng đại diện cho chúng như các bộ dữ liệu có ý nghĩa, vì chúng có thể băm. Tuy nhiên hàm băm() cho tôi kết quả lạ đối với bộ dữ liệu:

hash(((1, -1, 0), (1, 0, 0), (1, 0, -1))) 

Out[147]: -697649482279922733 

hash(((1, 0, -1), (1, 0, 0), (1, -1, 0))) 

Out[148]: -697649482279922733 

Như bạn có thể thấy, hai bộ khác nhau này có cùng giá trị băm. Lưu ý rằng chúng thực sự khá giống nhau (trao đổi các subtup đầu tiên và cuối cùng), tuy nhiên tôi không thể tìm thấy một ví dụ tối thiểu hơn: ((0,1),(0,0)) và ((0,0),(0,1)) có các giá trị băm khác nhau chẳng hạn.

Bất kỳ đầu mối nào về những gì đang xảy ra? Tôi không thể tin rằng nó chỉ là may mắn vô cùng tồi tệ ... Bây giờ tôi đã tìm thấy nơi mà vấn đề là tôi có thể bỏ qua nó một cách dễ dàng, nhưng tôi nghĩ rằng nó là đáng nói đến ở đây anyway.

Answer 1

Các hash của một tuple được dựa trên băm của nội dung bằng cách sử dụng công thức sau (từ tuplehash() function):

long mult = 1000003L; 
x = 0x345678L; 
p = v->ob_item; 
while (--len >= 0) { 
    y = PyObject_Hash(*p++); 
    if (y == -1) 
     return -1; 
    x = (x^y) * mult; 
    /* the cast might truncate len; that doesn't change hash stability */ 
    mult += (long)(82520L + len + len); 
} 
x += 97531L; 
if (x == -1) 
    x = -2; 
return x; 

Vì nó xảy ra, công thức sản xuất đầu ra chính xác tương tự cho (1, 0, -1) và (1, -1, 0):

>>> hash((1, -1, 0)) 
-2528505496374624146 
>>> hash((1, 0, -1)) 
-2528505496374624146 

số nguyên vì băm cho 3 chứa rất 1, 0 và -2:

01.

>>> hash(1) 
1 
>>> hash(0) 
0 
>>> hash(-1) 
-2 

và hoán đổi 0 và -2 không có ảnh hưởng thực tế đến kết quả.

Vì vậy, băm cho 3 bộ chứa không thay đổi giữa hai ví dụ, do đó, băm cuối cùng cũng không thay đổi.

Đây chỉ là trùng hợp ngẫu nhiên, trong thực tế điều này không xảy ra tất cả rằng thường và các bộ từ điển và bộ đã có thể xử lý các xung đột tốt.

Answer 2

Có vẻ kỳ lạ, nhưng không sử dụng hash một trong hai cách: https://docs.python.org/2/library/functions.html#hash

[băm được] sử dụng để nhanh chóng so sánh các phím từ điển trong một tra cứu từ điển.

Nó không thực sự được thực hiện cho mục đích chung băm - từ điển có kiểm tra thêm vượt quá bình đẳng băm đơn giản. Để băm mục đích chung, hãy sử dụng hashlib