哈希函数对于一对多长？

Question

我需要将一对映射long long到a double,但我不确定要使用什么散列函数.每对可以由任意两个数字组成,但在实践中它们通常是介于0和之间的数字100(但同样,这是不可保证的).

这是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

散列对的自然方法是以某种方式组合其组件的散列.最简单的方法是使用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

请注意,这个哈希对象(1,1)或(2,2)全部为零,因此您可能希望使用一些更复杂的方法来组合零件的哈希值,具体取决于您的数据.Boost做了这样的事情:

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

Answer 2

boost :: hash表单功能库.

或者自己写.最简单的版本= pair.first*max_second_value + pair.second

Answer 3

你真的需要一个基于哈希的地图吗？只要复杂性保证它能够解决您正在解决的问题，基于二叉树的通用映射就可以很好地工作。