title: Unordered map for unique keys and hashing
body: <p>I am working in a library in which some elements, that do not matter here, must be identified with a name (i.e. values are associated to names). Names are strings for the user, whatever their internal representation is, and should behave transparently.</p>
  
  <ul>
  <li><strong>Names are constant and initialized with strings literals.</strong> They are known at compile-time.</li>
  <li><strong>Two names that were initialized with different strings must compare different</strong>, whatever their internal representation is.</li>
  <li><strong>Names may be of arbitrary length.</strong> My library does not set any restriction.</li>
  <li><strong>Virtually, there must not be a limit on possible names.</strong> The implementation's constraints must not affect the interface, so, again, no restrictions from my side.</li>
  </ul>
  
  <p>Considering that frequent lookup will happen, I have thought about using an unordered map.</p>
  
  <p>Unordered associative containers store their elements, whatever their type is, by numbers (typically of type <code>std::size_t</code>), which are obtained with a hash function. This means that:</p>
  
  <ul>
  <li>For types whose number of possible values is less or equal to that of the hash value, no collisions should happen.</li>
  <li>For types whose number of possible values is greater than that of the hash value, collisions may happen, since some data is lost in the hashing process.</li>
  </ul>
  
  <p>I have thought about two solutions.</p>
  
  <h3>Hashing by value</h3>
  
  <p>Using the data itself to compute the hash value. Considerations:</p>
  
  <ul>
  <li><strong>Possibly computed at compile-time.</strong> Since the names are constructed from string literals, a <code>constexpr</code> hashing function could be invoked by the constructor (which would be <code>constexpr</code> itself) and the hash value stored in the class itself, for quick retrieval later (by the hasher object).</li>
  <li><strong>How often would collisions happen?</strong> Which would be the best algorithm?</li>
  </ul>
  
  <h3>Hashing by order</h3>
  
  <p>The Boost.Log library, as explained <a href="http://www.boost.org/doc/libs/1_56_0/libs/log/doc/html/log/detailed/attributes.html#log.detailed.attributes.related_components.attribute_name" rel="nofollow">here</a>, maintains a global (i.e. static) table that associates names with their hash value. A possible implementation would be the following:</p>
  
  <ol>
  <li>When a name is constructed (from a string literal), the table is looked up (performing exact comparisons).
  <ul>
  <li>If it isn't found, it is registered at the end of the container.</li>
  </ul></li>
  <li>Its entry's offset in the table becomes its hash value.</li>
  </ol>
  
  <p>Considerations:</p>
  
  <ul>
  <li><strong>Very slow.</strong> For every name constructed, as much string comparisons as names registered would have to be performed. This is not much better than a traditional <code>std::map</code>, is it?</li>
  <li><strong>Thread unsafe.</strong> The table would have to be protected.</li>
  <li><strong>Forcibly done at runtime.</strong></li>
  </ul>
  
  <hr>
  
  <h2>Questions</h2>
  
  <ol>
  <li><strong>Is it right to use an unordered map under these conditions?</strong> Would it be better to use a <code>std::map</code> instead?</li>
  <li>If 1 is 'yes', <strong>which approach is better, and why?</strong> The one used in Boost.Log seems really unefficient, why is it used instead of the other I explained, even if strings are not necessarily known at compile-time?</li>
  </ol>
  
  <p>Note: I have not added the <code>c++14</code> tag even though I have access to the experimental support offered by gcc and clang. Please, do not hesitate using features included in the upcoming specification.</p>