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

22 :60
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — To avoid this a transformation could be applied to the hash function, for an example see http://web.archive.org/web/20121102023700/http://www.concentric.net/~Ttwang/tech/inthash.htm[Thomas Wang's article on integer hash functions^]. Unfortunately, a transformation like Wang's requires knowledge of the number of bits in the hash value, so it was only used when `size_t` was 64 bit. 382/10000 · 382
23 :66
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Since release 1.79.0, https://en.wikipedia.org/wiki/Hash_function#Fibonacci_hashing[Fibonacci hashing] is used instead. With this implementation, the bucket number is determined by using `(h * m) >> (w - k)`, where `h` is the hash value, `m` is `2^w` divided by the golden ratio, `w` is the word size (32 or 64), and `2^k` is the number of buckets. This provides a good compromise between speed and distribution. 412/10000 · 412
24 :73
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Since release 1.80.0, prime numbers are chosen for the number of buckets in tandem with sophisticated modulo arithmetic. This removes the need for "mixing" the result of the user's hash function as was used for release 1.79.0. 226/10000 · 226
25 :77
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Open-addresing Containers 25/10000 · 25
26 :79
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The C++ standard specification of unordered associative containers impose severe limitations on permissible implementations, the most important being that closed addressing is implicitly assumed. Slightly relaxing this specification opens up the possibility of providing container variations taking full advantage of open-addressing techniques. 344/10000 · 344
27 :85
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The design of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_map` has been guided by Peter Dimov's https://pdimov.github.io/articles/unordered_dev_plan.html[Development Plan for Boost.Unordered^]. We discuss here the most relevant principles. 292/10000 · 292
28 :89
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Hash Function 13/10000 · 13
29 :91
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Given its rich functionality and cross-platform interoperability, `boost::hash` remains the default hash function of open-addressing containers. As it happens, `boost::hash` for integral and other basic types does not possess the statistical properties required by open addressing; to cope with this, we implement a post-mixing stage: 334/10000 · 334
30 :97
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — {nbsp}{nbsp}{nbsp}{nbsp} _a_ <- _h_ *mul* _C_, + {nbsp}{nbsp}{nbsp}{nbsp} _h_ <- *high*(_a_) *xor* *low*(_a_), 110/10000 · 110
31 :100
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — where *mul* is an _extended multiplication_ (128 bits in 64-bit architectures, 64 bits in 32-bit environments), and *high* and *low* are the upper and lower halves of an extended word, respectively. In 64-bit architectures, _C_ is the integer part of 2^64^&#8725;https://en.wikipedia.org/wiki/Golden_ratio[_&phi;_], whereas in 32 bits _C_ = 0xE817FB2Du has been obtained from https://arxiv.org/abs/2001.05304[Steele and Vigna (2021)^]. 435/10000 · 435
32 :105
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — When using a hash function directly suitable for open addressing, post-mixing can be opted out of via a dedicated `link:../../../../container_hash/doc/html/hash.html#ref_hash_is_avalanchinghash[hash_is_avalanching]` trait. `boost::hash` specializations for string types are marked as avalanching. 296/10000 · 296
33 :109
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Platform Interoperability 25/10000 · 25
34 :111
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The observable behavior of `boost::unordered_flat_set`/`unordered_node_set` and `boost::unordered_flat_map`/`unordered_node_map` is deterministically identical across different compilers as long as their ``std::size_t``s are the same size and the user-provided hash function and equality predicate are also interoperable &#8212;this includes elements being ordered in exactly the same way for the same sequence of operations. 425/10000 · 425
35 :117
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Although the implementation internally uses SIMD technologies, such as https://en.wikipedia.org/wiki/SSE2[SSE2^] and https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(NEON)[Neon^], when available, this does not affect interoperatility. For instance, the behavior is the same for Visual Studio on an x64-mode Intel CPU with SSE2 and for GCC on an IBM s390x without any supported SIMD technology. 413/10000 · 413
36 :122
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Concurrent Containers 21/10000 · 21
37 :124
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — The same data structure used by Boost.Unordered open-addressing containers has been chosen also as the foundation of `boost::concurrent_flat_set`/`boost::concurrent_node_set` and `boost::concurrent_flat_map`/`boost::concurrent_node_map`: 237/10000 · 237
38 :128
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Open-addressing is faster than closed-addressing alternatives, both in non-concurrent and 89/10000 · 89
39 :129
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — concurrent scenarios. 21/10000 · 21
40 :130
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Open-addressing layouts are eminently suitable for concurrent access and modification 85/10000 · 85
41 :131
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — with minimal locking. In particular, the metadata array can be used for implementations of lookup that are lock-free up to the last step of actual element comparison. 166/10000 · 166