Exit Zen
1
:3
English
:idprefix: rationale_
21/210 · 21
2
:5
English
= Implementation Rationale
8/260 · 26
3
:7
English
Closed-addressing Containers
5/280 · 28
4
:9
English
`boost::unordered_[multi]set` and `boost::unordered_[multi]map` adhere to the standard requirements for unordered associative containers, so the interface was fixed. But there are still some implementation decisions to make. The priorities are conformance to the standard and portability.
136/2880 · 288
5
:15
English
The http://en.wikipedia.org/wiki/Hash_table[Wikipedia article on hash tables^] has a good summary of the implementation issues for hash tables in general.
74/1540 · 154
6
:18
English
Data Structure
4/140 · 14
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.
36/1470 · 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:
61/2050 · 205
9
:27
English
The standard requires that pointers to elements aren't invalidated, so
19/700 · 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.
56/1800 · 180
11
:31
English
Local iterators would be very inefficient and may not be able to
19/640 · 64
12
:32
English
meet the complexity requirements.
8/330 · 33
13
:33
English
There are also the restrictions on when iterators can be invalidated. Since
22/750 · 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.
83/2780 · 278
15
:38
English
And since the standard is written with a eye towards closed
19/590 · 59
16
:39
English
addressing, users will be surprised if the performance doesn't reflect that.
20/760 · 76
17
:41
English
So closed addressing is used.
10/290 · 29
18
:43
English
Number of Buckets
3/170 · 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.
43/1550 · 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.
73/2650 · 265