Làm thế nào để tạo ra một hash_combine tốt với đầu ra 64 bit (lấy cảm hứng từ boost :: hash_combine)

Question

Hiện tại Boost có hàm hash_combine xuất ra 32 bit số nguyên không dấu (chính xác, size_t). Một số tài liệu tham khảo:

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/combine.html

Magic number in boost::hash_combine

Tôi muốn khám phá về cách tạo phiên bản 64 bit của hash_combine.

Điều đầu tiên là nhận tỷ lệ vàng hoặc bất kỳ số vô lý nào khác trong 64 bit.

Phần thứ hai là sử dụng ca. Phần này khá phức tạp và tôi muốn hỏi liệu có thực hành hay hướng dẫn tốt nhất về việc sử dụng ca làm việc để có được giá trị băm không? Hoặc chọn các thay đổi như mã ban đầu:

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

hoàn toàn ngẫu nhiên?

Ngoài ra cách đánh giá đầu ra của hash_combine để đảm bảo rằng nó không tạo ra va chạm nhiều hơn hàm băm gốc hash_value?

Answer 1

Đọc http://burtleburtle.net/bob/hash/doobs.html để biết một số thông tin cơ bản về thiết kế hàm băm và phần còn lại của các bài viết trong http://burtleburtle.net/bob/hash/ để biết thêm thông tin chi tiết. CityHash đã được thử nghiệm sử dụng http://code.google.com/p/smhasher/ và bạn có thể kiểm tra hash_combine bằng cách sử dụng cùng một bộ kiểm tra.

Mặc dù tôi không phải là chuyên gia về băm, thiết kế của hàm băm gần đây khiến tôi tin rằng việc sử dụng hash_combine() của kỹ thuật tăng 2 ca không còn được cải thiện và có thể được cải thiện.

Answer 2

Nếu bạn chỉ muốn một hash_combine băm 2 giá trị 64 bit thành một, và bạn không cần hàm băm mới cho chuỗi, bạn có thể nhấc một đoạn mã nhỏ từ CityHash, giống như thế này (giả sử size_t là một số nguyên unsigned 64 bit, thêm chút yêu thích của bạn Preprocessor hoặc mẫu thủ đoạn gian trá để xác nhận rằng):

template <class T> inline void hash_combine(std::size_t& seed, const T& v) 
{ 
    std::hash<T> hasher; 
    const std::size_t kMul = 0x9ddfea08eb382d69ULL; 
    std::size_t a = (hasher(v)^seed) * kMul; 
    a ^= (a >> 47); 
    std::size_t b = (seed^a) * kMul; 
    b ^= (b >> 47); 
    seed = b * kMul; 
} 

(tôi nghĩ rằng sao chép đoạn mã này ở đây và các nơi khác là OK vì nó không tạo thành một 'phần đáng kể' của mã CityHash, nhưng vui lòng kiểm tra các nguồn CityHash & thỏa thuận cấp phép để tự quyết định)