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

What is the best way to use a HashMap in C++?

提问by user855

I know that STL has a HashMap API, but I cannot find any good and thorough documentation with good examples regarding this.

我知道 STL 有一个 HashMap API，但我找不到任何关于这方面的好例子的好的和彻底的文档。

Any good examples will be appreciated.

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

回答by maxschlepzig

The standard library includes the ordered and the unordered map (std::mapand std::unordered_map) containers. In an ordered map the elements are sorted by the key, insert and access is in O(log n). Usually the standard library internally uses red black treesfor ordered maps. But this is just an implementation detail. In an unordered map insert and access is in O(1). It is just another name for a hashtable.

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

An example with (ordered) std::map:

一个带有 (ordered) 的例子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;
}

Output:

输出：

23
Key: hello Value: 23

If you need ordering in your container and are fine with the O(log n) runtime then just use std::map.

如果您需要在容器中进行排序并且对 O(log n) 运行时没问题，那么只需使用std::map.

Otherwise, if you really need a hash-table (O(1) insert/access), check out std::unordered_map, which has a similar to std::mapAPI (e.g. in the above example you just have to search and replace mapwith unordered_map).

否则，如果您确实需要一个哈希表（O(1) 插入/访问），请查看std::unordered_map，它具有类似于std::mapAPI（例如，在上面的示例中，您只需搜索并替换map为unordered_map）。

The unordered_mapcontainer was introduced with the C++11 standardrevision. Thus, depending on your compiler, you have to enable C++11 features (e.g. when using GCC 4.8 you have to add -std=c++11to the CXXFLAGS).

该unordered_map容器是在C++11 标准修订版中引入的。因此，根据您的编译器，您必须启用 C++11 功能（例如，当使用 GCC 4.8 时，您必须添加-std=c++11到 CXXFLAGS）。

Even before the C++11 release GCC supported unordered_map- in the namespace std::tr1. Thus, for old GCC compilers you can try to use it like this:

甚至在 C++11 版本之前支持 GCC unordered_map- 在命名空间中std::tr1。因此，对于旧的 GCC 编译器，您可以尝试像这样使用它：

#include <tr1/unordered_map>

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

It is also part of boost, i.e. you can use the corresponding boost-headerfor better portability.

它也是 boost 的一部分，即您可以使用相应的boost-header以获得更好的可移植性。

回答by Jerry Coffin

A hash_mapis an older, unstandardized version of what for standardization purposes is called an unordered_map(originally in TR1, and included in the standard since C++11). As the name implies, it's different from std::mapprimarily in being unordered -- if, for example, you iterate through a map from begin()to end(), you get items in order by key¹, but if you iterate through an unordered_mapfrom begin()to end(), you get items in a more or less arbitrary order.

Ahash_map是一个较旧的非标准化版本，用于标准化目的称为 an unordered_map（最初在 TR1 中，自 C++11 起包含在标准中）。顾名思义，它与std::map主要的无序不同——例如，如果您遍历映射 from begin()to end()，则按键¹按顺序获取项目，但是如果遍历unordered_mapfrom begin()to end()，您将获取项目或多或少的任意顺序。

An unordered_mapis normally expected to have constant complexity. That is, an insertion, lookup, etc., typically takes essentially a fixed amount of time, regardless of how many items are in the table. An std::maphas complexity that's logarithmic on the number of items being stored -- which means the time to insert or retrieve an item grows, but quite slowly, as the map grows larger. For example, if it takes 1 microsecond to lookup one of 1 million items, then you can expect it to take around 2 microseconds to lookup one of 2 million items, 3 microseconds for one of 4 million items, 4 microseconds for one of 8 million items, etc.

Anunordered_map通常预期具有恒定的复杂性。也就是说，无论表中有多少项，插入、查找等通常都需要固定的时间。An 的std::map复杂性是存储的项目数量的对数——这意味着插入或检索项目的时间会增加，但随着地图变大，速度非常缓慢。例如，如果查找 100 万个项目中的一个需要 1 微秒，那么您可以预期查找 200 万个项目中的一个需要大约 2 微秒，400 万个项目中的一个需要 3 微秒，800 万个中的一个需要 4 微秒物品等。

