Giá trị băm cho một tiêu chuẩn :: unordered_map

Question

Theo tiêu chuẩn không có hỗ trợ cho các thùng chứa (hãy để một mình những thứ không có thứ tự) trong lớp std::hash. Vì vậy, tôi tự hỏi làm thế nào để thực hiện điều đó. Những gì tôi có là:

std::unordered_map<std::wstring, std::wstring> _properties; 
std::wstring _class; 

Tôi nghĩ về lặp lại các mục, tính toán băm cá nhân cho các phím và các giá trị (thông qua std::hash<std::wstring>) và nối kết quả bằng cách nào đó.

Điều gì sẽ là một cách hay để thực hiện điều đó và có quan trọng không nếu thứ tự trong bản đồ không được xác định?

Lưu ý: Tôi không muốn sử dụng tăng.

Một XOR đơn giản đã được đề xuất, vì vậy nó sẽ là như thế này:

size_t MyClass::GetHashCode() 
{ 
    std::hash<std::wstring> stringHash; 
    size_t mapHash = 0; 
    for (auto property : _properties) 
    mapHash ^= stringHash(property.first)^stringHash(property.second); 

    return ((_class.empty() ? 0 : stringHash(_class)) * 397)^mapHash; 
} 

?

Tôi thực sự không chắc liệu XOR đơn giản đó có đủ không.

Answer 1

đáp ứng

Nếu bởi đủ, bạn có ý nghĩa hay không chức năng của bạn là đơn ánh, câu trả lời là Không. Lý do là tập tất cả các giá trị hash chức năng của bạn ra có thể có cardinality 2^64, trong khi không gian đầu vào của bạn là nhiều hơn lớn hơn. Tuy nhiên, điều này là không thực sự quan trọng, bởi vì bạn không thể có một hàm băm tiêm cho bản chất của đầu vào của bạn. Hàm băm tốt có những phẩm chất sau:

• Không dễ dàng đảo ngược. Với đầu ra k, nó không khả thi tính toán trong vòng đời của vũ trụ để tìm m sao cho h (m) = k.
• Phạm vi được phân bố đồng đều trên không gian đầu ra.
• Thật khó để tìm thấy hai đầu vào m và m 'sao cho h (m) = h (m')

Tất nhiên, mức độ của những thực sự phụ thuộc vào việc bạn muốn cái gì đó là mã hóa an toàn, hoặc bạn muốn lấy một số dữ liệu tùy ý và chỉ cần gửi một số nguyên 64 bit tùy ý. Nếu bạn muốn một cái gì đó mã hóa an toàn, viết nó cho mình không phải là một ý tưởng tốt. Trong trường hợp đó, bạn cũng cần đảm bảo rằng chức năng này nhạy cảm với những thay đổi nhỏ trong đầu vào. Đối tượng chức năng std::hash không bắt buộc phải bảo mật về mặt mã hóa. Nó tồn tại cho các trường hợp sử dụng isomorphic cho các bảng băm. CPP Rerefence nói:

Đối với hai tham số khác nhau k1 và k2 rằng không bằng nhau, xác suất mà std::hash<Key>()(k1) == std::hash<Key>()(k2) nên rất nhỏ, tiếp cận 1.0/std::numeric_limits<size_t>::max().

Tôi sẽ hiển thị bên dưới cách giải pháp hiện tại của bạn không thực sự đảm bảo điều này.

Va chạm

tôi sẽ cung cấp cho bạn một vài trong số những quan sát của tôi trên một biến thể của giải pháp của bạn (Tôi không biết những gì thành viên _class của bạn là).

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) { 
    std::hash<std::string> h; 
    std::size_t result = 0; 
    for (auto&& p : m) { 
     result ^= h(p.first)^h(p.second); 
    } 
    return result; 
} 

Thật dễ dàng để tạo ra xung đột.Hãy xem xét các bản đồ sau:

std::unordered_map<std::string, std::string> container0; 
std::unordered_map<std::string, std::string> container1; 
container0["123"] = "456"; 
container1["456"] = "123"; 
std::cout << hash_code(container0) << '\n'; 
std::cout << hash_code(container1) << '\n'; 

Trên máy tính của tôi, biên soạn với g ++ 4.9.1, kết quả đầu ra này:

1225586629984767119 
1225586629984767119 

Câu hỏi đặt ra là liệu vấn đề này hay không phát sinh. Điều có liên quan là mức độ thường xuyên bạn sẽ có bản đồ nơi các khóa và giá trị được đảo ngược. Những va chạm này sẽ xảy ra giữa hai bản đồ trong đó tập các khóa và giá trị giống nhau.

Trình tự lặp lại

Hai unordered_map trường có chính xác các cặp khóa-giá trị tương tự sẽ không nhất thiết phải theo thứ tự lặp lại. CPP Rerefence nói:

Đối với hai tham số k1 và k2 rằng đều bình đẳng, std::hash<Key>()(k1) == std::hash<Key>()(k2).

Đây là yêu cầu nhỏ đối với hàm băm. Giải pháp của bạn tránh điều này vì thứ tự lặp lại không quan trọng vì XOR là giao hoán.

Một Giải pháp

Nếu bạn không cần cái gì đó là mã hóa an toàn, bạn có thể sửa đổi giải pháp của bạn một chút để giết đối xứng. Cách tiếp cận này là không quan trọng trong thực tế cho các bảng băm và tương tự. Giải pháp này cũng độc lập với thực tế là thứ tự trong một unordered_map là không xác định. Nó sử dụng cùng một thuộc tính mà giải pháp của bạn sử dụng (Commutativity of XOR).

std::size_t hash_code(const std::unordered_map<std::string, std::string>& m) { 
    const std::size_t prime = 19937; 
    std::hash<std::string> h; 
    std::size_t result = 0; 
    for (auto&& p : m) { 
     result ^= prime*h(p.first) + h(p.second); 
    } 
    return result; 
} 

Tất cả các bạn cần trong một hàm băm trong trường hợp này là một cách để ánh xạ một cặp khóa-giá trị cho một giá trị tùy ý băm tốt, và là một cách để kết hợp băm của các cặp khóa-giá trị sử dụng một giao hoán hoạt động. Bằng cách đó, trật tự không quan trọng. Trong ví dụ hash_code Tôi đã viết, giá trị băm cặp khóa-giá trị chỉ là kết hợp tuyến tính của giá trị băm của khóa và giá trị băm của giá trị. Bạn có thể xây dựng một cái gì đó phức tạp hơn một chút, nhưng không cần thiết cho điều đó.