Tại sao -1 và -2 cả hai hàm băm -2 trong CPython?

Question

thể trùng lặp:
When is a python object's hash computed and why is the hash of -1 different?

Tại sao -1 và -2 cả băm để cùng một số nếu Python?

Vì chúng thực hiện, Python làm cách nào để phân biệt hai số này?

>>> -1 is -2 
False 
>>> hash(-1) is hash(-2) 
True 
>>> hash(-1) 
-2 
>>> hash(-2) 
-2 

Answer 1

-1 là một giá trị được bảo lưu ở cấp C CPython, giúp ngăn chặn hàm băm từ việc có thể để tạo ra một giá trị hash của -1. Theo ghi nhận của DSM, điều này cũng không đúng trong IronPython và PyPy nơi hash(-1) != hash(-2).

Xem this Quora answer:

Nếu bạn viết một loại trong một mô-đun mở rộng C và cung cấp một phương pháp tp_hash , bạn phải tránh -1 - nếu bạn quay lại -1, Python sẽ giả bạn có nghĩa là để ném một lỗi.

Nếu bạn viết một lớp bằng Python thuần túy và cung cấp phương thức __hash__, không yêu cầu như vậy, thật may mắn. Nhưng đó là vì mã C gọi phương thức __hash__ của bạn cho bạn - nếu __hash__ trả lại -1, sau đó hash() áp dụng cho đối tượng của bạn sẽ thực sự trả về -2.

nào thực sự chỉ repackages thông tin từ effbot:

Các băm giá trị -1 được dành riêng (nó được sử dụng để lỗi cờ trong việc thực hiện C ). Nếu thuật toán băm tạo ra giá trị này, chúng tôi chỉ cần sử dụng -2 thay thế.

Bạn cũng có thể thấy điều này trong nguồn. Ví dụ cho đối tượng int Python 3, đây là vào cuối the hash implementation:

if (x == (Py_uhash_t)-1) 
    x = (Py_uhash_t)-2; 
return (Py_hash_t)x; 

---

Kể từ khi họ làm, như thế nào Python nói với hai con số này ngoài?

Vì tất cả hàm băm ánh xạ không gian đầu vào lớn vào không gian nhập nhỏ hơn, các xung đột luôn được mong đợi, bất kể hàm băm tốt đến mức nào. Hãy nghĩ về các chuỗi băm, ví dụ. Nếu mã băm là các số nguyên 32 bit, bạn có mã băm 2^32 (nhiều hơn 4 tỷ). Nếu bạn xem xét tất cả các chuỗi ASCII có độ dài 6, bạn có (2^7)^6 (chỉ dưới 4,4 nghìn tỷ) các mục khác nhau trong không gian nhập của bạn. Chỉ với bộ này, bạn được đảm bảo có nhiều, nhiều va chạm dù bạn có tốt đến mức nào. Thêm các ký tự Unicode và các chuỗi có độ dài không giới hạn vào đó!

Do đó, mã băm chỉ gợi ý tại vị trí của đối tượng, kiểm tra bình đẳng sau để kiểm tra các khóa ứng cử viên. Để thực hiện kiểm tra thành viên trong tập hợp bảng băm, mã băm cung cấp cho bạn số "thùng" để tìm kiếm giá trị. Tuy nhiên, tất cả các mục đã đặt có cùng mã băm đều nằm trong nhóm. Đối với điều này, bạn cũng cần một bài kiểm tra bình đẳng để phân biệt giữa tất cả các ứng viên trong nhóm.

Mã băm và nhị phân bình đẳng này được gợi ý trong số CPython documentation on hashable objects. Trong các ngôn ngữ/khuôn khổ khác, có một nguyên tắc/quy tắc rằng nếu bạn cung cấp chức năng mã băm tùy chỉnh, bạn cũng phải cung cấp kiểm tra bình đẳng tùy chỉnh (được thực hiện trên cùng các trường như hàm mã băm).

---

Thật vậy, Python phát hành địa chỉ hiện nay chính xác này, với một bản vá bảo mật nhằm giải quyết vấn đề hiệu quả khi điều này (giá trị băm giống nhau, nhưng trên quy mô lớn) được sử dụng như một tấn công từ chối dịch vụ - http://mail.python.org/pipermail/python-list/2012-April/1290792.html