|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r60796 - in sandbox/tokenmap/libs/tokenmap/doc: . html html/images html/tokenmap
From: sl_at_[hidden]
Date: 2010-03-23 21:06:57
Author: sl_
Date: 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
New Revision: 60796
URL: http://svn.boost.org/trac/boost/changeset/60796
Log:
Added Background section contributed by Daniel Trebbien
Added:
sandbox/tokenmap/libs/tokenmap/doc/html/images/latex1.png (contents, props changed)
sandbox/tokenmap/libs/tokenmap/doc/html/images/latex2.png (contents, props changed)
sandbox/tokenmap/libs/tokenmap/doc/html/images/latex3.png (contents, props changed)
Text files modified:
sandbox/tokenmap/libs/tokenmap/doc/html/index.html | 58 +++++++++++++++++++++-------
sandbox/tokenmap/libs/tokenmap/doc/html/standalone_HTML.manifest | 3 +
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html | 2
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/quick_tutorial.html | 6 +-
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/rationale_.html | 6 +-
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html | 10 ++--
sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk | 79 ++++++++++++++++++++++++++++++++++-----
7 files changed, 126 insertions(+), 38 deletions(-)
Added: sandbox/tokenmap/libs/tokenmap/doc/html/images/latex1.png
==============================================================================
Binary file. No diff available.
Added: sandbox/tokenmap/libs/tokenmap/doc/html/images/latex2.png
==============================================================================
Binary file. No diff available.
Added: sandbox/tokenmap/libs/tokenmap/doc/html/images/latex3.png
==============================================================================
Binary file. No diff available.
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/index.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/index.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/index.html 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -5,7 +5,7 @@
<link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.73.2">
<link rel="start" href="index.html" title="Chapter 1. Boost.Tokenmap">
-<link rel="next" href="tokenmap/quick_tutorial.html" title="Quick tutorial">
+<link rel="next" href="tokenmap/background.html" title="Background">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
@@ -17,7 +17,7 @@
<td align="center">More</td>
</tr></table>
<hr>
-<div class="spirit-nav"><a accesskey="n" href="tokenmap/quick_tutorial.html"><img src="../../../../doc/html/images/next.png" alt="Next"></a></div>
+<div class="spirit-nav"><a accesskey="n" href="tokenmap/background.html"><img src="../../../../doc/html/images/next.png" alt="Next"></a></div>
<div class="chapter" lang="en">
<div class="titlepage"><div>
<div><h2 class="title">
@@ -27,7 +27,7 @@
</h3></div></div>
<div><p class="copyright">Copyright © 2009 Slawomir Lisznianski</p></div>
<div><div class="legalnotice">
-<a name="id499870"></a><p>
+<a name="id531067"></a><p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
</p>
@@ -37,12 +37,15 @@
<p><b>Table of Contents</b></p>
<dl>
<dt><span class="section">Description</span></dt>
+<dt><span class="section"> Background</span></dt>
+<dd><dl><dt><span class="section"><a href="tokenmap/background.html#tokenmap.background.analysis_of_simple_strategy"> Analysis
+ of the simple strategy</a></span></dt></dl></dd>
<dt><span class="section">Quick tutorial</span></dt>
<dt><span class="section">Reference</span></dt>
<dt><span class="section">Performance </span></dt>
<dt><span class="section">Examples </span></dt>
<dt><span class="section">Rationale </span></dt>
-<dt><span class="section">Acknowledgements </span></dt>
+<dt><span class="section">Acknowledgements</span></dt>
</dl>
</div>
<div class="section" lang="en">
@@ -51,25 +54,50 @@
</h2></div></div></div>
<p>
A <code class="computeroutput"><span class="identifier">tokenmap</span></code> is a data structure
- that uniquely maps pseudo-random generated keys with elements of the collection.
+ that uniquely maps pseudo-random integer keys to values.
</p>
<p>
- Boost.Tokenmap is a (perfect) hash container library for C++. An important
- distinction between <code class="computeroutput"><span class="identifier">tokenmap</span></code>
- and other dictionary-like containers, such as std::map or Boost.Unordered, is that <code class="computeroutput"><span class="identifier">tokenmap</span></code>
- generates keys internally (referred to as "tokens") rather than relying
- on user to provide them. Specifically, when a new element is inserted into
- the <code class="computeroutput"><span class="identifier">tokenmap</span></code>, an apparently
- random key is returned back to the caller which uniquely maps to the stored
- element. The returned key can later be used in a very efficient lookup.
+ Unlike other dictionary-like containers such as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> or
+ Boost.Unordered,
+ a <code class="computeroutput"><span class="identifier">tokenmap</span></code> generates the keys
+ (also called “<span class="quote">tokens</span>”) for values by an internal, pseudo-random
+ algorithm rather than relying on the user to provide them; that is, when a
+ new value is inserted into a <code class="computeroutput"><span class="identifier">tokenmap</span></code>,
+ the <code class="computeroutput"><span class="identifier">tokenmap</span></code> generates a key
+ for the value in some unspecified way and returns this key to the caller. Returned
+ keys, which uniquely map to values, can later be used to retrieve the corresponding
+ value in a very efficient lookup.
+ </p>
+<p>
+ <code class="literal">tokenmap</code>s have the following properties:
+ </p>
+<div class="orderedlist"><ol type="1">
+<li>
+ No two tokens map to the same value (<code class="computeroutput"><span class="identifier">tokenmap</span></code>
+ differs from <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">multimap</span></code> in this respect)
+ </li>
+<li>
+ The returned tokens are <span class="emphasis"><em>stable</em></span> (a token will always
+ map to the corresponding value regardless of how the <code class="computeroutput"><span class="identifier">tokenmap</span></code>
+ was modified since the token was generated)
+ </li>
+<li>
+ Lookups are much faster - sometimes 30 times faster - than <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code>
+ lookups
+ </li>
+</ol></div>
+<p>
+ The second property, also called the <span class="emphasis"><em>perfect hashing property</em></span>,
+ requires special support from the container, as described on the <a class="link" href="tokenmap/background.html" title="Background">Background</a>
+ page.
</p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: March 01, 2010 at 17:22:50 GMT</small></p></td>
+<td align="left"><p><small>Last revised: March 24, 2010 at 01:03:37 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
-<div class="spirit-nav"><a accesskey="n" href="tokenmap/quick_tutorial.html"><img src="../../../../doc/html/images/next.png" alt="Next"></a></div>
+<div class="spirit-nav"><a accesskey="n" href="tokenmap/background.html"><img src="../../../../doc/html/images/next.png" alt="Next"></a></div>
</body>
</html>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/standalone_HTML.manifest
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/standalone_HTML.manifest (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/standalone_HTML.manifest 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -1,7 +1,8 @@
index.html
+tokenmap/background.html
tokenmap/quick_tutorial.html
tokenmap/reference.html
tokenmap/performance_.html
tokenmap/examples_.html
tokenmap/rationale_.html
-tokenmap/acknowledgements_.html
+tokenmap/acknowledgements.html
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -32,7 +32,7 @@
them:
</p>
<div class="table">
-<a name="id510122"></a><p class="title"><b>Table 1.1. Tutorial examples</b></p>
+<a name="id542272"></a><p class="title"><b>Table 1.1. Tutorial examples</b></p>
<div class="table-contents"><table class="table" summary="Tutorial examples">
<colgroup>
<col>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/quick_tutorial.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/quick_tutorial.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/quick_tutorial.html 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -6,7 +6,7 @@
<meta name="generator" content="DocBook XSL Stylesheets V1.73.2">
<link rel="start" href="../index.html" title="Chapter 1. Boost.Tokenmap">
<link rel="up" href="../index.html" title="Chapter 1. Boost.Tokenmap">
-<link rel="prev" href="../index.html" title="Chapter 1. Boost.Tokenmap">
+<link rel="prev" href="background.html" title="Background">
<link rel="next" href="reference.html" title="Reference">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
@@ -20,7 +20,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="../index.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
+<a accesskey="p" href="background.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
</div>
<div class="section" lang="en">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
@@ -81,7 +81,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="../index.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
+<a accesskey="p" href="background.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/rationale_.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/rationale_.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/rationale_.html 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -7,7 +7,7 @@
<link rel="start" href="../index.html" title="Chapter 1. Boost.Tokenmap">
<link rel="up" href="../index.html" title="Chapter 1. Boost.Tokenmap">
<link rel="prev" href="examples_.html" title="Examples">
-<link rel="next" href="acknowledgements_.html" title="Acknowledgements">
+<link rel="next" href="acknowledgements.html" title="Acknowledgements">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
@@ -20,7 +20,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="examples_.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="acknowledgements_.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
+<a accesskey="p" href="examples_.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="acknowledgements.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
</div>
<div class="section" lang="en">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
@@ -60,7 +60,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="examples_.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="acknowledgements_.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
+<a accesskey="p" href="examples_.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="acknowledgements.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -27,7 +27,7 @@
<a name="tokenmap.reference"></a><a class="link" href="reference.html" title="Reference">Reference</a>
</h2></div></div></div>
<a name="tokenmap.reference.headers"></a><h4>
-<a name="id509118"></a>
+<a name="id541266"></a>
<a class="link" href="reference.html#tokenmap.reference.headers">Headers</a>
</h4>
<p>
@@ -36,7 +36,7 @@
to boost namespace.
</p>
<a name="tokenmap.reference.synopsis"></a><h4>
-<a name="id509144"></a>
+<a name="id541293"></a>
<a class="link" href="reference.html#tokenmap.reference.synopsis">Synopsis</a>
</h4>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span>
@@ -83,15 +83,15 @@
</span><span class="special">}</span> <span class="comment">// namespace boost
</span></pre>
<a name="tokenmap.reference.class_template_tokenmap"></a><h4>
-<a name="id509732"></a>
+<a name="id541881"></a>
<a class="link" href="reference.html#tokenmap.reference.class_template_tokenmap">Class template tokenmap</a>
</h4>
<a name="tokenmap.reference.nested_types"></a><h4>
-<a name="id509746"></a>
+<a name="id541895"></a>
<a class="link" href="reference.html#tokenmap.reference.nested_types">Nested types</a>
</h4>
<a name="tokenmap.reference.constructors__copy_and_assignment"></a><h4>
-<a name="id509761"></a>
+<a name="id541910"></a>
<a class="link" href="reference.html#tokenmap.reference.constructors__copy_and_assignment">Constructors,
copy and assignment</a>
</h4>
Modified: sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk 2010-03-23 21:06:55 EDT (Tue, 23 Mar 2010)
@@ -99,16 +99,74 @@
[section Description]
-A `tokenmap` is a data structure that uniquely maps pseudo-random generated keys with
-elements of the collection.
+A `tokenmap` is a data structure that uniquely maps pseudo-random integer keys to values.
-Boost.Tokenmap is a (perfect) hash container library for C++. An important distinction
-between `tokenmap` and other dictionary-like containers, such as std::map or
-_boost_unordered_, is that `tokenmap` generates keys internally (referred to as
-"tokens") rather than relying on user to provide them. Specifically, when a new element
-is inserted into the `tokenmap`, an apparently random key is returned back to the caller
-which uniquely maps to the stored element. The returned key can later be used in a very
-efficient lookup.
+Unlike other dictionary-like containers such as `std::map` or _boost_unordered_, a `tokenmap` generates the keys (also called ["tokens]) for values by an internal, pseudo-random algorithm rather than relying on the user to provide them; that is, when a new value is inserted into a `tokenmap`, the `tokenmap` generates a key for the value in some unspecified way and returns this key to the caller. Returned keys, which uniquely map to values, can later be used to retrieve the corresponding value in a very efficient lookup.
+
+[^tokenmap]s have the following properties:
+
+# No two tokens map to the same value (`tokenmap` differs from `std::multimap` in this respect)
+# The returned tokens are /stable/ (a token will always map to the corresponding value regardless of how the `tokenmap` was modified since the token was generated)
+# Lookups are much faster - sometimes 30 times faster - than `std::map` lookups
+
+The second property, also called the /perfect hashing property/, requires special support from the container, as described on the [link tokenmap.background Background] page.
+
+[endsect]
+
+[section:background Background]
+
+[:['This section was contributed by Daniel Trebbien.]]
+
+The main design goal of `tokenmap` was to make an associative container that uses random keys and which has extremely fast lookup operations (i.e. given a key, the operation to find the associated value should be as fast as possible). Array accesses are known to be among the fastest operations performable on today's computing equipment, so the question in developing `tokenmap` was whether it would be possible to use a dynamic array as the backing storage and still implement a dictionary-like container that allows random keys.
+
+There are many conceivable mapping strategies (the way that tokens are mapped to indices in the array), but it's not always obvious which particular strategy yields an associative container with all of the following properties:
+
+# The container can grow in size to accommodate more elements.
+# Tokens will always map to their corresponding values regardless of the container's growth.
+# The tokens are random.
+
+One simple strategy is to take a token `t` (an unsigned integer) and return the value `store[t % store_length]` where `store` is the name of the dynamic array and `store_length` is its length. Interestingly enough, this strategy /does/ allow the implementation of an associative container with those properties, and this is the strategy that is used by `tokenmap`.
+
+[section:analysis_of_simple_strategy Analysis of the simple strategy]
+
+One immediate consequence of using this simple strategy is that a user cannot provide her own tokens; they must be generated by the container. This is because the user might try to use tokens that, modulo the store length at the time of insert, are the same. For example, if the store length is 12, then a container that is based on the simple strategy cannot allow tokens `0x3af8cf08` and `0xc0d9a414` to map to different values because modulo 12, these numbers are both 8. Some applications require the ability to specify the token, so containers based on this simple strategy are not suitable for these applications. However, there are other applications where you just want to generate handles or IDs of resources that will always map to the resources. For these, the particular values of the handles or IDs are irrelevant (they just need to uniquely map to the resources), so a container that generates the tokens (the particular values of handles or IDs) is perfectly acceptable.
+
+A container that is based on the described above strategy must implement a rehashing algorithm which is used whenever the container is expanded to accommodate more elements. An algorithm that works well with our strategy is:
+
+# Create a new store `new_store` of length `new_store_length`.
+# For each token `t` in the container, place the associated value at `new_store[t % new_store_length]`.
+# Delete the old store and use `new_store` as the store.
+
+If we say that the initial store length is ['s]'''<subscript>0</subscript>''' and subsequent store lengths are ['s]'''<subscript>1</subscript>''', ['s]'''<subscript>2</subscript>''', ..., ['s]'''<subscript><emphasis>k</emphasis></subscript>''', then careful choices of the sequence {['s]'''<subscript><emphasis>k</emphasis></subscript>'''} allow the container to have the property that tokens always map to their corresponding values regardless of the number of re-hashes that have occurred since they were generated (the perfect hashing property).
+
+Some choices of the sequence {['s]'''<subscript><emphasis>k</emphasis></subscript>'''} will not work. For example, suppose ['s]'''<subscript>0</subscript>''' were 2 and ['s]'''<subscript>1</subscript>''' were 3. Then, tokens `0x25b786ef` and `0x0010b86c` can be generated while the store length is 2 (because modulo 2, they are 1 and 0, respectively), but once the store length becomes 3, they hash to the same location (they are both 2 modulo 3).
+
+In the following sections, it will be proven that whenever `new_store_length` is a multiple of the old `store_length`, then the perfect hashing property is preserved.
+
+[heading Modular arithmetic notation]
+
+We denote the set of integers {..., -4, -3, -2, -1, 0, 1, 2, 3, ...} as [*['Z]] and the set of sets of integers that are congruent modulo /s/ as [*['Z]]'''<subscript><emphasis>s</emphasis></subscript>'''. The elements of [*['Z]]'''<subscript><emphasis>s</emphasis></subscript>''' are denoted by so-called /class notation/: \[['x]\]'''<subscript><emphasis>s</emphasis></subscript>''' is the set of integers that have the same remainder as /x/ when divided by /s/; in other words, for /x/ an integer, \[['x]\]'''<subscript><emphasis>s</emphasis></subscript>''' is the set of all integers that are congruent modulo /s/.
+
+[heading Proposition 1: Perfect hashing is preserved with multiples of the old store length]
+
+In order for the token-generating strategy to remain perfect after a single rehash, the crucial property of store lengths /s/'''<subscript><emphasis>k</emphasis></subscript>''' and /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' is:
+[:[$images/latex1.png][footnote Read: If /x/ and /y/ are incongruent modulo /s/'''<subscript><emphasis>k</emphasis></subscript>''', then they are incongruent modulo /s/'''<subscript><emphasis>k</emphasis>+1</subscript>'''.]]
+
+One choice of /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' that always works is when /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' is a multiple of /s/'''<subscript><emphasis>k</emphasis></subscript>'''; when /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' = ['c]·/s/'''<subscript><emphasis>k</emphasis></subscript>''', then it is always true that:
+[:[$images/latex2.png]]
+
+[*Proof]
+
+The statement is proved by way of the logically-equivalent [@http://en.wikipedia.org/wiki/Contrapositive contrapositive]:
+[:[$images/latex3.png]]
+
+If \[['x]\]'''<subscript><emphasis>c</emphasis>·<emphasis>s</emphasis><subscript><emphasis>k</emphasis></subscript></subscript>''' equals \[['y]\]'''<subscript><emphasis>c</emphasis>·<emphasis>s</emphasis><subscript><emphasis>k</emphasis></subscript></subscript>''' then ['c]·['s]'''<subscript><emphasis>k</emphasis></subscript>''' divides (['x] - ['y]) by definition. This implies that /s/'''<subscript><emphasis>k</emphasis></subscript>''' divides (['x] - ['y]), so \[['x]\]'''<subscript><emphasis>s</emphasis><subscript><emphasis>k</emphasis></subscript></subscript>''' equals \[['y]\]'''<subscript><emphasis>s</emphasis><subscript><emphasis>k</emphasis></subscript></subscript>'''. '''∎'''
+
+[heading {['s]'''<subscript><emphasis>k</emphasis></subscript>'''} that preserves perfect hashing after arbitrary rehashes]
+
+From Proposition 1, we know that to preserve the perfect property after a single rehash, one choice of /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' that always works is to make /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' a multiple of /s/'''<subscript><emphasis>k</emphasis></subscript>'''. Therefore, to preserve the perfect hashing property after arbitrary rehashes, we can pick /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' = /c/'''<subscript><emphasis>k</emphasis></subscript>'''·/s/'''<subscript><emphasis>k</emphasis></subscript>''' for any sequence of natural numbers {/c/'''<subscript><emphasis>k</emphasis></subscript>'''}. To make things simple, however, `tokenmap` uses 2 for every /c/'''<subscript><emphasis>k</emphasis></subscript>'''. Thus /s/'''<subscript><emphasis>k</emphasis></subscript>''' = 2'''<superscript><emphasis>k</emphasis></superscript>'''·/s/'''<subscript>0</subscript>'''.
+
+[endsect]
[endsect]
@@ -267,6 +325,7 @@
[endsect]
-[section Acknowledgements ]
+[section Acknowledgements]
+
[endsect]
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk