一对 long long 的哈希函数？

Question

我需要将一对 long long 映射到一个 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

boost::hash 形成函数库。

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

Answer 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

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

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

Answer 3

建议：看看这个帖子："我不明白std::tr1 ::unordered_map"。

另外，有关 相等谓词和哈希谓词<的 Boost 文档/a> 也是一个好地方（以及这个 示例）。

Answer 4

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