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

Question

我知道STL有一个HashMap API，但是我找不到任何好的和详细的文档以及好的例子。

欢迎提供好的例子。

- user855

---

你是在问关于 C++1x 的 hash_map，还是 std::map？ - philant

当C++开发者需要类似于java.util.HashMap的东西时，他们通常会使用什么？如果有标准化方法，请提供；否则提供最佳的非标准库。 - user855

Answer 1

标准库包含有序和无序映射（std::map和std::unordered_map）容器。在有序映射（std::map）中，元素按键排序，插入和访问的时间复杂度为O(log n)。通常，标准库内部使用红黑树来实现有序映射。但这只是一个实现细节。在无序映射（std::unordered_map）中，插入和访问的时间复杂度为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
键：hello 值：23

如果您需要容器中的排序，并且可以接受 O(log n) 的运行时间，则只需使用 std::map。

否则，如果您真的需要哈希表（O(1) 插入/访问），请查看 std::unordered_map，它具有类似于 std::map 的 API（例如，在上面的示例中，您只需搜索并替换 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以获得更好的可移植性。

- maxschlepzig

---

虽然标准库没有哈希表容器，但几乎所有的实现都以某种形式包含 SGI STL 中的 hash_map。 - James McNellis

@JamesMcNellis 建议使用 unordered_map 还是 hash_map 来实现 HashMap？ - Shameel Mohamed

@ShameelMohamed，2017年，距离C++11已经过去了6年，现在很难找到不提供unordered_map的STL。因此，考虑非标准的hash_map是没有必要的。 - maxschlepzig

Answer 2

hash_map 是一个旧的、非标准化的版本，为了标准化而称为 unordered_map（最初在 TR1 中，自 C++11 以来已包括在标准中）。顾名思义，它与 std::map 主要的不同之处在于它是无序的。例如，如果你通过从 begin() 到 end() 遍历一个 map，你会按键顺序获得项目，但是如果你通过从 begin() 到 end() 遍历一个 unordered_map，你会以更或多或少的任意顺序获得项目。

通常希望 unordered_map 具有固定复杂度。也就是说，插入、查找等操作通常需要基本上固定的时间，而与表中有多少项无关。而 std::map 的复杂度是对存储项数取对数的 -- 这意味着插入或检索一项的时间会增长，但随着 map 变大，增长速度相当缓慢。例如，如果查找 1000000 个项中的一个需要 1 微秒，那么查找 2000000 个项中的一个将需要大约 2 微秒、4000000 个项中的一个将需要 3 微秒、8000000 个项中的一个将需要 4 微秒等。

从实际角度来看，这并不是整个故事的全部。一个简单的哈希表本质上具有固定的大小。使其适应通用容器的可变大小需求有些棘手。因此，可能会相对较慢地执行(潜在地)增长表格大小的操作（例如插入）（也就是说，大多数操作都是相当快速的，但周期性地会有一个操作较慢）。查询操作（无法更改表格的大小）通常要快得多。因此，大多数基于哈希的表在您需要做很多查询而不是插入时表现最佳。对于需要插入大量数据，然后迭代一次来检索结果（例如，在文件中计算唯一单词的数量），std::map 的速度可能会与哈希表差不多，甚至更快（但是，再次说明，计算复杂度是不同的，所以这也可能取决于文件中唯一单词的数量）。

---

^{1 当创建映射时，顺序由第三个模板参数定义，默认为 std::less<T>。}

- Jerry Coffin

---

我知道我的回答是在9年后发布的，但是...您是否有提到无序映射可以缩小大小的文档链接？通常，std集合只会增长。 此外，如果您插入了大量数据，但事先知道您将插入多少个键，您可以在创建时指定地图的大小，这基本上使调整大小成本为零（因为不会有任何调整）。 - Zonko

@Zonko：抱歉，我在被问到时没有注意到这个问题。据我所知，unordered_map除非调用'rehash'，否则不会缩小。当您调用'rehash'时，您为表格指定一个大小。该大小将被使用，除非这样做会超过表格的指定最大负载因子（在这种情况下，大小将自动增加以保持负载因子在限制范围内）。 - Jerry Coffin

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

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

- Jerry Miller

---

我必须说，这个例子在C++中是一个非常糟糕的实践。您正在使用强类型语言并通过使用 void* 来破坏它。首先，没有理由包装 unordered_map，因为它是标准库的一部分，将会降低代码可维护性。其次，如果一定要包装它，就请使用模板，因为那正是模板的用途所在。 - Guy

强类型？你可能指的是静态类型。他能够从const char指针到void无声转换使得C++是静态类型但不是强类型。有类型，但编译器除非你启用某些晦涩的标志，否则不会说一句话。该标志很可能不存在。 - user11877195

Answer 4

证据表明在GCC stdlibc++ 6.4中，std::unordered_map使用哈希映射。

这在这里提到过：https://dev59.com/8XA65IYBdhLWcg3w4C6j#3578247但在下面的答案中：What data structure is inside std::map in C++?我通过以下方式进一步证明了GCC stdlibc++ 6.4实现中的情况:

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

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

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

这个回答解决了问题：C++ unordered_map using a custom class type as the key

摘录：相等：

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

}

- Ciro Santilli OurBigBook.com

Answer 5

对于我们这些试图弄清楚如何在仍使用标准模板的情况下哈希自己的类的人来说，有一个简单的解决方案：

1. 在您的类中，您需要定义一个等号运算符重载 ==。如果您不知道如何做到这一点，GeeksforGeeks有一个很好的教程 https://www.geeksforgeeks.org/operator-overloading-c/ 2. 在标准命名空间下，声明一个模板结构体称为哈希，以您的类名作为类型（见下文）。我发现了一篇很棒的博客文章，它还展示了使用异或和位移计算哈希的示例，但这超出了本问题的范围，但它还包括有关如何使用哈希函数的详细说明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
      ...
    }
  };

}

3. 因此，要使用您的新哈希函数实现哈希表，您只需像往常一样创建一个std::map或std::unordered_map，并将my_type用作键，标准库将自动使用您在步骤2中定义的哈希函数来哈希您的键。

#include <unordered_map>

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

- iggy12345

---

或者查看这个关于哈希用户定义类的Stackoverflow问题。 - maxschlepzig