Mặc định __hash__ trong python là gì?

Question

Tôi thường sử dụng các công cụ thú vị làm chìa khóa cho từ điển, và do đó, tôi tự hỏi làm cách nào để làm điều đó - và điều này thực hiện các phương pháp băm tốt cho các đối tượng của tôi. Tôi biết các câu hỏi khác được hỏi ở đây như good way to implement hash, nhưng tôi muốn hiểu cách hoạt động của các đối tượng tùy chỉnh mặc định __hash__ và nếu có thể dựa vào nó.

tôi đã nhận thấy rằng mutables là explicitely unhashable từ hash({}) đặt ra một lỗi ... nhưng kỳ lạ, các lớp học tùy chỉnh hashable:

>>> class Object(object): pass 
>>> o = Object() 
>>> hash(o) 

Vì vậy, không ai biết cách hàm băm mặc định này làm việc? Bằng cách hiểu điều này, tôi muốn biết:

Tôi có thể dựa vào băm mặc định này không, nếu tôi đặt các đối tượng cùng loại với các khóa của từ điển? ví dụ. :

key1 = MyObject() 
key2 = MyObject() 
key3 = MyObject() 
{key1: 1, key2: 'blabla', key3: 456} 

Tôi có thể dựa vào nó nếu tôi sử dụng các loại đối tượng khác nhau làm khóa trong từ điển không? ví dụ.

{int: 123, MyObject(10): 'bla', 'plo': 890} 

Và trong trường hợp cuối cùng, làm cách nào để đảm bảo rằng băm tùy chỉnh của tôi không xung đột với băm dựng sẵn? ví dụ:

{int: 123, MyObject(10): 'bla', MyObjectWithCustomHash(123): 890} 

Answer 1

Những gì bạn có thể dựa vào: các đối tượng tùy chỉnh có mặc định là hash() dựa trên nhận dạng của đối tượng. tức là bất kỳ đối tượng nào sử dụng giá trị băm mặc định sẽ có giá trị không đổi cho băm đó trong suốt thời gian tồn tại của nó và các đối tượng khác nhau có thể hoặc không có giá trị băm khác.

Bạn không thể dựa vào bất kỳ mối quan hệ cụ thể nào giữa giá trị được trả lại bởi id() và giá trị được trả về bởi hash(). Trong triển khai C chuẩn của Python 2.6 và trước đó chúng giống nhau, trong Python 2.7-3.2 hash(x)==id(x)/16.

Chỉnh sửa: ban đầu tôi đã viết trong phiên bản 3.2.3 trở lên hoặc 2.7.3 hoặc cao hơn giá trị băm có thể được ngẫu nhiên và trong Python 3.3 mối quan hệ sẽ luôn được ngẫu nhiên. Trên thực tế, sự ngẫu nhiên hiện tại chỉ áp dụng cho các chuỗi băm nên trên thực tế, chia cho 16 mối quan hệ có thể tiếp tục giữ cho bây giờ, nhưng không phải là ngân hàng trên nó.

Va chạm băm không thường là vấn đề: trong tra cứu từ điển để tìm đối tượng, nó phải có cùng giá trị băm và cũng phải so sánh bằng nhau.Va chạm chỉ quan trọng nếu bạn nhận được một tỷ lệ va chạm rất cao như trong cuộc tấn công từ chối dịch vụ dẫn đến các phiên bản gần đây của Python có thể ngẫu nhiên tính toán băm.

Answer 2

>>> class C(object): 
...  pass 
... 
>>> c = C() 
>>> hash(c) == id(c) 
True 

Xem chức năng id

Answer 3

Các documentation trạng thái mà đối tượng tùy chỉnh dựa vào id() như hash() thực hiện của họ:

CPython chi tiết thực hiện: Đây là địa chỉ của đối tượng trong trí nhớ.

Nếu bạn kết hợp đối tượng tùy chỉnh với các loại dựng sẵn như int của họ có thể va chạm băm, nhưng điều đó không có vấn đề gì cả nếu chúng được chia đều. Đừng điều tra quá nhiều trừ khi bạn thực sự gặp vấn đề về hiệu suất.

