Hàm băm chung cho tất cả các hộp chứa STL

Question

Tôi đang sử dụng std::unordered_map<key,value> khi triển khai. tôi sẽ sử dụng bất kỳ vùng chứa STL nào làm khóa. Tôi đã tự hỏi nếu nó có thể tạo ra một hàm băm chung cho bất kỳ container đang được sử dụng.

This câu hỏi trong SO cung cấp chức năng in chung cho tất cả các vùng chứa STL. Trong khi bạn có thể có điều đó, tại sao bạn không thể có một cái gì đó giống như một hàm Hash định nghĩa mọi thứ? Và vâng, một mối quan tâm lớn cũng là nó cần phải nhanh chóng và hiệu quả.

Tôi đã cân nhắc thực hiện chức năng băm đơn giản chuyển đổi giá trị của khóa thành size_t và thực hiện chức năng đơn giản như this.

Việc này có thể thực hiện được không?

PS: Vui lòng không sử dụng thư viện boost. Cảm ơn.

Answer 1

Chúng tôi có thể nhận được câu trả lời bằng cách bắt chước Tăng và kết hợp băm.

Cảnh báo: Kết hợp băm, tức là tính toán nhiều thứ từ nhiều băm, không phải là một ý tưởng hay, vì hàm băm kết quả không "tốt" theo nghĩa thống kê. Một băm thích hợp của nhiều thứ nên được xây dựng từ toàn bộ dữ liệu thô của tất cả các thành phần, không phải từ các băm trung gian. Nhưng hiện tại không có cách nào tốt để làm điều này.

Dù sao:

Trước hết, chúng tôi cần chức năng hash_combine. Vì lý do ngoài sự hiểu biết của tôi nó không được đưa vào thư viện chuẩn, nhưng đó là trung tâm cho tất cả mọi thứ khác:

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); 
} 

Sử dụng này, chúng ta có thể băm tất cả những gì được tạo thành từ các yếu tố hashable, theo cặp và các bộ cụ thể (tập thể dục cho người đọc).

Tuy nhiên, chúng tôi cũng có thể sử dụng điều này cho các vùng chứa băm bằng cách băm thành phần của chúng. Đây chính xác là những gì "phạm vi băm" của Boost thực hiện, nhưng nó rất dễ làm cho chính bạn bằng cách sử dụng hàm kết hợp.

Khi bạn đã thực hiện bằng văn bản hasher phạm vi của bạn, chỉ cần chuyên std::hash và bạn tốt để đi:

namespace std 
{ 
    template <typename T, class Comp, class Alloc> 
    struct hash<std::set<T, Comp, Alloc>> 
    { 
    inline std::size_t operator()(const std::set<T, Comp, Alloc> & s) const 
    { 
     return my_range_hash(s.begin(), s.end()); 
    } 
    }; 

    /* ... ditto for other containers */ 
} 

Nếu bạn muốn bắt chước các máy in đẹp, bạn thậm chí có thể làm điều gì đó cực đoan hơn và chuyên std::hash cho tất cả các container, nhưng tôi muốn có thể cẩn thận hơn với điều đó và làm cho một đối tượng băm rõ ràng cho container:

template <typename C> struct ContainerHasher 
{ 
    typedef typename C::value_type value_type; 
    inline size_t operator()(const C & c) const 
    { 
    size_t seed = 0; 
    for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it) 
    { 
     hash_combine<value_type>(seed, *it); 
    } 
    return seed; 
    } 
}; 

Cách sử dụng:

std::unordered_map<std::set<int>, std::string, ContainerHasher<std::set<int>>> x;