1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<head> 4<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5<title>Implementation Rationale</title> 6<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css"> 7<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 8<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset"> 9<link rel="up" href="../unordered.html" title="Chapter 44. Boost.Unordered"> 10<link rel="prev" href="compliance.html" title="Standard Compliance"> 11<link rel="next" href="changes.html" title="Change Log"> 12</head> 13<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 14<table cellpadding="2" width="100%"><tr> 15<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td> 16<td align="center"><a href="../../../index.html">Home</a></td> 17<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td> 18<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 19<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 20<td align="center"><a href="../../../more/index.htm">More</a></td> 21</tr></table> 22<hr> 23<div class="spirit-nav"> 24<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> 25</div> 26<div class="section"> 27<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 28<a name="unordered.rationale"></a><a class="link" href="rationale.html" title="Implementation Rationale">Implementation Rationale</a> 29</h2></div></div></div> 30<p> 31 The intent of this library is to implement the unordered containers in the 32 draft standard, so the interface was fixed. But there are still some implementation 33 decisions to make. The priorities are conformance to the standard and portability. 34 </p> 35<p> 36 The <a href="http://en.wikipedia.org/wiki/Hash_table" target="_top">Wikipedia article 37 on hash tables</a> has a good summary of the implementation issues for 38 hash tables in general. 39 </p> 40<h3> 41<a name="unordered.rationale.h0"></a> 42 <span class="phrase"><a name="unordered.rationale.data_structure"></a></span><a class="link" href="rationale.html#unordered.rationale.data_structure">Data 43 Structure</a> 44 </h3> 45<p> 46 By specifying an interface for accessing the buckets of the container the standard 47 pretty much requires that the hash table uses chained addressing. 48 </p> 49<p> 50 It would be conceivable to write a hash table that uses another method. For 51 example, it could use open addressing, and use the lookup chain to act as a 52 bucket but there are some serious problems with this: 53 </p> 54<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 55<li class="listitem"> 56 The draft standard requires that pointers to elements aren't invalidated, 57 so the elements can't be stored in one array, but will need a layer of 58 indirection instead - losing the efficiency and most of the memory gain, 59 the main advantages of open addressing. 60 </li> 61<li class="listitem"> 62 Local iterators would be very inefficient and may not be able to meet the 63 complexity requirements. 64 </li> 65<li class="listitem"> 66 There are also the restrictions on when iterators can be invalidated. Since 67 open addressing degrades badly when there are a high number of collisions 68 the restrictions could prevent a rehash when it's really needed. The maximum 69 load factor could be set to a fairly low value to work around this - but 70 the standard requires that it is initially set to 1.0. 71 </li> 72<li class="listitem"> 73 And since the standard is written with a eye towards chained addressing, 74 users will be surprised if the performance doesn't reflect that. 75 </li> 76</ul></div> 77<p> 78 So chained addressing is used. 79 </p> 80<h3> 81<a name="unordered.rationale.h1"></a> 82 <span class="phrase"><a name="unordered.rationale.number_of_buckets"></a></span><a class="link" href="rationale.html#unordered.rationale.number_of_buckets">Number 83 of Buckets</a> 84 </h3> 85<p> 86 There are two popular methods for choosing the number of buckets in a hash 87 table. One is to have a prime number of buckets, another is to use a power 88 of 2. 89 </p> 90<p> 91 Using a prime number of buckets, and choosing a bucket by using the modulus 92 of the hash function's result will usually give a good result. The downside 93 is that the required modulus operation is fairly expensive. This is what the 94 containers do in most cases. 95 </p> 96<p> 97 Using a power of 2 allows for much quicker selection of the bucket to use, 98 but at the expense of losing the upper bits of the hash value. For some specially 99 designed hash functions it is possible to do this and still get a good result 100 but as the containers can take arbitrary hash functions this can't be relied 101 on. 102 </p> 103<p> 104 To avoid this a transformation could be applied to the hash function, for an 105 example see <a href="http://web.archive.org/web/20121102023700/http://www.concentric.net/~Ttwang/tech/inthash.htm" target="_top">Thomas 106 Wang's article on integer hash functions</a>. Unfortunately, a transformation 107 like Wang's requires knowledge of the number of bits in the hash value, so 108 it isn't portable enough to use as a default. It can applicable in certain 109 cases so the containers have a policy based implementation that can use this 110 alternative technique. 111 </p> 112<p> 113 Currently this is only done on 64 bit architectures, where prime number modulus 114 can be expensive. Although this varies depending on the architecture, so I 115 probably should revisit it. 116 </p> 117<p> 118 I'm also thinking of introducing a mechanism whereby a hash function can indicate 119 that it's safe to be used directly with power of 2 buckets, in which case a 120 faster plain power of 2 implementation can be used. 121 </p> 122</div> 123<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 124<td align="left"></td> 125<td align="right"><div class="copyright-footer">Copyright © 2003, 2004 Jeremy B. Maitin-Shepard<br>Copyright © 2005-2008 Daniel 126 James<p> 127 Distributed under the Boost Software License, Version 1.0. (See accompanying 128 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>) 129 </p> 130</div></td> 131</tr></table> 132<hr> 133<div class="spirit-nav"> 134<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> 135</div> 136</body> 137</html> 138
