2. Boost Unordered Translation (zh_Hans)
3. Doc / Modules / Root / Pages / Structures (adoc)
4. English
5. Zen

20 :78
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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. 373/10000 · 373
21 :86
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::foa-metadata.png[align=center] 37/10000 · 37
22 :88
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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: 156/10000 · 156
23 :91
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — - 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. 284/10000 · 284
24 :97
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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: 594/10000 · 594
25 :106
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — - 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. 291/10000 · 291
26 :112
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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. 152/10000 · 152
27 :115
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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. 279/10000 · 279
28 :122
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::foa-metadata-interleaving.png[align=center] 50/10000 · 50
29 :124
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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]. 324/10000 · 324
30 :130
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Concurrent Containers 21/10000 · 21
31 :132
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — `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. 275/10000 · 275
32 :140
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — image::cfoa.png[align=center] 29/10000 · 29
33 :142
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Two levels of synchronization are used: 39/10000 · 39
34 :144
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Container level: A read-write mutex is used to control access from any operation 80/10000 · 80
35 :145
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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. 312/10000 · 312
36 :149
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Group level: Each 15-slot group is equipped with an 8-byte word containing: 75/10000 · 75
37 :150
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — ** A read-write spinlock for synchronized access to any element in the group. ** An atomic _insertion counter_ used for optimistic insertion as described below. 160/10000 · 160
38 :154
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — 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. 245/10000 · 245
39 :158
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Insertion uses the following _optimistic algorithm_: 52/10000 · 52