在C++中使用HashMap的最佳方法是什么？

Question

我知道STL有一个HashMap API,但我找不到任何好的和全面的文档,并提供了很好的例子.

任何好的例子将不胜感激.

Answer 1

标准库包括有序和无序映射(std::map和std::unordered_map)容器.在有序映射中,元素按键排序,插入和访问在O(log n)中.通常,标准库内部使用红黑树作为有序映射.但这只是一个实现细节.在无序映射中,插入和访问在O(1)中.它只是哈希表的另一个名称.

(有序)的例子std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

输出:

23
Key: hello Value: 23

如果您需要在容器中进行订购并且可以使用O(log n)运行时,那么只需使用std::map.

否则,如果你真的需要一个哈希表(O(1)插入/接入),退房std::unordered_map,其中有一个类似的std::mapAPI(例如,在你只需要搜索和替换上面的例子map用unordered_map).

该unordered_map容器是在C++ 11标准版本中引入的.因此,根据您的编译器,您必须启用C++ 11功能(例如,使用GCC 4.8时,您必须添加-std=c++11到CXXFLAGS).

甚至在C++ 11发布GCC支持之前unordered_map- 在命名空间中std::tr1.因此,对于旧的GCC编译器,您可以尝试使用它:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

它也是boost的一部分,即你可以使用相应的boost-header来获得更好的可移植性.

Answer 2

A hash_map是标准化目的的较旧的非标准化版本unordered_map(目前作为TR1的一部分提供,将包含在C++ 0x中).顾名思义,它是从不同的std::map主要是无序的-如果,例如,您可以通过地图迭代从begin()到end(),你的密钥,以便项目¹,但如果你通过一个循环unordered_map从begin()到end(),你在一个项目或多或少的任意顺序.

unordered_map通常预期An 具有恒定的复杂性.也就是说,插入,查找等基本上花费固定的时间量,而不管表中有多少项.对于std::map存储的项目数量具有对数的复杂性 - 这意味着插入或检索项目的时间增长,但随着地图变大,非常缓慢.例如,如果查找100万个项目中的一个需要1微秒,那么您可以预期查找200万个项目中的一个需要大约2微秒,400万个项目中的一个项目需要3微秒,800万个项目中的一个项目需要4微秒物品等

从实际的角度来看,这并非真正的整个故事.本质上,简单的哈希表具有固定的大小.使其适应通用容器的可变大小要求有点不重要.结果,(可能)增长或缩小表格(例如,插入和删除)的操作通常相对较慢.查找不能改变表的大小,通常要快得多.因此,当您进行大量查找和相对较少的插入和删除时,大多数基于散列的表往往处于最佳状态.对于插入大量数据的情况,然后遍历表一次以检索结果(例如,计算文件中唯一单词的数量),可能性std::map一样快,甚至可能更快.

¹std::less<T>默认情况下,在创建地图时,第三个模板参数定义了顺序.

Answer 3

这是一个更完整,更灵活的示例,不会忽略生成编译错误所必需的包含:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

对于键仍然没有特别有用,除非它们被预定义为指针,因为匹配值不会做!(但是,由于我通常使用字符串作为键,因此在键的声明中将"string"替换为"const void*"应解决此问题.)

Answer 4

std::unordered_map在GCC stdlibc ++ 6.4 中使用哈希映射的证据

在/sf/answers/250477321/中提到了此问题，但在以下答案中：在C ++中std :: map内包含什么数据结构？我已通过以下方式为GCC stdlibc ++ 6.4实现提供了进一步的证据：

• GDB一步调试进入类
• 性能特征分析

这是该答案中描述的性能特征图的预览：

如何使用自定义类和哈希函数 unordered_map

这个答案很明确：使用自定义类类型作为键的C ++ unordered_map

摘录：平等：

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

哈希函数：

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}