介绍
哈希表是非常流行的数据结构，几乎存在于所有编程语言的某种形式中。虽然其他关联结构，如 rb 树（C++ 中由 std::set 和 std::map 使用）在插入和查找时具有对数时间复杂度，但哈希表（如果配置得当）平均而言可以在常数时间内完成这些操作，并且通常速度快得多。
C++ 在 C++11 中引入了无序关联容器 std::unordered_set、std::unordered_map、std::unordered_multiset 和 std::unordered_multimap，但对哈希表的研究从未停止：CPU 架构的进步，如更强大的缓存、SIMD 操作和日益普及的多核处理器，为改进的基于哈希的数据结构和新用例提供了可能性，这些新用例是 2011 年标准中无序关联容器无法企及的。
Boost.Unordered 提供了一个哈希容器目录，具有不同的标准合规性级别、性能和预期的使用场景。
基于节点的 |
扁平化的 |
|
|---|---|---|
闭散列 |
|
|
开散列 |
|
|
并发 |
|
|
-
闭散列容器完全符合 C++ 标准对无序关联容器的规范，并在强制要求的标准接口的技术限制内，提供了市场上最快的实现之一。
-
开散列容器依赖于更快的数据结构和算法（在典型场景下快 2 倍以上），同时为了适应实现，略微偏离了标准接口。有两种变体：扁平化（最快）和基于节点，后者在重新哈希时提供指针稳定性，但速度较慢。
-
最后，并发容器被设计和实现为用于高性能多线程场景。它们的接口与常规 C++ 容器的接口截然不同。提供了扁平化和基于节点的变体。
Boost.Unordered 中的所有集合和映射都以类似于 std::unordered_set 和 std::unordered_map 的方式进行实例化。
namespace boost {
template <
class Key,
class Hash = boost::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class unordered_set;
// same for unordered_multiset, unordered_flat_set, unordered_node_set,
// concurrent_flat_set and concurrent_node_set
template <
class Key, class Mapped,
class Hash = boost::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<Key const, Mapped> > >
class unordered_map;
// same for unordered_multimap, unordered_flat_map, unordered_node_map,
// concurrent_flat_map and concurrent_node_map
}将对象存储在无序关联容器中需要键相等函数和哈希函数。标准容器中的默认函数对象支持一些基本类型，包括整数类型、浮点类型、指针类型和标准字符串。由于 Boost.Unordered 使用 boost::hash，它还支持其他一些类型，包括标准容器。要使用这些方法不支持的任何类型，您必须扩展 Boost.Hash 以支持该类型，或使用自己的自定义相等谓词和哈希函数。有关更多详细信息，请参阅 相等谓词和哈希函数 部分。