title: How does hopscotch hashing actually work?
body: <p>I am reading about <a href="http://en.wikipedia.org/wiki/Hopscotch_hashing" rel="nofollow">hopscotch hashing</a><br>
  The algorithm says when we run into colision during insert:  </p>
  
  <pre><code>Otherwise, j is too far from i. To create an empty entry closer to i, find an
  item y whose hash value lies between i and j, but within H − 1 of j, and
  whose entry lies below j. Displacing y to j creates a new empty slot closer
  to i. Repeat. If no such item exists, or if the bucket already i contains H
  items, resize and rehash the table.
  </code></pre>
  
  <p>I am not sure how this works.<br>
  Example. Assume H = 3 and that a,b,c all map to 0 and d,e map to 1<br>
  We have:  </p>
  
  <pre><code> 0  1  2  3  4  5    
  [a, b, c, d,  ,  ] the table with 2 slots empty    
      i       j
  </code></pre>
  
  <p>b,c are within H - 1 (2) places away of their position (0) in locations 1,2 of the table and d is within 2 positions from its location 1.<br>
  If I try to insert e that also maps to 1 I would start from index 4 (an empty slot found with linear probing) and would work backwards towards 1.<br>
  According to the algorithm index 3 (which has now d) is between i and j (which are 1 and 4 respectively)  and within H - 1 i.e. 2 positions of j.<br>
  So we can swap and have:  </p>
  
  <pre><code> 0  1  2  3  4  5    
  [a, b, c,  , d ,  ] the table with 2 slots empty    
      i       j
  </code></pre>
  
  <p>so now the empty slot is 3 and we can insert e since it is 2 positions away from i.<br>
  But now d whose hash value maps to 1 is more than 2 positions from 1 and can no longer be found.  </p>
  
  <p>So how does this algorithm work?<br>
  <em>Note:</em> My assumption and understanding is that the hop value is only an optimization trick for not having to run the equality over all H elements belonging to the bucket and not related with the core algorithm per se.</p>