Boost Unordered Translation (zh_Hans)/Doc / Modules / Root / Pages / Rationale (adoc)

Exit Zen

7 :20

	English By specifying an interface for accessing the buckets of the container the standard pretty much requires that the hash table uses closed addressing. 147/10000 · 147
8 :23

	English It would be conceivable to write a hash table that uses another method. For example, it could use open addressing, and use the lookup chain to act as a bucket but there are some serious problems with this: 205/10000 · 205
9 :27

	English The standard requires that pointers to elements aren't invalidated, so 70/10000 · 70
10 :28

	English the elements can't be stored in one array, but will need a layer of indirection instead - losing the efficiency and most of the memory gain, the main advantages of open addressing. 180/10000 · 180
11 :31

	English Local iterators would be very inefficient and may not be able to 64/10000 · 64
12 :32

	English meet the complexity requirements. 33/10000 · 33
13 :33

	English There are also the restrictions on when iterators can be invalidated. Since 75/10000 · 75
14 :34

	English 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 And since the standard is written with a eye towards closed 59/10000 · 59
16 :39

	English addressing, users will be surprised if the performance doesn't reflect that. 76/10000 · 76
17 :41

	English So closed addressing is used. 29/10000 · 29
18 :43

	English Number of Buckets 17/10000 · 17
19 :45

	English 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 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 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 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 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 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 Open-addresing Containers 25/10000 · 25
26 :79

	English 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

Shortcut	Action
`?`	Open available keyboard shortcuts.
`Alt` + `Home`	Navigate to the first translation in the current search.
`Alt` + `End`	Navigate to the last translation in the current search.
`Alt` + `PageUp` or `Ctrl` + `↑` or `Alt` + `↑` or `Cmd` + `↑` or	Navigate to the previous translation in the current search.
`Alt` + `PageDown` or `Ctrl` + `↓` or `Alt` + `↓` or `Cmd` + `↓` or	Navigate to the next translation in the current search.
`Ctrl` + `Enter` or `Cmd` + `Enter`	Submit current form; this works the same as pressing Save and continue while editing translation.
`Ctrl` + `Shift` + `Enter` or `Cmd` + `Shift` +`Enter`	Unmark translation as Needing edit and submit it.
`Alt` + `Enter` or `Option` + `Enter`	Submit the string as a suggestion; this works the same as pressing Suggest while editing translation.
`Ctrl` + `E` or `Cmd` + `E`	Focus on translation editor.
`Ctrl` + `U` or `Cmd` + `U`	Focus on comment editor.
`Ctrl` + `M` or `Cmd` + `M`	Shows Automatic suggestions tab.
`Ctrl` + `1` to `Ctrl` + `9` or `Cmd` + `1` to `Cmd` + `9`	Copies placeable of a given number from source string.
`Ctrl` + `M` followed by `1` to `9` or `Cmd` + `M` followed by `1` to `9`	Copy the machine translation of a given number to current translation.
`Ctrl` + `I` followed by `1` to `9` or `Cmd` + `I` followed by `1` to `9`	Ignore one item in the list of failing checks.
`Ctrl` + `J` or `Cmd` + `J`	Shows the Nearby strings tab.
`Ctrl` + `S` or `Cmd` + `S`	Focus on search field.
`Ctrl` + `O` or `Cmd` + `O`	Copy the source string.
`Ctrl` + `Y` or `Cmd` + `Y`	Toggle the Needs editing checkbox.
`→`	Browse the next translation string.
`←`	Browse the previous translation string.