are deleted entries counted in the load factor of a hash table using open addressing

Posted by Dr. Monkey on Stack Overflow See other posts from Stack Overflow or by Dr. Monkey
Published on 2010-06-08T09:13:33Z Indexed on 2010/06/08 19:22 UTC
Read the original article Hit count: 367

Filed under:
|

When calculating the load factor of a hashtable with an open-addressing array implementation I am using:

numberOfKeysInArray/sizeOfArray

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.

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.

Which is the proper calculation: including deleted keys or not?

© Stack Overflow or respective owner

Related posts about hashtable

Related posts about load-factor