创建通用哈希表 - C++

Question

.NET Framework提供了一个Dictionary<TKey,TValue>类，它是基于哈希表实现的，可以在常量时间（O(1)）内检索数据。我想找到一个类似的C++实现。我知道std::map，但是其中的数据检索需要对数时间。是否有任何好的哈希表实现可以在C++中在常量时间内检索数据？

如果我要编写自己的哈希表，我如何为键计算哈希码？与.NET一样，我考虑对类型实现GetHashCode()方法。

template<typename TKey,typename TVal>
class Dictionary
{
public:
   void Add(TKey key, TVal val){
       int hashCode = key.GetHashCode();
       /* .... */
   }
}

如果我像上面那样进行操作，而给定的键类型没有GetHashCode()方法，编译器会报错。但是当键是原始类型如int时，这种方法不起作用。我可能需要编写一个包装器来提供GetHashCode()。

我想知道C++实现这个的方式是什么？

有什么想法吗？

- Navaneeth K N

Answer 1

如果需要严格遵守C ++标准，请查看 C ++ Technical Report 1 以获取 std :: tr1 :: unordered_map 。

实际上， std :: hash_map 不是C ++标准，但仍然被广泛使用。

- Gart

---

请注意，有两个不同版本的（非标准）std::hash_map。我会使用std::tr1::unordered_map，它将成为下一个标准版本的std::unordered_map。 - sbi

std::hash_map是SGI的扩展。它也可以在G++中使用，但在不同的命名空间(__gnu_cxx)中。 - Michael Ekstrand

但也有一个Dinkumware版本。（我认为它现在在stdext命名空间中或类似的位置，但它曾经在std命名空间中，因此他们的库中存在这样的版本。） - sbi

Answer 2

boost::unordered_map 可能是目前最好的、最广泛可移植的解决方案，如果你手头上没有TR1实现。

- Kylotan

Answer 3

如果您正在寻找现成的实现，除了STL/TR1和Boost哈希映射之外，还有google-sparsehash（它包含两种实现-一种优化了空间，另一种优化了速度）。

如果想要编写自己的代码，则可以将GetHashCode实现为一个单独的函数对象。

template < typename TKey, typename TValue, typename THash = someDefaultHash<TKey> >
class Dictionary
{
public:
   void Add(TKey key, TVal val){
       int hashCode = THash()(key);
       /* .... */
   }
}

这就是SGI的hash_map的实现方式。

- Cat Plus Plus

---

谢谢回复。这看起来很有前途。我会尝试一下。 - Navaneeth K N

Answer 4

假设您正在使用已安装功能包或服务包1的VS 2008，那么您就拥有TR1的实现，其中包括TR1 :: unordered_map。

另一方面，除非您真的创建了一个巨大的集合，否则std :: map将比您预期的更具竞争力。在我的测试中，这两个容器几乎是平手的，而且std :: map经常会更快。

- Jerry Coffin

---

事实上，一个 std::vector<std::pair<K,V> > 经常与一个 std::map<K,V> 竞争。我认为 Meyers 的 "Effective STL" 书中有一项内容涉及此问题（http://www.amazon.com/gp/product/0321334876）。 - sbi

有一种方法，但只适用于特定情况下的竞争。为了快速查找，向量必须被排序。如果事情按阶段进行，那么它可以很好地工作，您可以收集所有数据，然后对其进行排序，然后进行搜索（但很少在排序后插入或删除）。如果您混合插入、删除和搜索，则类似于 map 的东西更好。 - Jerry Coffin

@Jerry：是的，你总结得非常好。 - sbi

Answer 5

也许可以使用 std::hash_map？

请注意，这不是标准STL库规范的一部分，但通常可用。它在MS库、SGI库（如链接所示）和STLport中都有。

- Skizz

---

虽然不是真正的标准，但过去5年中几乎每个编译器都实现了一个（尽管MSVC和G++具有略微不同的语义）。首选应该是unordered_map或等效的boost容器。 - Joe

Answer 6

在C++中，您需要传递一个包含哈希函数作为类型参数的函数对象类型到模板中。

- Pete Kirkham