Cách chính xác và tốt để triển khai __hash __() là gì?

Question

Cách chính xác và tốt để triển khai __hash__() là gì?

Tôi đang nói về hàm trả về mã băm sau đó được sử dụng để chèn các đối tượng vào từ điển hashtables.

Khi __hash__() trả về một số nguyên và được sử dụng cho các đối tượng "binning" vào hashtables, tôi giả định rằng giá trị của số nguyên được trả về phải được phân phối đồng đều cho dữ liệu chung (để giảm thiểu va chạm). Thực hành tốt để có được các giá trị như vậy là gì? Va chạm có phải là vấn đề không? Trong trường hợp của tôi, tôi có một lớp nhỏ hoạt động như một lớp container chứa một số int, một số float và một chuỗi.

Answer 1

Cách thực hiện dễ dàng, chính xác __hash__() là sử dụng một bộ chìa khóa. Nó sẽ không được nhanh như băm chuyên dụng, nhưng nếu bạn cần mà sau đó có lẽ bạn nên thực hiện các loại trong C.

Dưới đây là một ví dụ của việc sử dụng một chìa khóa cho băm và bình đẳng:

class A(object): 
    def __key(self): 
     return (self.attr_a, self.attr_b, self.attr_c) 

    def __eq__(x, y): 
     return x.__key() == y.__key() 

    def __hash__(self): 
     return hash(self.__key()) 

Ngoài ra, documentation of __hash__ có thêm thông tin, có thể có giá trị trong một số trường hợp cụ thể.

Answer 2

Phụ thuộc vào kích thước của giá trị băm bạn trả lại. Đó là logic đơn giản rằng nếu bạn cần trả về một int 32bit dựa trên băm của bốn int 32bit, bạn sẽ bị va chạm.

Tôi sẽ ưu tiên các thao tác bit. Giống như, mã C giả sau đây:

int a; 
int b; 
int c; 
int d; 
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F); 

một hệ thống như vậy có thể làm việc cho nổi quá, nếu bạn chỉ đơn giản là chúng như giá trị bit của họ chứ không phải là thực sự đại diện cho một giá trị dấu chấm động, có lẽ tốt hơn.

Đối với chuỗi, tôi có ít/không có ý tưởng.

Answer 3

Tôi có thể cố gắng trả lời phần thứ hai của câu hỏi của bạn.

Các va chạm có thể sẽ không phải do mã băm, mà từ ánh xạ mã băm đến chỉ mục trong bộ sưu tập. Vì vậy, ví dụ hàm băm của bạn có thể trả về các giá trị ngẫu nhiên từ 1 đến 10000, nhưng nếu bảng băm của bạn chỉ có 32 mục, bạn sẽ nhận được các xung đột khi chèn.

Ngoài ra, tôi cho rằng các va chạm sẽ được giải quyết bởi bộ sưu tập trong nội bộ và có nhiều phương pháp để giải quyết xung đột. Cách đơn giản nhất (và tệ nhất) là, với mục nhập chèn vào chỉ mục i, thêm 1 vào i cho đến khi bạn tìm thấy một điểm trống và chèn vào đó. Retrieval sau đó hoạt động theo cùng một cách. Điều này dẫn đến các truy xuất không hiệu quả cho một số mục nhập, vì bạn có thể có một mục nhập yêu cầu duyệt toàn bộ bộ sưu tập để tìm!

Các phương pháp giải quyết va chạm khác giảm thời gian truy xuất bằng cách di chuyển các mục nhập trong bảng băm khi một mục được chèn vào để phát tán mọi thứ. Điều này làm tăng thời gian chèn nhưng giả sử bạn đọc nhiều hơn bạn chèn. Ngoài ra còn có các phương pháp thử và phân nhánh các mục nhập va chạm khác nhau để các mục nhập cụm vào một vị trí cụ thể.

Ngoài ra, nếu bạn cần thay đổi kích thước bộ sưu tập, bạn sẽ cần phải phục hồi mọi thứ hoặc sử dụng phương pháp băm năng động.

Tóm lại, tùy thuộc vào những gì bạn đang sử dụng mã băm cho bạn có thể phải triển khai phương pháp giải quyết va chạm của riêng bạn.Nếu bạn không lưu trữ chúng trong một bộ sưu tập, bạn có thể lấy đi một hàm băm mà chỉ tạo ra các mã băm trong một phạm vi rất lớn. Nếu vậy, bạn có thể chắc chắn rằng thùng chứa của bạn lớn hơn mức cần thiết (càng lớn càng tốt) tùy thuộc vào mối quan ngại về bộ nhớ của bạn.

Dưới đây là một số liên kết nếu bạn quan tâm hơn:

coalesced hashing on wikipedia

Wikipedia cũng đã một summary các phương pháp khác nhau có độ phân giải va chạm:

Ngoài ra, "File Organization And Processing" bởi Tharp bao gồm rất nhiều va chạm phương pháp phân giải rộng rãi. IMO nó là một tham chiếu tuyệt vời cho các thuật toán băm.

Answer 4

Paul Larson của Microsoft Research đã nghiên cứu nhiều chức năng băm khác nhau. Anh ấy nói với tôi rằng

for c in some_string: 
    hash = 101 * hash + ord(c) 

hoạt động đáng kinh ngạc với nhiều chuỗi. Tôi đã tìm thấy rằng các kỹ thuật đa thức tương tự hoạt động tốt để tính toán băm của các trường con khác nhau.

Answer 5

John Millikin đề xuất một giải pháp tương tự như sau:

class A(object): 

    def __init__(self, a, b, c): 
     self._a = a 
     self._b = b 
     self._c = c 

    def __eq__(self, othr): 
     return ((self._a, self._b, self._c) == 
       (othr._a, othr._b, othr._c)) 

    def __hash__(self): 
     return hash((self._a, self._b, self._c)) 

Vấn đề với giải pháp này là hash(A(a, b, c)) == hash((a, b, c)). Nói cách khác, hàm băm va chạm với phần tử của các thành viên chính của nó. Có lẽ điều này không quan trọng trong thực tế?

Các Python documentation on __hash__ gợi ý kết hợp băm của các tiểu hợp phần sử dụng một cái gì đó giống như XOR, mang đến cho chúng ta điều này:

class B(object): 

    def __init__(self, a, b, c): 
     self._a = a 
     self._b = b 
     self._c = c 

    def __eq__(self, othr): 
     return (isinstance(othr, type(self)) 
       and (self._a, self._b, self._c) == 
        (othr._a, othr._b, othr._c)) 

    def __hash__(self): 
     return (hash(self._a)^hash(self._b)^hash(self._c)^
       hash((self._a, self._b, self._c))) 

Bonus: mạnh mẽ hơn __eq__ ném trong đó cho biện pháp tốt.

Cập nhật: như Blckknght chỉ ra, thay đổi thứ tự của a, b và c có thể gây ra sự cố. Tôi đã thêm ^ hash((self._a, self._b, self._c)) bổ sung để nắm bắt thứ tự của các giá trị được băm. Có thể xóa ^ hash(...) cuối cùng này nếu không thể sắp xếp lại các giá trị được kết hợp (ví dụ: nếu chúng có các loại khác nhau và do đó giá trị của _a sẽ không bao giờ được gán cho _b hoặc _c, v.v ...).