1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Implementation Rationale</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../unordered.html" title="Chapter 33. Boost.Unordered">
<link rel="prev" href="compliance.html" title="C++11 Compliance">
<link rel="next" href="changes.html" title="Change Log">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="compliance.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="changes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="unordered.rationale"></a><a class="link" href="rationale.html" title="Implementation Rationale">Implementation Rationale</a>
</h2></div></div></div>
<p>
The intent of this library is to implement the unordered containers in the
draft standard, so the interface was fixed. But there are still some implementation
decisions to make. The priorities are conformance to the standard and portability.
</p>
<p>
The <a href="http://en.wikipedia.org/wiki/Hash_table" target="_top">wikipedia article
on hash tables</a> has a good summary of the implementation issues for
hash tables in general.
</p>
<h3>
<a name="unordered.rationale.h0"></a>
<span><a name="unordered.rationale.data_structure"></a></span><a class="link" href="rationale.html#unordered.rationale.data_structure">Data
Structure</a>
</h3>
<p>
By specifying an interface for accessing the buckets of the container the standard
pretty much requires that the hash table uses chained addressing.
</p>
<p>
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 a some serious problems with this:
</p>
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
The draft standard requires that pointers to elements aren't invalidated,
so 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.
</li>
<li class="listitem">
Local iterators would be very inefficient and may not be able to meet the
complexity requirements.
</li>
<li class="listitem">
There are also the restrictions on when iterators can be invalidated. Since
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.
</li>
<li class="listitem">
And since the standard is written with a eye towards chained addressing,
users will be surprised if the performance doesn't reflect that.
</li>
</ul></div>
<p>
So chained addressing is used.
</p>
<h3>
<a name="unordered.rationale.h1"></a>
<span><a name="unordered.rationale.number_of_buckets"></a></span><a class="link" href="rationale.html#unordered.rationale.number_of_buckets">Number
of Buckets</a>
</h3>
<p>
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.
</p>
<p>
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.
</p>
<p>
Using a power of 2 allows for much quicker selection of the bucket to use,
but at the expense of loosing 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.
</p>
<p>
To avoid this a transformation could be applied to the hash function, for an
example see <a href="http://www.concentric.net/~Ttwang/tech/inthash.htm" target="_top">Thomas
Wang's article on integer hash functions</a>. Unfortunately, a transformation
like Wang's requires knowledge of the number of bits in the hash value, so
it isn't portable enough. This leaves more expensive methods, such as Knuth's
Multiplicative Method (mentioned in Wang's article). These don't tend to work
as well as taking the modulus of a prime, and the extra computation required
might negate efficiency advantage of power of 2 hash tables.
</p>
<p>
So, this implementation uses a prime number for the hash table size.
</p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel
James<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="compliance.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../unordered.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="changes.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
