C++ - Tại sao tăng :: hash_combine cách tốt nhất để kết hợp giá trị băm?

Question

Tôi đã đọc trong các bài đăng khác rằng đây dường như là cách tốt nhất để kết hợp các giá trị băm. Ai đó có thể vui lòng phá vỡ điều này và giải thích tại sao đây là cách tốt nhất để làm điều đó?

template <class T> 
inline void hash_combine(std::size_t& seed, const T& v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 
} 

Chỉnh sửa: Câu hỏi khác chỉ yêu cầu số ma thuật, nhưng tôi muốn biết về toàn bộ chức năng, không chỉ phần này.

Answer 1

Đó là "tốt nhất" là tranh luận.

Đó là "tốt" hoặc thậm chí "rất tốt", ít nhất bề ngoài, thật dễ dàng.

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2); 

Chúng tôi sẽ giả định seed là kết quả trước đó là hasher hoặc thuật toán này.

^= có nghĩa là các bit ở bên trái và các bit ở bên phải đều thay đổi các bit của kết quả.

hasher(v) được coi là băm phong nha trên v. Nhưng phần còn lại là phòng thủ trong trường hợp nó không phải là một băm phong nha.

0x9e3779b9 là giá trị 32 bit (có thể được mở rộng thành 64 bit nếu size_t được cho là 64 bit) có chứa nửa 0 và nửa giây. Về cơ bản, nó là một chuỗi ngẫu nhiên các số 0 và 1 được thực hiện bằng cách xấp xỉ hằng số vô lý cụ thể dưới dạng giá trị điểm cố định cơ sở-2. Điều này giúp đảm bảo rằng nếu hasher trả về giá trị xấu, chúng tôi vẫn nhận được một smear của 1s và 0s trong đầu ra của chúng tôi.

(seed<<6) + (seed>>2) là một chút trộn của hạt giống đến.

Hãy tưởng tượng hằng số 0x bị thiếu. Hãy tưởng tượng các hasher trả về hằng số 0x01000 cho hầu như mọi v được truyền vào. Bây giờ, mỗi bit của hạt giống được trải ra trong lần lặp tiếp theo của băm, trong đó nó lại được trải ra.

seed ^= (seed<<6) + (seed>>2)0x00001000 trở thành 0x00041400 sau một lần lặp. Sau đó, 0x00859500. Khi bạn lặp lại thao tác, bất kỳ bit nào được thiết lập đều được "bôi đen" trên các bit đầu ra. Cuối cùng, các bit phải và trái va chạm và di chuyển bit đã đặt từ "vị trí chẵn" đến "vị trí lẻ".

Các bit phụ thuộc vào giá trị của hạt giống đầu vào phát triển tương đối nhanh và theo các cách phức tạp khi thao tác kết hợp đệ quy trên thao tác hạt giống. Thêm nguyên nhân mang, mà bôi nhọ nhiều thứ hơn. Hằng số 0x thêm một loạt các bit giả ngẫu nhiên làm cho các giá trị băm nhàm chán chiếm nhiều hơn một vài bit của không gian băm sau khi được kết hợp. Nó là bất đối xứng nhờ bổ sung (kết hợp băm của "dog" và "god" cho kết quả khác nhau), nó xử lý các giá trị băm nhàm chán (ánh xạ ký tự với giá trị ascii của chúng, chỉ liên quan đến việc ghép một số bit). Và, nó là hợp lý nhanh chóng.

Kết hợp băm chậm hơn mạnh mẽ về mặt mã hóa có thể tốt hơn trong các trường hợp khác. Tôi, ngây thơ, sẽ cho rằng việc dịch chuyển là sự kết hợp giữa những thay đổi chẵn lẻ và lẻ có thể là một ý tưởng hay (nhưng có thể là bổ sung, di chuyển ngay cả bit từ bit lẻ, làm cho ít vấn đề hơn: sau 3 lần lặp lại, bit sẽ va chạm và thêm và gây ra một carry).

Nhược điểm của loại phân tích này là nó chỉ mất một sai lầm để làm cho hàm băm thực sự tồi tệ. Chỉ ra tất cả những điều tốt đẹp không giúp ích gì nhiều. Vì vậy, một điều khác làm cho nó tốt bây giờ là nó là hợp lý nổi tiếng và trong một kho lưu trữ mã nguồn mở, và tôi đã không nghe bất cứ ai chỉ ra lý do tại sao nó là xấu.