doc/html/hash/rationale.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Rationale</title>
   5 <link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
   7 <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
   8 <link rel="up" href="../hash.html" title="Chapter&#160;12.&#160;Boost.Functional/Hash">
   9 <link rel="prev" href="changes.html" title="Change Log">
  10 <link rel="next" href="reference.html" title="Reference">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
  15 <td align="center"><a href="../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="changes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../hash.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="reference.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
  27 <a name="hash.rationale"></a><a class="link" href="rationale.html" title="Rationale">Rationale</a>
  28 </h2></div></div></div>
  29 <p>
  30       The rationale can be found in the original design <a href="#ftn.hash.rationale.f0" class="footnote" name="hash.rationale.f0"><sup class="footnote">[2]</sup></a>.
  31     </p>
  32 <h4>
  33 <a name="hash.rationale.h0"></a>
  34       <span class="phrase"><a name="hash.rationale.quality_of_the_hash_function"></a></span><a class="link" href="rationale.html#hash.rationale.quality_of_the_hash_function">Quality
  35       of the hash function</a>
  36     </h4>
  37 <p>
  38       Many hash functions strive to have little correlation between the input and
  39       output values. They attempt to uniformally distribute the output values for
  40       very similar inputs. This hash function makes no such attempt. In fact, for
  41       integers, the result of the hash function is often just the input value. So
  42       similar but different input values will often result in similar but different
  43       output values. This means that it is not appropriate as a general hash function.
  44       For example, a hash table may discard bits from the hash function resulting
  45       in likely collisions, or might have poor collision resolution when hash values
  46       are clustered together. In such cases this hash function will preform poorly.
  47     </p>
  48 <p>
  49       But the standard has no such requirement for the hash function, it just requires
  50       that the hashes of two different values are unlikely to collide. Containers
  51       or algorithms designed to work with the standard hash function will have to
  52       be implemented to work well when the hash function's output is correlated to
  53       its input. Since they are paying that cost a higher quality hash function would
  54       be wasteful.
  55     </p>
  56 <p>
  57       For other use cases, if you do need a higher quality hash function, then neither
  58       the standard hash function or <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">hash</span></code> are
  59       appropriate. There are several options available. One is to use a second hash
  60       on the output of this hash function, such as <a href="http://web.archive.org/web/20121102023700/http://www.concentric.net/~Ttwang/tech/inthash.htm" target="_top">Thomas
  61       Wang's hash function</a>. This this may not work as well as a hash algorithm
  62       tailored for the input.
  63     </p>
  64 <p>
  65       For strings there are several fast, high quality hash functions available (for
  66       example <a href="http://code.google.com/p/smhasher/" target="_top">MurmurHash3</a>
  67       and <a href="http://code.google.com/p/cityhash/" target="_top">Google's CityHash</a>),
  68       although they tend to be more machine specific. These may also be appropriate
  69       for hashing a binary representation of your data - providing that all equal
  70       values have an equal representation, which is not always the case (e.g. for
  71       floating point values).
  72     </p>
  73 <div class="footnotes">
  74 <br><hr style="width:100; text-align:left;margin-left: 0">
  75 <div id="ftn.hash.rationale.f0" class="footnote"><p><a href="#hash.rationale.f0" class="para"><sup class="para">[2] </sup></a>
  76         issue 6.18 of the <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1837.pdf" target="_top">Library
  77         Extension Technical Report Issues List</a> (page 63)
  78       </p></div>
  79 </div>
  80 </div>
  81 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
  82 <td align="left"></td>
  83 <td align="right"><div class="copyright-footer">Copyright &#169; 2005-2008 Daniel
  84       James<p>
  85         Distributed under the Boost Software License, Version 1.0. (See accompanying
  86         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>)
  87       </p>
  88 </div></td>
  89 </tr></table>
  90 <hr>
  91 <div class="spirit-nav">
  92 <a accesskey="p" href="changes.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../hash.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="reference.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
  93 </div>
  94 </body>
  95 </html>