19

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

一般来说，我永远不确定要使用什么散列函数。什么是好的通用哈希函数？

4

4 回答 4

11

散列一对的自然方法是以某种方式组合其组件的散列。最简单的方法就是使用 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);
于 2009-04-10T17:00:57.480 回答
10

boost::hash形式的函数库。

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

于 2009-04-10T15:58:52.153 回答
2

一个建议：看看这个 SO 帖子：“我不明白std::tr1::unordered_map”。

此外，关于Equality Predicates 和 Hash Predicates的 Boost Documentation也是一个好地方（以及这个例子）。

于 2009-04-10T15:58:32.683 回答
1

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

于 2009-04-10T15:51:36.380 回答