title: are deleted entries counted in the load factor of a hash table using open addressing
body: <p>When calculating the load factor of a hashtable with an open-addressing  array implementation I am using:</p>
  
  <pre><code>numberOfKeysInArray/sizeOfArray
  </code></pre>
  
  <p>however it occurred to me that since deleted entries must be marked as such (to distinguish them from empty spaces), it might make sense to include these in the number of keys.</p>
  
  <p>My thinking is that as far as estimating the average number of probes to find an entry, deleted entries should count towards the load factor, but as far as inserting a new key they should not.</p>
  
  <p>Which is the proper calculation: including deleted keys or not?</p>