创建通用哈希表 - C++

Question

.NET框架有一个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()方法,编译器将抛出错误.但是当key是基本类型(如int)时,此方法将不起作用.我可能需要通过提供GetHashCode来为int编写包装器.

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

有什么想法吗？

Answer 1

此外,检查C++技术报告1对std::tr1::unordered_map是否需要严格遵守C++标准.

实际上std::hash_map不是C++标准,但无论如何广泛使用.

Answer 2

如果你没有TR1实现,boost :: unordered_map可能是你目前最好和最广泛的可移植解决方案.