2

So the question came up about whether tombstones should be included when calculating the load factor of a hash table.

I thought that, given that the load factor is used to determine when to expand capacity, tombstones should not be included. An obvious example is if you almost fill and then remove every value in a hash table. Here insertions are super easy (no collisions) so I believe the load factor shouldn't include them.

But you could look at this and think that with all the tombstones lookups will be slow (potentially searching almost the entire space).

So I thought I'd ask the question. Should the load factor of a hashtable include tombstones in the calculation?

1 Answer 1

2

Load factor is not an essential part of hash table data structure -- it is the way to define rules of behaviour for the dymamic system (growing/shrinking hash table is a dynamic system).

Moreover, in my opinion, in 95% of modern hash table cases this way is over simplified, dynamic systems behave suboptimally. It's advantages:

  • Well, simplicity of understanding and implementation.
  • Hash table data structure shouldn't store many numbers with some thresholds -- likely only one number. This is meaningful when hash table is very small and the size of the header affects total data structure memory efficiency (in bytes to store an entry).
  • In certain (and common) case: append/update only hash table, more complex models of behaviour degenerate to the "just load factor" model, in other words, load factor model defines relatively optimal behaviour.

See also my answer on load factor model. I prefer [min load, target load, max load] + growth factor frame model.


If you develop general-purpose hash table with tombstones, I think you can just pick up my results (below). I spend maybe several weeks solely developing this model. Maybe you can make some improvements or further research, I would be glad.

Two main hash table dynamic behaviour patterns are targeted:

  • growing hash table (maybe in growing phase), with little or no removals
    • initial fill of hash table, when proper capacity was not specified (or unknown)
  • hash table that remains of the same or nearly the same size, number of removals is equal or nearly equal to number of insertions
    • caches with upper size bound, LRUs, tables with entry expires

Two thresholds are defined:

  • max size (i. e. number of alive entries), table size * max load

  • min number of free (i. e. empty, without alive entry nor tombstone) slots, computed by magic formula.

If hash table size exceeds max size, we assume we are in the "growing pattern", rehash to the table size to be able to store current size * growth factor entries, i. e. choose table size closest possible to current size * growth factor / target load.

If the number of free slots becomes below than min number of free slots, we are in "cache pattern", rehash "to the current size", i. e. to the table size closest possible to current size / target load.

Read the source where all the above logics are coded.

Also, article Tombstones purge from hashtable: theory and practice sheds some light.


If you develop specially purposed hash table, which dymanic properties are known (or could be studied), I recommend you to develop your own model, fitting your case. Don't rely on pure math and CS theory, evaluate your model in benchmarks.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.