4

hash map我想知道对于for 坐标（在 2d 或 3d 中，即双精度向量）是否有一个通用的全方位解决方案？

这里的一个示例演示了如何为 创建自定义哈希映射pair<int,int>，但想出一个从pair<double,double>（可以表示二维坐标）到的唯一映射似乎并非易事size_t。

我知道我可以通过提供比较器对象来使用有序映射，但是对于我的应用程序来说，不需要对它们进行排序，而且哈希映射似乎更快。但是，由于我是所有这些hash东西的新手，所以我对如何进行有点迷茫。

p/s/ 我使用 c++11。

4

4 回答 4

5

为避免额外的依赖，您可以使用std::hash. 这是一个使用您发布的链接中的代码的示例，并更新为使用std::pair<double,double>：

#include <unordered_map>
#include <cassert>

using namespace std;

class TPoint3D{
public:
    TPoint3D(double x, double y, double z) : x(x), y(y), z(z){};

    double x, y, z;
};

struct hashFunc{
    size_t operator()(const TPoint3D &k) const{
    size_t h1 = std::hash<double>()(k.x);
    size_t h2 = std::hash<double>()(k.y);
    size_t h3 = std::hash<double>()(k.z);
    return (h1 ^ (h2 << 1)) ^ h3;
    }
};

struct equalsFunc{
  bool operator()( const TPoint3D& lhs, const TPoint3D& rhs ) const{
    return (lhs.x == rhs.x) && (lhs.y == rhs.y) && (lhs.z == rhs.z);
  }
};

typedef unordered_map<TPoint3D, int, hashFunc, equalsFunc> TPoint3DMap;

int main(){
  TPoint3DMap myMap;

  // test equalsFunc
  myMap[TPoint3D(10.0, 20.0, 30.0)] = 100;
  myMap[TPoint3D(10.0, 20.0, 30.0)] = 200;

  assert(myMap[TPoint3D(10.0, 20.0, 30.0)] == 200);

  // test if hashFunc handles well repeated values inside TPoint3D
  myMap[TPoint3D(10.0, 10.0, 10.0)] = 1;
  myMap[TPoint3D(10.0, 20.0, 10.0)] = 2;
  myMap[TPoint3D(10.0, 10.0, 20.0)] = 3;
  myMap[TPoint3D(20.0, 10.0, 10.0)] = 4;

  assert(myMap[TPoint3D(10.0, 10.0, 10.0)] == 1);
  assert(myMap[TPoint3D(10.0, 20.0, 10.0)] == 2);
  assert(myMap[TPoint3D(10.0, 10.0, 20.0)] == 3);
  assert(myMap[TPoint3D(20.0, 10.0, 10.0)] == 4);

  return 0;
}

正如我之前所说，如果您希望使用另一种结构，您必须调整pairHash类和pairEquals结构 operator()以分别适当地散列和比较新键。

干杯

编辑 ：

  • 修改代码以使用自定义 TPPoint3D 类和统一仿函数类定义（均使用结构）。
  • 添加了简单的测试来验证 hash 和 equals 函子。
于 2013-05-28T14:13:38.747 回答
4

我无法评论安德烈的回答，因为我还没有足够的声誉，但是任何尝试使用 ^ (XOR) 创建散列函数的人都应该注意 XOR 是关联的。换句话说a ^ (b ^ c) == (a ^ b) ^ c。这意味着

(h1 ^ (h2 << 1)) ^ h3

这是安德烈答案的返回值，与以下内容相同：

h1 ^ ((h2 << 1) ^ h3)

由于 XOR ( a ^ b == b ^ a) 的交换性质，它本身等同于：

(h3 ^ (h2 << 1)) ^ h1

所有这一切意味着我所指的哈希方法对于 distinct a、b和将c返回与对于 相同的哈希。换句话说，x 和 z 坐标是顺序无关的/不敏感的。(a,b,c)(c,b,a)

根据您使用此哈希方法的方式，这可能不是问题。但是，例如，如果您正在散列的点与网格对齐，您将收到大量的散列冲突。

我会将 Andre 的答案中的 return 语句中的表达式替换为下面的表达式。这应该取决于订单/敏感。

(h1 ^ (h2 << 1)) ^ (h3 << 2)
于 2017-12-21T16:16:07.030 回答
2

在 3D 情况下，假设您正在执行精确查找std::unordered_map<std::tuple<double, double, double>, your_value_type>，应该可以正常工作。根据它正在聚合的类型的相等和散列函数为您定义相等和散列函数。std::tuple<...>

2D 情况当然是相同的，但使用std::tuple<double, double>.

编辑：对不起，错误信息。实际上没有为std::tuple. 要使用这种方法，您必须定义一个hash_tuple模板仿函数类，然后在std::unordered_map. 其他答案显示了如何做那部分。

于 2013-05-28T17:14:45.163 回答
1

使用hash_combineBoost 怎么样？

http://www.boost.org/doc/libs/1_53_0/doc/html/hash/combine.html

于 2013-05-28T13:41:41.133 回答