Answer 4

Hàm băm mặc định cho các lớp do người dùng định nghĩa là chỉ trả về id của chúng. Điều này cho một hành vi thường hữu ích; sử dụng một thể hiện của một lớp do người dùng định nghĩa làm khóa từ điển sẽ cho phép lấy giá trị liên quan khi chính xác cùng một đối tượng được cung cấp lại để tra cứu giá trị. ví dụ:

>>> class Foo(object): 
    def __init__(self, foo): 
     self.foo = foo 


>>> f = Foo(10) 
>>> d = {f: 10} 
>>> d[f] 
10 

này phù hợp với bình đẳng mặc định của các tầng lớp người dùng định nghĩa:

>>> g = Foo(10) 
>>> f == g 
False 
>>> d[g] 

Traceback (most recent call last): 
    File "<pyshell#9>", line 1, in <module> 
    d[g] 
KeyError: <__main__.Foo object at 0x0000000002D69390> 

Lưu ý rằng mặc dù f và g có cùng giá trị cho các thuộc tính của họ, họ không bằng nhau và nhìn lên g trong d không tìm thấy giá trị được lưu trữ trong f. Hơn nữa, ngay cả khi chúng ta thay đổi giá trị của f.foo, nhìn lên f trong d vẫn tìm thấy giá trị:

>>> f.foo = 11 
>>> d[f] 
10 

Giả định là trường hợp của một số lớp mới tùy ý phải được coi là không tương đương, trừ khi các lập trình viên đặc biệt khai báo các điều kiện cho hai trường hợp được coi là tương đương bằng cách xác định __eq__ và __hash__.

Và công việc này khá nhiều; nếu tôi xác định một lớp học Car, tôi có thể xem xét hai chiếc xe với các thuộc tính giống hệt nhau để đại diện cho hai chiếc xe khác nhau. Nếu tôi có một từ điển lập bản đồ ô tô cho chủ sở hữu đã đăng ký, tôi không muốn tìm Alice khi tôi tra cứu xe của Bob, ngay cả khi Alice và Bob tình cờ sở hữu những chiếc xe giống hệt nhau! OTOH, nếu tôi định nghĩa một lớp để đại diện cho mã bưu điện, tôi có thể muốn xem xét hai đối tượng khác nhau có cùng mã để có thể biểu diễn hoán đổi cho nhau, và trong trường hợp này, nếu tôi đã ánh xạ từ điển mã bưu điện cho các trạng thái , Tôi rõ ràng muốn có thể tìm thấy cùng một trạng thái với hai đối tượng khác nhau đại diện cho cùng một mã bưu điện.

Tôi gọi đây là sự khác biệt giữa "loại giá trị" và "loại đối tượng". Các loại giá trị đại diện cho một số giá trị và đó là giá trị Tôi quan tâm chứ không phải từng nhận dạng của từng đối tượng riêng lẻ. Hai cách khác nhau để đưa ra cùng một giá trị đều tốt, và "hợp đồng" của mã truyền xung quanh các loại giá trị thường chỉ hứa hẹn sẽ cung cấp cho bạn một đối tượng với một số giá trị, mà không xác định đối tượng cụ thể nào. Đối với các kiểu đối tượng OTOH, mỗi cá thể cá thể có bản sắc riêng của nó, ngay cả khi nó chứa chính xác cùng một dữ liệu như một cá thể khác. Các "hợp đồng" của mã đi qua xung quanh các loại đối tượng thường hứa hẹn để theo dõi các đối tượng chính xác cá nhân.

Vậy tại sao các lớp có thể thay đổi được tích hợp sử dụng id của chúng làm băm của chúng? Đó là bởi vì họ đang tất cả container, và chúng ta thường xem xét container là chủ yếu như các loại giá trị, với giá trị của chúng được xác định bởi các yếu tố chứa:

>>> [1, 2, 3] == [1, 2, 3] 
True 
>>> {f: 10} == {f: 10} 
True 

