简介
哈希表 是极其流行的计算机数据结构，几乎可以在任何编程语言中以某种形式找到。虽然其他关联结构（例如 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 以支持该类型，或使用您自己的自定义相等谓词和哈希函数。 有关更多详细信息，请参见 相等谓词和哈希函数 部分。