title: Quadratic testing in hash tables
body: <p>During an assignment, I was asked to show that a hash table of size m (m>3, m is prime) that is less than half full, and that uses quadratic checking (<code>hash(k, i) = (h(k) + i^2) mod m</code>) we will always find a free spot.</p>
  
  <p>I've checked and arrived to the conclusion that the spots that will be found (when h(k)=0) are <code>0 mod m</code>, <code>1 mod m</code>, <code>4 mod m</code>, <code>9 mod m</code>, ...<br>
  My problem is that I can't figure a way to show that it will always find the free spot. I've tested it myself with different values of m, and also have proven myself that if the hash table is more than half full, we might never find a free spot. </p>
  
  <p>Can anyone please hint me towards the way to solve this?</p>
  
  <p>Thanks!</p>