en	= Introduction
zh-hans	= 引言

en	:idprefix: intro_ :cpp: C++

en	link:https://en.wikipedia.org/wiki/Hash_table[Hash tables^] are extremely popular computer data structures and can be found under one form or another in virtually any programming language. Whereas other associative structures such as rb-trees (used in {cpp} by `std::set` and `std::map`) have logarithmic-time complexity for insertion and lookup, hash tables, if configured properly, perform these operations in constant time on average, and are generally much faster.
zh-hans	https://en.wikipedia.org/wiki/Hash_table[哈希表] 是一种极其流行的计算机数据结构，几乎在所有编程语言中都能找到其不同形式的存在。红黑树（在 C{plus}{plus} 中被 `std::set` 和 `std::map` 使用）等其他关联结构在插入和查找操作上具有对数时间复杂度，但哈希表若配置得当，这些操作的平均时间复杂度可达到常数级别，并且通常速度更快。

en	{cpp} introduced __unordered associative containers__ `std::unordered_set`, `std::unordered_map`, `std::unordered_multiset` and `std::unordered_multimap` in {cpp}11, but research on hash tables hasn't stopped since: advances in CPU architectures such as more powerful caches, link:https://en.wikipedia.org/wiki/Single_instruction,_multiple_data[SIMD] operations and increasingly available link:https://en.wikipedia.org/wiki/Multi-core_processor[multicore processors] open up possibilities for improved hash-based data structures and new use cases that are simply beyond reach of unordered associative containers as specified in 2011.
zh-hans	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 年标准所定义的无序关联容器的能力范围。

en	Boost.Unordered offers a catalog of hash containers with different standards compliance levels, performances and intented usage scenarios:
zh-hans	Boost.Unordered 提供了一系列哈希容器，它们在标准符合性、性能表现和设计应用场景上各有不同：

en	^h| ^h|*Node-based* ^h|*Flat*
zh-hans	^h| ^h|*基于节点* ^h|*扁平*

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

en	^.^h|*Open addressing* ^m| boost::unordered_node_set + boost::unordered_node_map ^m| boost::unordered_flat_set + boost::unordered_flat_map
zh-hans	^.^h|*开放寻址法* ^m| boost::unordered_node_set + boost::unordered_node_map ^m| boost::unordered_flat_set + boost::unordered_flat_map

en	^.^h|*Concurrent* ^| `boost::concurrent_node_set` + `boost::concurrent_node_map` ^| `boost::concurrent_flat_set` + `boost::concurrent_flat_map`
zh-hans	^.^h|*并发* ^| `boost::concurrent_node_set` + `boost::concurrent_node_map` ^| `boost::concurrent_flat_set` + `boost::concurrent_flat_map`

en	**Closed-addressing containers** are fully compliant with the C++ specification
zh-hans	**闭寻址容器**完全符合C{plus}{plus}无序关联容器规范，

en	for unordered associative containers and feature one of the fastest implementations in the market within the technical constraints imposed by the required standard interface.
zh-hans	并在标准接口的技术约束范围内提供了业界领先的运行性能。

en	**Open-addressing containers** rely on much faster data structures and algorithms
zh-hans	**开放寻址容器**采用了更高效的数据结构与算法

en	(more than 2 times faster in typical scenarios) while slightly diverging from the standard interface to accommodate the implementation. There are two variants: **flat** (the fastest) and **node-based**, which provide pointer stability under rehashing at the expense of being slower.
zh-hans	（典型场景下性能提升2倍以上），同时为了适配实现方案而对标准接口做了细微调整。该类容器包含两种变体：*扁平式*（最快）与**基于节点式**，后者在重新哈希时能保持指针稳定性，但性能会有所下降。

en	Finally, **concurrent containers** are designed and implemented to be used in high-performance
zh-hans	最后，**并发容器**专为高性能多线程场景设计与实现，

en	multithreaded scenarios. Their interface is radically different from that of regular C++ containers. Flat and node-based variants are provided.
zh-hans	其接口与常规C{plus}{plus}容器存在根本性差异。该系列同时提供扁平与基于节点两种变体。

en	All sets and maps in Boost.Unordered are instantiatied similarly as `std::unordered_set` and `std::unordered_map`, respectively:
zh-hans	Boost.Unordered 中的所有 set 和 map 分别与 `std::unordered_set` 和 `std::unordered_map` 类似的方式进行实例化：

en	Storing an object in an unordered associative container requires both a key equality function and a hash function. The default function objects in the standard containers support a few basic types including integer types, floating point types, pointer types, and the standard strings. Since Boost.Unordered uses link:../../../../container_hash/index.html[boost::hash^] it also supports some other types, including standard containers. To use any types not supported by these methods you have to extend Boost.Hash to support the type or use your own custom equality predicates and hash functions. See the xref:hash_equality.adoc#hash_equality[Equality Predicates and Hash Functions], section for more details.
zh-hans	在无序关联容器中存储对象需要同时提供键相等函数和哈希函数。标准容器中的默认函数对象支持若干基本类型，包括整数类型、浮点类型、指针类型以及标准字符串。由于 Boost.Unordered 使用 link:../../../../container_hash/index.html[boost::hash^]，它还支持其他一些类型，包括标准容器。要使用这些方法不支持的任意类型，用户必须扩展 Boost.Hash 以支持该类型，或者使用自定义的相等谓词和哈希函数。更多详情请参见 xref:hash_equality.adoc#hash_equality[相等谓词与哈希函数] 一节。