[#intro]
= 引言

:idprefix: intro_ :cpp: C++

https://en.wikipedia.org/wiki/Hash_table[哈希表] 是一种极其流行的计算机数据结构，几乎在所有编程语言中都能找到其不同形式的存在。红黑树（在 C{plus}{plus} 中被 `std::set` 和 `std::map` 使用）等其他关联结构在插入和查找操作上具有对数时间复杂度，但哈希表若配置得当，这些操作的平均时间复杂度可达到常数级别，并且通常速度更快。

C{plus}{plus}11 标准引入了__无序关联容器__ `std::unordered++_++set` 、 `std::unordered++_++map` 、 `std::unordered++_++multiset` 和 `std::unordered++_++multimap` ，但针对哈希表的研究并未止步：CPU架构的进步（如更强大的缓存、 https://en.wikipedia.org/wiki/Single_instruction,_multiple_data[SIMD] 指令集以及日益普及的 https://en.wikipedia.org/wiki/Multi-core_processor[多核处理器]）为改进基于哈希的数据结构创造了新的可能，这些新应用场景已远超 2011 年标准所定义的无序关联容器的能力范围。

Boost.Unordered 提供了一系列哈希容器，它们在标准符合性、性能表现和设计应用场景上各有不同：

[caption=, title='Table {counter:table-counter}. Boost.Unordered containers']
[cols="1,1,.^1", frame=all, grid=all]
|===
^h| ^h|*基于节点* ^h|*扁平*

^.^h|*Closed addressing* ^m| boost::unordered_set + boost::unordered_map + boost::unordered_multiset + boost::unordered_multimap ^|

^.^h|*开放寻址法* ^m| boost::unordered_node_set + boost::unordered_node_map ^m| boost::unordered_flat_set + boost::unordered_flat_map

^.^h|*并发* ^| `boost::concurrent_node_set` + `boost::concurrent_node_map` ^| `boost::concurrent_flat_set` + `boost::concurrent_flat_map`

|===

* **闭寻址容器**完全符合C{plus}{plus}无序关联容器规范，
并在标准接口的技术约束范围内提供了业界领先的运行性能。
* **开放寻址容器**采用了更高效的数据结构与算法
（典型场景下性能提升2倍以上），同时为了适配实现方案而对标准接口做了细微调整。该类容器包含两种变体：*扁平式*（最快）与**基于节点式**，后者在重新哈希时能保持指针稳定性，但性能会有所下降。
* 最后，**并发容器**专为高性能多线程场景设计与实现，
其接口与常规C{plus}{plus}容器存在根本性差异。该系列同时提供扁平与基于节点两种变体。

Boost.Unordered 中的所有 set 和 map 分别与 `std::unordered_set` 和 `std::unordered_map` 类似的方式进行实例化：

[source,c++]
----
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 使用 link:../../../../container_hash/index.html[boost::hash^]，它还支持其他一些类型，包括标准容器。要使用这些方法不支持的任意类型，用户必须扩展 Boost.Hash 以支持该类型，或者使用自定义的相等谓词和哈希函数。更多详情请参见 xref:hash_equality.adoc#hash_equality[相等谓词与哈希函数] 一节。