title: Moving from Linear Probing to Quadratic Probing (hash collisons)
body: <p>My current implementation of an Hash Table is using Linear Probing and now I want to move to Quadratic Probing (and later to chaining and maybe double hashing too). I've read a few articles, tutorials, wikipedia, etc... But I still don't know exactly what I should do.</p>
  
  <p>Linear Probing, basically, has a step of 1 and that's easy to do. When searching, inserting or removing an element from the Hash Table, I need to calculate an hash and for that I do this:</p>
  
  <pre><code>index = hash_function(key) % table_size;
  </code></pre>
  
  <p>Then, while searching, inserting or removing I loop through the table until I find a free bucket, like this:</p>
  
  <pre><code>do {
      if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
          // FOUND ELEMENT
  
          return;
      } else {
          index = (index + 1) % table_size;
      }
  while(/* LOOP UNTIL IT'S NECESSARY */);
  </code></pre>
  
  <p>As for Quadratic Probing, I think what I need to do is change how the "index" step size is calculated but that's what I don't understand how I should do it. I've seen various pieces of code, and all of them are somewhat different.</p>
  
  <p>Also, I've seen some implementations of Quadratic Probing where the hash function is changed to accommodated that (but not all of them). Is that change really needed or can I avoid modifying the hash function and still use Quadratic Probing?</p>
  
  <p><strong>EDIT:</strong>
  After reading everything pointed out by Eli Bendersky below I think I got the general idea. Here's part of the code at <a href="http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx" rel="nofollow noreferrer">http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx</a>:   </p>
  
  <pre><code>15   for ( step = 1; table-&gt;table[h] != EMPTY; step++ ) {
  16     if ( compare ( key, table-&gt;table[h] ) == 0 )
  17       return 1;
  18 
  19     /* Move forward by quadratically, wrap if necessary */
  20     h = ( h + ( step * step - step ) / 2 ) % table-&gt;size;
  21   }
  </code></pre>
  
  <p>There's 2 things I don't get... They say that quadratic probing is usually done using <code>c(i)=i^2</code>. However, in the code above, it's doing something more like <code>c(i)=(i^2-i)/2</code></p>
  
  <p>I was ready to implement this on my code but I would simply do:</p>
  
  <pre><code>index = (index + (index^index)) % table_size;
  </code></pre>
  
  <p>...and not:</p>
  
  <pre><code>index = (index + (index^index - index)/2) % table_size;
  </code></pre>
  
  <p>If anything, I would do:</p>
  
  <pre><code>index = (index + (index^index)/2) % table_size;
  </code></pre>
  
  <p>...cause I've seen other code examples diving by two. Although I don't understand why...</p>
  
  <p><strong>1)</strong> Why is it subtracting the step?<br>
  <strong>2)</strong> Why is it diving it by 2?</p>