Nhưng mutable container có giá trị đó là thoáng qua. Một số danh sách nhất định hiện tại có giá trị [1, 2, 3], nhưng có thể bị biến đổi thành giá trị [4, 5, 6]. Nếu bạn có thể sử dụng danh sách làm khóa từ điển, thì chúng tôi sẽ phải quyết định xem liệu tra cứu có nên sử dụng giá trị (hiện tại) của danh sách hay danh tính của nó hay không.Dù bằng cách nào chúng ta có thể (rất) ngạc nhiên khi giá trị của một đối tượng hiện đang được sử dụng như một khóa từ điển được thay đổi bằng cách thay đổi nó. Sử dụng các đối tượng làm khóa từ điển chỉ hoạt động tốt khi giá trị của đối tượng là danh tính của nó hoặc khi danh tính của đối tượng không liên quan đến giá trị của đối tượng. Vì vậy, câu trả lời được chọn bởi Python là khai báo các vùng chứa có thể thay đổi không thể sửa chữa được.

---

Bây giờ, chi tiết cụ thể hơn trong câu trả lời cho những câu hỏi trực tiếp của bạn:

1) Kể từ khi băm mặc định này trong CPython (mặc dù dường như chỉ < 2.6, theo câu trả lời khác/comments) maps vào bộ nhớ của đối tượng địa chỉ, sau đó trong CPython không có hai đối tượng sử dụng băm mặc định, cả hai đều tồn tại cùng một lúc có thể có thể đụng độ trên các giá trị băm của chúng, bất kể các lớp có liên quan (và nếu nó được lưu trữ như là một khóa từ điển trực tiếp). Tôi cũng hy vọng rằng các triển khai Python khác không sử dụng các địa chỉ bộ nhớ như các băm nên vẫn có các bản phân phối băm tốt giữa các đối tượng bằng cách sử dụng băm mặc định. Vì vậy, có, bạn có thể dựa vào nó.

2) Miễn là bạn không trở lại làm băm tùy chỉnh của bạn, kết quả chính xác là giá trị băm của một số đối tượng hiện có, bạn nên tương đối tốt. Sự hiểu biết của tôi là các thùng chứa dựa trên hàm băm của Python tương đối khoan dung các hàm băm nhỏ tối ưu, miễn là chúng không hoàn toàn thoái hóa.

Answer 5

>>> class C(object): 
...  pass 
... 
>>> c = C() 
>>> hash(c) == id(c) 
False 
>>> hash(c) == id(c)/16 
True 

Chia 16 cho Đúng

Answer 6

Trong Python 3 hàm sau được sử dụng trên lớp con của object so với id() của đối tượng (từ pyhash.c)

Py_hash_t 
_Py_HashPointer(void *p) 
{ 
    Py_hash_t x; 
    size_t y = (size_t)p; 
    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid 
     excessive hash collisions for dicts and sets */ 
    y = (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4)); 
    x = (Py_hash_t)y; 
    if (x == -1) 
     x = -2; 
    return x; 
} 

SIZEOF_VOID_P là 8 cho 64 -bit Python và 4 cho Python 32 bit.

>>> class test: pass 
... 
>>> a = test() 
>>> id(a) 
4325845928 
>>> hash(a) 
-9223372036584410438 

Bạn có thể thấy rằng băm được tính từ id(a) sử dụng công thức (id(a) >> 4) | (id(a) << (8 * SIZEOF_VOID_P - 4)), nơi mà các hoạt động Bitwise được thực hiện trên nguyên C ký. Ví dụ, đối với a định nghĩa ở trên:

>>> import numpy 
>>> y = numpy.array([4325845928], dtype='int64') 
>>> SIZEOF_VOID_P = 8 
>>> (y >> 4) | (y << (8 * SIZEOF_VOID_P - 4)) 
array([-9223372036584410438]) 

Lưu ý rằng tôi đang sử dụng numpy.array(dtype='int64') để các hoạt động Bitwise hành động giống như cách họ sẽ trong C (nếu bạn thực hiện các hoạt động tương tự trên ints Python bạn nhận được hành vi khác nhau vì họ không tràn). Xem https://stackoverflow.com/a/5994397/161801.