Va chạm bất ngờ với std :: hash

Question

Tôi biết băm vô hạn chuỗi thành 32b int phải tạo ra xung đột, nhưng tôi mong đợi từ hàm băm một số phân phối tốt đẹp.

Thật lạ khi hai chuỗi này có cùng một mã băm?

size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
//hash0 == hash1 

Tôi biết tôi có thể sử dụng boost::hash<std::string> hoặc những người khác, nhưng tôi muốn biết những gì là sai với std::hash. Tôi có sử dụng sai không? Không phải tôi bằng cách nào đó "hạt giống" nó?

Answer 1

Không có gì sai với việc bạn sử dụng std::hash là. Vấn đề là chuyên môn std::hash<std::string> được cung cấp bởi việc thực hiện thư viện chuẩn đi kèm với Visual Studio 2010 chỉ mất một tập con của các ký tự chuỗi để xác định giá trị băm (có lẽ vì lý do hiệu suất). Thật trùng hợp, ký tự cuối cùng của chuỗi có 14 ký tự không phải là một phần của tập hợp này, đó là lý do tại sao cả hai chuỗi mang lại giá trị băm giống nhau.

Theo tôi biết hành vi này phù hợp với tiêu chuẩn, trong đó yêu cầu chỉ nhiều lệnh gọi hàm băm có cùng đối số phải luôn trả về cùng một giá trị. Tuy nhiên, xác suất của một va chạm băm nên là tối thiểu. Việc thực hiện VS2010 đáp ứng phần bắt buộc, nhưng không tính đến phần tùy chọn.

Để biết chi tiết, hãy xem triển khai trong tệp tiêu đề xfunctional (bắt đầu tại dòng 869 trong bản sao của tôi) và §17.6.3.4 của tiêu chuẩn C++ (latest public draft).

Nếu bạn hoàn toàn cần hàm băm tốt hơn cho chuỗi, bạn nên tự thực hiện nó. Nó thực sự là not that hard.

Answer 2

Bạn không gieo hạt hàm băm, bạn chỉ có thể muối "chúng" nhiều nhất.

Chức năng này được sử dụng đúng cách và va chạm này có thể là ngẫu nhiên.

Bạn không thể biết liệu hàm băm không được phân phối đồng đều trừ khi bạn thực hiện một phép thử lớn với các khóa ngẫu nhiên.

Answer 3

Hàm băm TR1 và tiêu chuẩn mới nhất xác định quá tải thích hợp cho những thứ như chuỗi. Khi tôi chạy mã này bằng cách sử dụng std :: tr1 :: hash (g ++ 4.1.2), tôi nhận được các giá trị băm khác nhau cho hai chuỗi này.

Answer 4

Bạn có thể nhận được các giá trị băm khác nhau. Tôi nhận được giá trị khác nhau băm (GCC 4.5):

hashtest.cpp

#include <string> 
#include <iostream> 
#include <functional> 
int main(int argc, char** argv) 
{ 
size_t hash0 = std::hash<std::string>()("generated_id_0"); 
size_t hash1 = std::hash<std::string>()("generated_id_1"); 
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n"; 
return 0; 
} 

Output

# g++ hashtest.cpp -o hashtest -std=gnu++0x 
# ./hashtest 
16797002355621538189 != 16797001256109909978 

Answer 5

Thuật toán băm chính xác không được chỉ định theo tiêu chuẩn, do đó kết quả sẽ thay đổi. Thuật toán được VC10 sử dụng dường như không nhận tất cả các ký tự nếu chuỗi dài hơn 10 ký tự; nó các khoản tạm ứng với số gia tăng là 1 + s.size()/10. Điều này là hợp pháp, mặc dù theo quan điểm của QoI, khá đáng thất vọng; mã băm như vậy được biết là hoạt động rất kém đối với một số bộ dữ liệu điển hình (như URL).Tôi muốn khuyên bạn thay thế nó với một trong hai một hash FNV hoặc một dựa trên một số nguyên tố Mersenne:

FNV băm:

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = (16777619 * result) 
        ^static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

Mersenne thủ băm:

struct hash 
{ 
    size_t operator()(std::string const& s) const 
    { 
     size_t result = 2166136261U ; 
     std::string::const_iterator end = s.end() ; 
     for (std::string::const_iterator iter = s.begin() ; 
       iter != end ; 
       ++ iter) { 
      result = 127 * result 
        + static_cast< unsigned char >(*iter) ; 
     } 
     return result ; 
    } 
}; 

(Các FNV băm được cho là tốt hơn, nhưng băm chính Mersenne sẽ nhanh hơn trên nhiều máy, vì nhân với 127 thường là nhanh hơn đáng kể so với nhân với 2166136261.)