title: Why is my std::unordered_map access time not constant
body: <p>I wrote some code to test my unordered map performance with a 2 component vector as a key.</p>
  
  <pre><code>std::unordered_map&lt;Vector2i, int&gt; m;                                                                      
  
  for(int i = 0; i &lt; 1000; ++i)                                                                             
      for(int j = 0; j &lt; 1000; ++j)                                                                         
          m[Vector2i(i,j)] = i*j+27*j;                                                                      
  
  clock.restart();                                                                                          
  
  auto found = m.find(Vector2i(0,5));                                                                                                                                                            
  
  std::cout &lt;&lt; clock.getElapsedTime().asMicroseconds() &lt;&lt; std::endl;                                         
  </code></pre>
  
  <p>output for the code above: 56 (microseconds)
  When I replace 1000 in the for loops by 100 the outputs is 2 (microseconds)
  Isn't the time supposed to be constant ?</p>
  
  <p>hash function for my Vector2i:</p>
  
  <pre><code>namespace std                                                                                                    
  {
  
     template&lt;&gt;                                                                                                   
      struct hash&lt;Vector2i&gt;                                                                                        
      {                                                                                                            
          std::size_t operator()(const Vector2i&amp; k) const                                                          
          {                                                                                                        
              using std::size_t;                                                                                   
              using std::hash;                                                                                     
              using std::string;                                                                                   
  
              return (hash&lt;int&gt;()(k.x)) ^ (hash&lt;int&gt;()(k.y) &lt;&lt; 1);                                                 
          }                                                                                                        
  
      };                                                                                                           
  
  
  }                                                                             
  </code></pre>
  
  <p><strong>EDIT:</strong> 
  I added this code to count the collisions after the for loop:</p>
  
  <pre><code>for (size_t bucket = 0; bucket != m.bucket_count(); ++bucket)                                             
      if (m.bucket_size(bucket) &gt; 1)                                                                        
           ++collisions; 
  </code></pre>
  
  <p>With 100*100 elements: collisions = 256</p>
  
  <p>1000*1000 elements: collisions = 2048</p>