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
hashtable
|load-factor
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