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

12 :32
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — meet the complexity requirements. 33/10000 · 33
13 :33
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — There are also the restrictions on when iterators can be invalidated. Since 75/10000 · 75
14 :34
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — open addressing degrades badly when there are a high number of collisions the restrictions could prevent a rehash when it's really needed. The maximum load factor could be set to a fairly low value to work around this - but the standard requires that it is initially set to 1.0. 278/10000 · 278
15 :38
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — And since the standard is written with a eye towards closed 59/10000 · 59
16 :39
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — addressing, users will be surprised if the performance doesn't reflect that. 76/10000 · 76
17 :41
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — So closed addressing is used. 29/10000 · 29
18 :43
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Number of Buckets 17/10000 · 17
19 :45
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — There are two popular methods for choosing the number of buckets in a hash table. One is to have a prime number of buckets, another is to use a power of 2. 155/10000 · 155
20 :49
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Using a prime number of buckets, and choosing a bucket by using the modulus of the hash function's result will usually give a good result. The downside is that the required modulus operation is fairly expensive. This is what the containers used to do in most cases. 265/10000 · 265
21 :54
	English ↹ ↵ NBS … “ ” ‘ ’ ﹙-﹚ ‐ – — Using a power of 2 allows for much quicker selection of the bucket to use, but at the expense of losing the upper bits of the hash value. For some specially designed hash functions it is possible to do this and still get a good result but as the containers can take arbitrary hash functions this can't be relied on. 315/10000 · 315
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