title: Hashing Recurrence Formula
body: <p>I have a practice test question that is asking the following:</p>
  
  <blockquote>
    <p>Suppose that a hashing strategy is designed so that it starts with an initial hash table size of H= 8. You may assume that only insertions are performed (no deletions). Any time the hash table is going to be more than 50% full (when an attempt is made to add item H/2 + 1 to a table of size H), the hash table size is doubled to 2*H, and then the H/2 keys in the previous hash table are rehashed using H/2 extraneous key insertions into the new table of size 2 * H. The key insertions used to initially place each key into the hash table are called necessary key insertions (these are not extraneous). </p>
    
    <p><strong>QUESTION:
    Derive a recurrence relation E(H) for the number of extraneous key insertions that have occurred in total up until the point in time that the hash table size is H. Explain where the terms in recurrence relation are coming from.</strong> </p>
  </blockquote>
  
  <p>I'm not too sure how I would set up this recurrence, and was hoping if someone could help me with this. I know how to solve a recurrence but I find it the hardest to begin to set it up. </p>
  
  <p>From what I see is that the Hash table is doubled to 2H when the hash table is 50% full or higher. I'm not sure where to go next. </p>
  
  <p>If someone could help me, that would be great as I want to understand this for the test.</p>