title: Coalesced Hashing Deletion Algorithm
body: <p>Can someone show me an example of deletion algorithm for a coalesced chained hash table?</p>
  
  <p>My insertion algorithm is like this:</p>
  
  <pre><code>Insert (key) 
      int p = hash(key)
      if d[p] = NIL then
          d[p] = key
          next[p] = NIL
      else
          while next[p] != NIL 
              p = next[p]
          endwhile
          td[firstEmpty] = key
          next[p] = firstEmpty
          next[firstEmpty] = NIL
      endif
      UpdateFirstEmpty(); //sets firstEmpty to first empty slot with lowest index
  endInsert
  </code></pre>
  
  <p>Let's say the number of slots in the table is 13. The hash function returns <code>Key%13</code>.</p>
  
  <pre><code>    Keys | 5 | 18 | 16 | 15 | 13 | 31 | 26 |      
  Hash(key)| 5 |  5 |  3 |  2 |  0 |  5 |  0 |
  </code></pre>
  
  <p>After inserting them in this order my table would look something like this:</p>
  
  <pre><code>index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
      d| 18| 13| 15| 16| 31|  5| 26| -1| -1| -1| -1| -1| -1|
   next|  1|  4| -1| -1|  6|  0| -1| -1| -1| -1| -1| -1| -1|
  </code></pre>
  
  <p><code>where -1 = NIL</code></p>
  
  <p>If someone could explain to me what I should be trying to do when removing keys without breaking the chains even if it's in words I would really appreciate it. </p>
  
  <p>Thanks</p>
  
  <hr>
  
  <p><strong>EDIT -:</strong> I think I finally got it.. I'm using the same technique I used when deleting an item from a open addressed hash table.</p>
  
  <p>This is how it goes:</p>
  
  <pre><code>Search for key position and it's predecessor pp
      if key is found at position p
          if pp != NIL then 
               next[pp] = NIL  
          d[p] = NIL           //deletes the key
          p = next[p]          //move position to next value in the chain
          UpdateFirstEmpty()
          while d[p] != NIL do
              temp = d[p]      //save value
              d[p] = NIL       //delete value 
              p = next[p]      //move position to next value in chain
              UpdateFirstEmpty()
              Insert(temp)     //insert the value in the list again
          endwhile
     endif
  endalg
  
  index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
      d| 18| 13| 15| 16| 31|  5| 26| -1| -1| -1| -1| -1| -1|
   next|  1|  4| -1| -1|  6|  0| -1| -1| -1| -1| -1| -1| -1|
  firstFree: 7
  
  delete 18
  
  index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
      d| 13| 31| 15| 16| 26|  5| -1| -1| -1| -1| -1| -1| -1|
   next|  4| -1| -1| -1| -1|  1| -1| -1| -1| -1| -1| -1| -1|
  firstFree: 6
  
  delete 13
  
  index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
      d| 26| 31| 15| 16| -1|  5| -1| -1| -1| -1| -1| -1| -1|
   next| -1| -1| -1| -1| -1|  1| -1| -1| -1| -1| -1| -1| -1|
  firstFree: 4
  
  delete 26
  
  index|  0|  1|  2|  3|  4|  5|  6|  7|  8|  9| 10| 11| 12|
      d| -1| 31| 15| 16| -1|  5| -1| -1| -1| -1| -1| -1| -1|
   next| -1| -1| -1| -1| -1|  1| -1| -1| -1| -1| -1| -1| -1|
  firstFree: 0
  </code></pre>
  
  <p>I don't think this is the right way to be doing it, but it seems to be working. Anyway, I hope will help someone in the future.</p>