Exit Zen
2
:4
English
= Basics of Hash Tables
7/230 · 23
3
:6
English
The containers are made up of a number of _buckets_, each of which can contain any number of elements. For example, the following diagram shows a `xref:reference/unordered_set.adoc#unordered_set[boost::unordered_set]` with 7 buckets containing 5 elements, `A`, `B`, `C`, `D` and `E` (this is just for illustration, containers will typically have more buckets).
180/3600 · 360
4
:11
English
image::buckets.png[]
20/200 · 20
5
:13
English
In order to decide which bucket to place an element in, the container applies the hash function, `Hash`, to the element's key (for sets the key is the whole element, but is referred to as the key so that the same terminology can be used for sets and maps). This returns a value of type `std::size_t`. `std::size_t` has a much greater range of values then the number of buckets, so the container applies another transformation to that value to choose a bucket to place the element in.
143/4830 · 483
6
:20
English
Retrieving the elements for a given key is simple. The same process is applied to the key to find the correct bucket. Then the key is compared with the elements in the bucket to find any elements that match (using the equality predicate `Pred`). If the hash function has worked well the elements will be evenly distributed amongst the buckets so only a small number of elements will need to be examined.
108/4030 · 403
7
:27
English
There is xref:hash_equality.adoc#hash_equality[more information on hash functions and equality predicates in the next section].
66/1270 · 127
8
:30
English
You can see in the diagram that `A` & `D` have been placed in the same bucket. When looking for elements in this bucket up to 2 comparisons are made, making the search slower. This is known as a *collision*. To keep things fast we try to keep collisions to a minimum.
89/2670 · 267
9
:35
English
If instead of `boost::unordered_set` we had used `xref:reference/unordered_flat_set.adoc[boost::unordered_flat_set]`, the diagram would look as follows:
110/1520 · 152
10
:38
English
image::buckets-oa.png[]
23/230 · 23
11
:40
English
In open-addressing containers, buckets can hold at most one element; if a collision happens (like is the case of `D` in the example), the element uses some other available bucket in the vicinity of the original position. Given this simpler scenario, Boost.Unordered open-addressing containers offer a very limited API for accessing buckets.
110/3400 · 340
:48
:48
English
2+^h| *All containers* h|*Method* h|*Description*
26/490 · 49
13
:51
English
`size_type bucket_count() const`
32/320 · 32
14
:51
English
The number of buckets.
5/220 · 22
15
:54
English
2+^h| *Closed-addressing containers only* h|*Method* h|*Description*
29/680 · 68
16
:57
English
`size_type max_bucket_count() const`
36/360 · 36
17
:57
English
An upper bound on the number of buckets.
7/400 · 40
18
:57
English
`size_type bucket_size(size_type n) const`
42/420 · 42
19
:57
English
The number of elements in bucket `n`.
15/370 · 37
20
:57
English
`size_type bucket(key_type const& k) const`
47/430 · 43
21
:57
English
Returns the index of the bucket which would contain `k`.
17/560 · 56