title: Linear Hashing calculation?
body: <p>I am currently studying for my exams and have came up against this question:</p>
  
  <p>(5d) Suppose we are using linear hashing, and start with an empty table with 2 buckets (M = 2), split = 0 and a load factor of 0.9. Explain the steps we go through when the following hashes are added (in order):</p>
  
  <p>5,7,12,11,9</p>
  
  <p>The answer provided for this is:</p>
  
  <p>*— —5— (0,1)<br>
  * — —5,7 —</p>
  
  <ul>
  <li>split —*—5,7— — (0,1,2)  </li>
  </ul>
  
  <p>—12*—5,7— — —</p>
  
  <ul>
  <li>split —12—5—*—7— (0,1,2,3)</li>
  <li>split =M, M = 2*M, split = 0</li>
  </ul>
  
  <p>*—12—5— —7—<br>
  *—12—5— —7,11—</p>
  
  <ul>
  <li>split —*—5— —7,11—12— (0,1,2,3,4)</li>
  </ul>
  
  <p>—*—5,9— —7,11—12—</p>
  
  <ul>
  <li>split — —9*— —7,11—12—5— (0,1,2,3,4,5)</li>
  </ul>
  
  <p>This answer doesn't make any sense to me and the lecturer did not go through this.</p>
  
  <p>How do I tackle this question?</p>