From a practical viewpoint, that's not really the whole story though. By nature, a simple hash table has a fixed size. Adapting it to the variable-size requirements for a general purpose container is somewhat non-trivial. As a result, operations that (potentially) grow the table (e.g., insertion) are potentially relatively slow (that is, most are fairly fast, but periodically one will be much slower). Lookups, which cannot change the size of the table, are generally much faster. As a result, most hash-based tables tend to be at their best when you do a lot of lookups compared to the number of insertions. For situations where you insert a lot of data, then iterate through the table once to retrieve results (e.g., counting the number of unique words in a file) chances are that an std::mapwill be just as fast, and quite possibly even faster (but, again, the computational complexity is different, so that can also depend on the number of unique words in the file).

从实际的角度来看，这并不是故事的全部。本质上，简单的哈希表具有固定的大小。使其适应通用容器的可变大小要求有点重要。结果，（可能）增加表的操作（例如，插入）可能相对较慢（即，大多数操作相当快，但周期性的操作会慢得多）。无法更改表大小的查找通常要快得多。因此，与插入次数相比，当您进行大量查找时，大多数基于哈希的表往往处于最佳状态。对于插入大量数据，然后遍历表一次以检索结果（例如，计算文件中唯一单词的数量）的情况std::map将同样快，甚至可能更快（但是，同样，计算复杂度是不同的，因此这也可能取决于文件中唯一单词的数量）。

---

---

^{1Where the order is defined by the third template parameter when you create the map, std::less<T>by default.}

^{1std::less<T>默认情况下，顺序由创建地图时的第三个模板参数定义。}

回答by Jerry Miller

Here's a more complete and flexible example that doesn't omit necessary includes to generate compilation errors:

这是一个更完整和灵活的示例，它没有省略生成编译错误所需的包含：

#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");
}

Still not particularly useful for keys, unless they are predefined as pointers, because a matching value won't do! (However, since I normally use strings for keys, substituting "string" for "const void *" in the declaration of the key should resolve this problem.)

对于键仍然不是特别有用，除非它们被预定义为指针，因为匹配的值是行不通的！（但是，由于我通常使用字符串作为键，在键的声明中用“string”代替“const void *”应该可以解决这个问题。）

回答by iggy12345

For those of us trying to figure out how to hash our own classes whilst still using the standard template, there is a simple solution:

对于我们这些试图弄清楚如何在仍然使用标准模板的同时散列我们自己的类的人来说，有一个简单的解决方案：

1. In your class you need to define an equality operator overload ==. If you don't know how to do this, GeeksforGeeks has a great tutorial https://www.geeksforgeeks.org/operator-overloading-c/

2. Under the standard namespace, declare a template struct called hash with your classname as the type (see below). I found a great blogpost that also shows an example of calculating hashes using XOR and bitshifting, but that's outside the scope of this question, but it also includes detailed instructions on how to accomplish using hash functions as well https://prateekvjoshi.com/2014/06/05/using-hash-function-in-c-for-user-defined-classes/

1. 在您的类中，您需要定义一个相等运算符重载==。如果你不知道怎么做，GeeksforGeeks 有一个很棒的教程https://www.geeksforgeeks.org/operator-overloading-c/

2. 在标准命名空间下，声明一个名为 hash 的模板结构，使用您的类名作为类型（见下文）。我发现了一篇很棒的博客文章，其中还展示了使用 XOR 和位移位计算哈希的示例，但这超出了本问题的范围，但它还包含有关如何使用哈希函数完成的详细说明https://prateekvjoshi.com/ 2014/06/05/using-hash-function-in-c-for-user-defined-classes/

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

1. So then to implement a hashtable using your new hash function, you just have to create a std::mapor std::unordered_mapjust like you would normally do and use my_typeas the key, the standard library will automatically use the hash function you defined before (in step 2) to hash your keys.

3. 因此，要使用新的哈希函数实现哈希表，您只需要创建一个std::maporstd::unordered_map就像您通常做的那样并my_type用作键，标准库将自动使用您之前（在第 2 步中）定义的哈希函数进行哈希你的钥匙。

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}