介绍
哈希表是非常流行的数据结构，几乎存在于所有编程语言中。而其他关联结构，如红黑树（C++ 中的 std::set 和 std::map 所使用的），其插入和查找的时间复杂度为对数级别，而哈希表（如果配置得当）平均而言可在常数时间内完成这些操作，并且通常快得多。
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 以支持该类型，或使用自己的自定义相等谓词和哈希函数。有关更多详细信息，请参阅相等谓词和哈希函数部分。