Zen

Translation

By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group's spinlock used.
66/2450 · 245

Sign in to save translations.

English Chinese (Simplified Han script) Actions
- 0 if the corresponding bucket is empty. - 1 to encode a special empty bucket called a _sentinel_, which is used internally to stop iteration when the container has been fully traversed. - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of the element.
- 0 表示对应的桶为空。
- 1 用于编码一种特殊的空桶，称为 _哨位桶_，在容器被完全遍历时内部用于停止迭代。
- 如果桶被占用，则存储从元素哈希值中获得的 _缩减哈希值_。
When looking for an element with hash value _h_, SIMD technologies such as https://en.wikipedia.org/wiki/SSE2[SSE2] and https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the 15 buckets with just a handful of CPU instructions: non-matching buckets can be readily discarded, and those whose reduced hash value matches need be inspected via full comparison with the corresponding element. If the looked-for element is not present, the overflow byte is inspected:
当查找一个哈希值为 _h_ 的元素时，可以使用诸如 https://en.wikipedia.org/wiki/SSE2[SSE2] 和 https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] 等 SIMD 技术，仅需少量 CPU 指令即可快速检查完整的元数据字，并在全部 15 个桶中寻找 _h_ 的缩减值：不匹配的桶可以迅速丢弃，而那些缩减哈希值匹配的桶则需要通过与对应元素的完整比较来进行检查。如果未找到目标元素，则检查溢出字节。
- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the element is not present). - If the bit is set to 1 (the group has been _overflowed_), further groups are checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and the process is repeated.
- 若位置 _h_ mod 8 的比特位为零，则查找终止（确认元素不存在）。 元素不存在）。 - 若该比特位为1（表示该组已__溢出__），则通过 https://en.wikipedia.org/wiki/Quadratic_probing[_二次探查法_] 检查后续组，并重复此过程。
Insertion is algorithmically similar: empty buckets are located using SIMD, and when going past a full group its corresponding overflow bit is set to 1.
插入操作的算法逻辑类似：通过 SIMD 技术定位空桶，当遍历到已满的组时，会将其对应的溢出位设置为 1。
In architectures without SIMD support, the logical layout stays the same, but the metadata word is codified using a technique we call _bit interleaving_: this layout allows us to emulate SIMD with reasonably good performance using only standard arithmetic and logical operations.
在不支持 SIMD 的架构中，逻辑布局保持不变，但元数据字采用一种称为 _位交错_ 的技术进行编码：这种布局允许我们仅使用标准算术和逻辑运算，以相当不错的性能来模拟 SIMD。
image::foa-metadata-interleaving.png[align=center]
image::foa-metadata-interleaving.png[align=center]
A more detailed description of Boost.Unordered's open-addressing implementation is given in an https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_open_addresing_containers[corresponding section].
关于 Boost.Unordered 开放寻址实现的更详细描述，请参阅 https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[外部文章]。有关实现原理的更多信息，请阅读 xref:rationale.adoc#rationale_open_addresing_containers[相应章节]。
Concurrent Containers
并发容器
`boost::concurrent_flat_set`/`boost::concurrent_node_set` and `boost::concurrent_flat_map`/`boost::concurrent_node_map` use the basic xref:structures.adoc#structures_open_addressing_containers[open-addressing layout] described above augmented with synchronization mechanisms.
`boost::concurrent_flat_set`/`boost::concurrent_node_set` 和 `boost::concurrent_flat_map`/`boost::concurrent_node_map` 使用了上述基本的 xref:structures.adoc#structures_open_addressing_containers[开放寻址布局]，并增加了同步机制。
image::cfoa.png[align=center]
image::cfoa.png[align=center]
Two levels of synchronization are used:
采用两级同步机制：
Container level: A read-write mutex is used to control access from any operation
容器层面：使用读写互斥锁来控制来自任何操作的访问。
to the container. Typically, such access is in read mode (that is, concurrent) even for modifying operations, so for most practical purposes there is no thread contention at this level. Access is only in write mode (blocking) when rehashing or performing container-wide operations such as swapping or assignment.
对容器的访问。通常情况下，即使是修改操作，此类访问也处于读模式（即并发的），因此在实际使用中，此层面几乎不会发生线程争用。仅在重哈希或执行交换、赋值等容器级操作时，访问才会处于写模式（阻塞）。
Group level: Each 15-slot group is equipped with an 8-byte word containing:
组级：每个包含15个槽位的组都配备一个8字节的字，其中包含：
** A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below.
- 一个读写自旋锁，用于同步对组内任何元素的访问。
- 一个原子 _插入计数器_，用于下文所述的乐观插入。
By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group's spinlock used.
通过使用原子操作访问组元数据，查找操作在（组级别）上是无锁的，直到需要与实际进行 SIMD 匹配的元素进行比较时才会使用组的自旋锁。
Insertion uses the following _optimistic algorithm_:
插入操作使用以下 _乐观算法_：
The value of the insertion counter for the initial group in the probe
探测起始组的插入计数器值
sequence is locally recorded (let's call this value `c0`).
序列会被本地记录（我们称此值为 `c0`）。
Lookup is as described above. If lookup finds no equivalent element,
查找过程如上所述。如果查找未找到等效元素，
search for an available slot for insertion successively locks/unlocks each group in the probing sequence.
则会依次对探测序列中的每个组进行加锁/解锁，以搜索可用于插入的空槽位。
When an available slot is located, it is preemptively occupied (its
当定位到一个可用槽位时，该槽位会被预先占用（其
reduced hash value is set) and the insertion counter is atomically incremented: if no other thread has incremented the counter during the whole operation (which is checked by comparing with `c0`), then we're good to go and complete the insertion, otherwise we roll back and start over.
缩减哈希值被设置），并且插入计数器被原子地递增：如果在整个操作过程中没有其他线程递增该计数器（通过与 `c0` 比较来检查），则插入操作可以顺利完成，否则将回滚并重新开始。
This algorithm has very low contention both at the lookup and actual insertion phases in exchange for the possibility that computations have to be started over if some other thread interferes in the process by performing a succesful insertion beginning at the same group. In practice, the start-over frequency is extremely small, measured in the range of parts per million for some of our benchmarks.
该算法在查找和实际插入阶段都具有非常低的争用，代价是如果其他线程在同一个组上成功执行了插入操作，则当前计算可能需要重新开始。在实际应用中，重新开始的频率极低，根据我们的一些基准测试，其量级在百万分之一以内。
For more information on implementation rationale, read the xref:rationale.adoc#rationale_concurrent_containers[corresponding section].
如需了解实现原理的更多内容，请参阅 xref:rationale.adoc#rationale_concurrent_containers [对应章节]。
English Chinese (Simplified Han script) Actions
As with all open-addressing containers, elements (or pointers to the element nodes in the case of `boost::unordered_node_set` and `boost::unordered_node_map`) are stored directly in the bucket array. This array is logically divided into 2^_n_^ _groups_ of 15 elements each. In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^ 16-byte words.
与所有开放寻址容器一样，元素（对于 `boost::unordered++_++node++_++set` 和 `boost::unordered++_++node++_++map`则是元素节点的指针）直接存储在桶数组中。 该数组在逻辑上被划分为 2^_n_^个组，每组包含 15个元素。 除桶数组外，还存在一个关联的__元数据数组__，其中包含 2^_n_^ 个 16 字节的字。
A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is:
一个元数据字被划分为 15 个 _h_~_i_~ 字节（每个字节对应一个关联的桶），以及一个 _溢出字节_（图中标记为 _ofw_）。_h_~_i_~ 的值计算方式如下：
- 0 if the corresponding bucket is empty. - 1 to encode a special empty bucket called a _sentinel_, which is used internally to stop iteration when the container has been fully traversed. - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of the element.
- 0 表示对应的桶为空。
- 1 用于编码一种特殊的空桶，称为 _哨位桶_，在容器被完全遍历时内部用于停止迭代。
- 如果桶被占用，则存储从元素哈希值中获得的 _缩减哈希值_。
When looking for an element with hash value _h_, SIMD technologies such as https://en.wikipedia.org/wiki/SSE2[SSE2] and https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the 15 buckets with just a handful of CPU instructions: non-matching buckets can be readily discarded, and those whose reduced hash value matches need be inspected via full comparison with the corresponding element. If the looked-for element is not present, the overflow byte is inspected:
当查找一个哈希值为 _h_ 的元素时，可以使用诸如 https://en.wikipedia.org/wiki/SSE2[SSE2] 和 https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] 等 SIMD 技术，仅需少量 CPU 指令即可快速检查完整的元数据字，并在全部 15 个桶中寻找 _h_ 的缩减值：不匹配的桶可以迅速丢弃，而那些缩减哈希值匹配的桶则需要通过与对应元素的完整比较来进行检查。如果未找到目标元素，则检查溢出字节。
- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the element is not present). - If the bit is set to 1 (the group has been _overflowed_), further groups are checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and the process is repeated.
- 若位置 _h_ mod 8 的比特位为零，则查找终止（确认元素不存在）。 元素不存在）。 - 若该比特位为1（表示该组已__溢出__），则通过 https://en.wikipedia.org/wiki/Quadratic_probing[_二次探查法_] 检查后续组，并重复此过程。
Insertion is algorithmically similar: empty buckets are located using SIMD, and when going past a full group its corresponding overflow bit is set to 1.
插入操作的算法逻辑类似：通过 SIMD 技术定位空桶，当遍历到已满的组时，会将其对应的溢出位设置为 1。
In architectures without SIMD support, the logical layout stays the same, but the metadata word is codified using a technique we call _bit interleaving_: this layout allows us to emulate SIMD with reasonably good performance using only standard arithmetic and logical operations.
在不支持 SIMD 的架构中，逻辑布局保持不变，但元数据字采用一种称为 _位交错_ 的技术进行编码：这种布局允许我们仅使用标准算术和逻辑运算，以相当不错的性能来模拟 SIMD。
A more detailed description of Boost.Unordered's open-addressing implementation is given in an https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article]. For more information on implementation rationale, read the xref:rationale.adoc#rationale_open_addresing_containers[corresponding section].
关于 Boost.Unordered 开放寻址实现的更详细描述，请参阅 https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[外部文章]。有关实现原理的更多信息，请阅读 xref:rationale.adoc#rationale_open_addresing_containers[相应章节]。
`boost::concurrent_flat_set`/`boost::concurrent_node_set` and `boost::concurrent_flat_map`/`boost::concurrent_node_map` use the basic xref:structures.adoc#structures_open_addressing_containers[open-addressing layout] described above augmented with synchronization mechanisms.
`boost::concurrent_flat_set`/`boost::concurrent_node_set` 和 `boost::concurrent_flat_map`/`boost::concurrent_node_map` 使用了上述基本的 xref:structures.adoc#structures_open_addressing_containers[开放寻址布局]，并增加了同步机制。
image::cfoa.png[align=center]
image::cfoa.png[align=center]
Two levels of synchronization are used:
采用两级同步机制：
Container level: A read-write mutex is used to control access from any operation
容器层面：使用读写互斥锁来控制来自任何操作的访问。
to the container. Typically, such access is in read mode (that is, concurrent) even for modifying operations, so for most practical purposes there is no thread contention at this level. Access is only in write mode (blocking) when rehashing or performing container-wide operations such as swapping or assignment.
对容器的访问。通常情况下，即使是修改操作，此类访问也处于读模式（即并发的），因此在实际使用中，此层面几乎不会发生线程争用。仅在重哈希或执行交换、赋值等容器级操作时，访问才会处于写模式（阻塞）。
Group level: Each 15-slot group is equipped with an 8-byte word containing:
组级：每个包含15个槽位的组都配备一个8字节的字，其中包含：
** A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below.
- 一个读写自旋锁，用于同步对组内任何元素的访问。
- 一个原子 _插入计数器_，用于下文所述的乐观插入。
By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group's spinlock used.
通过使用原子操作访问组元数据，查找操作在（组级别）上是无锁的，直到需要与实际进行 SIMD 匹配的元素进行比较时才会使用组的自旋锁。
Insertion uses the following _optimistic algorithm_:
插入操作使用以下 _乐观算法_：
sequence is locally recorded (let's call this value `c0`).
序列会被本地记录（我们称此值为 `c0`）。
search for an available slot for insertion successively locks/unlocks each group in the probing sequence.
则会依次对探测序列中的每个组进行加锁/解锁，以搜索可用于插入的空槽位。
reduced hash value is set) and the insertion counter is atomically incremented: if no other thread has incremented the counter during the whole operation (which is checked by comparing with `c0`), then we're good to go and complete the insertion, otherwise we roll back and start over.
缩减哈希值被设置），并且插入计数器被原子地递增：如果在整个操作过程中没有其他线程递增该计数器（通过与 `c0` 比较来检查），则插入操作可以顺利完成，否则将回滚并重新开始。
This algorithm has very low contention both at the lookup and actual insertion phases in exchange for the possibility that computations have to be started over if some other thread interferes in the process by performing a succesful insertion beginning at the same group. In practice, the start-over frequency is extremely small, measured in the range of parts per million for some of our benchmarks.
该算法在查找和实际插入阶段都具有非常低的争用，代价是如果其他线程在同一个组上成功执行了插入操作，则当前计算可能需要重新开始。在实际应用中，重新开始的频率极低，根据我们的一些基准测试，其量级在百万分之一以内。

Loading…

User avatar admin

Translation uploaded
By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group's spinlock used.
Insertion uses the following _optimistic algorithm_:通过使用原子操作访问组元数据，查找操作在（组级别）上是无锁的，直到需要与实际进行 SIMD 匹配的元素进行比较时才会使用组的自旋锁。
06/05/2026
User avatar admin

String added in the repository
By using atomic operations to access the group metadata, lookup is (group-level) lock-free up to the point where an actual comparison needs to be done with an element that has been previously SIMD-matched: only then is the group's spinlock used.
Insertion uses the following _optimistic algorithm_:
06/05/2026
Browse all string changes

Glossary

English Chinese (Simplified Han script)
No related strings found in the glossary.

String information

Flags
safe-html, strict-same
Unit identifier
52289
Source string location
:154
String age
06/05/2026
Last updated
06/06/2026
Source string age
06/05/2026
Translation file AsciiDoc file
doc/modules/ROOT/pages/structures_zh_Hans.adoc, string 38