title: Why would map be much faster than unordered_map?
body: <p>I implemented a search caching results that consist of keys of type State (a class with 7 short ints) and values of type <code>Score</code> (a class of 3 doubles.) Using unordered_map was at least 20 times slower than map.  Why?</p>
  
  <p>Edit:  Darn it!  My hash function was </p>
  
  <pre><code>namespace std {
      size_t hash&lt;State&gt;::operator()(State const&amp; s) const {
          size_t retval = hash&lt;short&gt;()(s.s[0]);
          for (int i = 1; i &lt; R; i += 2) {  // 1 3 5
              int x = (static_cast&lt;int&gt;(s.s[i + 1]) &lt;&lt; 16)
                  + (static_cast&lt;int&gt;(s.s[i]));
              hash_combine(retval, x);
          }
      }
  }
  </code></pre>
  
  <p>I forgot to <code>return retval</code>, so it was all colliding!  I wish unordered_map had a hash_function_quality() function that reports the average number of collisions.</p>