Hàm băm cho một cặp dài?

Question

Tôi cần ánh xạ một cặp long long tới một số double, nhưng tôi không chắc chắn nên sử dụng hàm băm nào. Mỗi cặp có thể bao gồm hai số bất kỳ, mặc dù trong thực tế chúng thường sẽ là số giữa 0 và khoảng 100 (nhưng một lần nữa, điều đó không được đảm bảo).

Here là tài liệu tr1::unordered_map. Tôi bắt đầu như thế này:

typedef long long Int; 
typedef std::pair<Int, Int> IntPair; 

struct IntPairHash { 
    size_t operator(const IntPair& p) const { 
    return ...; // how to hash the pair? 
    } 
}; 

struct IntPairEqual { 
    bool operator(const IntPair& a, const IntPair& b) const { 
    return a.first == b.first 
     && a.second == b.second; 
    } 
}; 

tr1::unordered_map<IntPair, double, IntPairHash, IntPairEqual> myMap; 

Nói chung, tôi không bao giờ chắc chắn chức năng băm nào sẽ sử dụng. Chức năng băm có mục đích chung tốt là gì?

Answer 1

Bạn có thực sự cần bản đồ dựa trên băm không? Bản đồ chung dựa trên cây nhị phân sẽ hoạt động tốt miễn là độ phức tạp đảm bảo nó làm việc cho vấn đề bạn đang giải quyết.

Answer 2

Đề xuất: Hãy xem bài đăng SO này: "I don't understand std::tr1::unordered_map".

Ngoài ra, Tài liệu tăng cường trên Equality Predicates and Hash Predicates cũng là một địa điểm tốt (cũng như example) này.

Answer 3

boost::hash thư viện chức năng biểu mẫu.

hoặc viết của riêng bạn. phiên bản đơn giản nhất = pair.first * max_second_value + pair.second

Answer 4

Cách tự nhiên để băm một cặp là kết hợp các băm của các thành phần của nó theo một cách nào đó. Cách đơn giản nhất là chỉ với xor:

namespace std { 
namespace tr1 { 

template<typename a, typename b> 
struct hash< std::pair<a, b> > { 
private: 
    const hash<a> ah; 
    const hash<b> bh; 
public: 
    hash() : ah(), bh() {} 
    size_t operator()(const std::pair<a, b> &p) const { 
     return ah(p.first)^bh(p.second); 
    } 
}; 

}} // namespaces 

Lưu ý rằng cặp băm này như (1,1) hoặc (2,2) tất cả về 0, vì vậy bạn có thể muốn sử dụng một số cách phức tạp hơn để kết hợp băm của các bộ phận, tùy thuộc vào dữ liệu của bạn. Boost làm điều gì đó như thế này:

size_t seed = ah(p.first); 
return bh(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);