C++ STL无序容器中的哈希容器究竟是什么神奇的存在？

本文共计1483个文字，预计阅读时间需要6分钟。

继承map、multimap、set、multiset等关联式容器之后，从本节课开始，再讲解一类特殊的关联式容器。它们通常被称为无序容器、哈希容器或无序关联容器。

注意，无序容器是C++11标准才开始支持的。

继 map、multimap、set、multiset 关联式容器之后，从本节开始，再讲解一类“特殊”的关联式容器，它们常被称为“无序容器”、“哈希容器”或者“无序关联容器”。

注意，无序容器是 C++ 11 标准才正式引入到 STL 标准库中的，这意味着如果要使用该类容器，则必须选择支持 C++ 11 标准的编译器。

和关联式容器一样，无序容器也使用键值对（pair 类型）的方式存储数据。不过，本教程将二者分开进行讲解，因为它们有本质上的不同：

• 关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
• 无序容器的底层实现采用的是哈希表的存储结构。

C++ STL 底层采用哈希表实现无序容器时，会将所有数据存储到一整块连续的内存空间中，并且当数据存储位置发生冲突时，解决方法选用的是“链地址法”（又称“开链法”）。