해시 함수를 길게 한 쌍의?

Question

long long 한 쌍을 double에 매핑해야하지만 사용할 해시 기능을 잘 모르겠습니다. 실제적으로 그들은 보통 0과 약 100 사이의 숫자가 될 수 있지만 각 쌍은 임의의 두 숫자로 구성 될 수 있습니다 (단, 다시 말해 보장 할 수 없음).

Here은 tr1::unordered_map 설명서입니다. 나는 다음과 같이 시작했다 :

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; 

일반적으로 어떤 해시 함수를 사용할지는 모르겠다. 좋은 범용 해시 함수는 무엇입니까?

Answer 1

정말 해시 기반지도가 필요합니까? 이진 트리 기반의 일반 맵은 복잡성으로 인해 문제를 해결할 수있는 한 제대로 작동합니다.

Answer 2

제안 :이 게시물을보십시오 : "I don't understand std::tr1::unordered_map".

또한 부스트 문서 Equality Predicates and Hash Predicates도 좋은 장소입니다 (example도 마찬가지입니다).

Answer 3

boost::hash 형태의 기능 라이브러리.

또는 직접 작성하십시오. 가장 간단한 버전 = pair.first * max_second_value + pair.second

Answer 4

쌍을 해시하는 자연스러운 방법은 구성 요소의 해시를 결합하는 것입니다. 가장 간단한 방법은 XOR 함께 :이 (1,1) 또는 제로 (2,2) 모두 같은 쌍을 해시 것을

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 

주, 그래서 당신은을 결합하는 좀 더 복잡한 방법을 사용할 수 있습니다 데이터에 따라 부품의 해시. Boost는 다음과 같은 기능을 수행합니다.

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