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

Question

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?

Answer 1

No, by definition, load factor is the ratio of number of elements to bucket array size. See e.g. Wikipedia or this lecture.

There would also be a practical problem with counting delted entries in the load factor. Most implementations have a maximum load factor. If actual surpasses the maximum allowed, backing array size is increased. If deleted entries counted towards higher load factor, this could cause unnecessary array size increase for an almost empty but high on debris contents table.