C++ 关于 boost::unordered_map & boost::hash 的一些问题

Question

我最近才开始深入研究 boost 及其容器，我在网络和 stackoverflow 上阅读了几篇文章，发现 boost::unordered_map 是大集合中性能最快的容器。 所以，我有这个类状态，它在容器中必须是唯一的(没有重复)并且容器中将有数百万甚至数十亿个状态。 因此，我一直在尝试针对小尺寸和尽可能少的计算对其进行优化。我之前使用的是 boost::ptr_vector，但正如我在 stackoverflow 上读到的那样，只要其中没有那么多对象， vector 就是好的。 在我的例子中，状态描述了来自机器人的感觉运动信息，因此可能有大量的状态，因此快速查找是重中之重。 关注boost documentation对于 unordered_map，我意识到我可以做两件事来加快速度:使用 hash_function，并使用相等运算符根据 hash_function 比较状态。 因此，我实现了一个私有(private) hash() 函数，它接收状态信息并使用 boost::hash_combine，创建一个 std::size_t 哈希值。 operator== 基本上比较状态的哈希值。 所以:

• 是 std::size_t 足以覆盖数十亿个可能的 hash_function 组合？为了避免重复状态，我打算使用 他们的哈希值。

• 创建 state_map 时，我应该使用 State* 还是哈希作为键 值(value) ？ 即:boost::unordered_map<State*,std::size_t> state_map; 或者 boost::unordered_map<std::size_t,State*> state_map;

• 查找时间是否为 boost::unordered_map::iterator = state_map.find() 比通过 boost::ptr_vector 和 比较每个迭代器的键值 ?

• 最后，关于如何优化此类无序映射的任何提示或技巧 对于速度和快速查找将不胜感激。

编辑:我看到了很多答案，一个是不使用 boost，而是使用 C++0X，另一个是不使用 unordered_set，但老实说，我仍然想看看 boost::unordered_set 是如何与哈希函数。 我已经按照boost的文档进行了实现，但我仍然无法弄清楚如何将boost的哈希函数与有序集一起使用。

Answer 1

这个有点糊涂

• 你说的不是“你可以做些什么来加快速度”；相反，它们是您的类型的强制性要求，以便有资格作为无序映射的元素类型，以及无序集(您可能更想要)。

• 您需要提供比较对象 而非散列值的相等运算符。相等的全部意义在于区分具有相同散列的元素。

• size_t是无符号整数类型，在 x86 上为 32 位，在 x64 上为 64 位。由于您需要“数十亿个元素”，这意味着数 GB 的数据，我假设您无论如何都有一台可靠的 x64 机器。

• 关键是您的哈希函数良好，即几乎没有冲突。

• 你想要一套，而不是 map 。将对象直接放入集合中:std::unordered_set<State> .如果您要映射 某些东西，请使用 map ，即将状态映射到其他东西。哦，如果可以的话，使用 C++0x，而不是 boost。

• 使用 hash_combine很好。

---

宝贝例子:

struct State
{
  inline bool operator==(const State &) const;
  /* Stuff */
};

namespace std
{
  template <> struct hash<State>
  {
    inline std::size_t operator()(const State & s) const
    {
      /* your hash algorithm here */
    }
  };
}

std::size_t Foo(const State & s) { /* some code */ }

int main()
{
  std::unordered_set<State> states; // no extra data needed
  std::unordered_set<State, Foo> states; // another hash function
}