具有墓碑的哈希表的负载因子

那么问题来了，在计算哈希表的负载因子时是否应该包括墓碑。

我认为，考虑到负载系数是用来确定何时扩展容量的，所以不应该包括墓碑。一个明显的例子是，如果您几乎填充然后删除哈希表中的每个值。这里的插入非常容易（没有碰撞），所以我相信负载因子不应该包括它们。

但您可能会看到这一点并认为所有墓碑查找都会很慢（可能会搜索几乎整个空间）。

所以我想我会问这个问题。哈希表的负载因子是否应该在计算中包括墓碑？

负载因子不是哈希表数据结构的重要组成部分——它是定义的方式动态系统的行为规则（增长/收缩哈希表是一个动态系统）。

此外，在我看来，在 95% 的现代哈希表情况下，这种方式过于简化，动态系统的表现并不理想。它的优点：

• 嗯，理解和实施都很简单。
• 哈希表数据结构不应该存储许多具有某些阈值的数字——可能只存储一个数字。当哈希表非常小时并且标头的大小影响总数据结构内存效率（以存储条目的字节为单位）时，这是有意义的。
• 在某些（和常见）情况下：仅附加/更新哈希表，更复杂的行为模型退化为“仅负载因子”模型，换句话说，负载因子模型定义相对最优的行为。

另请参阅我对负载因子模型的回答。我更喜欢[最小负载、目标负载、最大负载]+增长因子框架模型。 https://stackoverflow.com/a/23438573/648955

---

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.

针对两种主要的哈希表动态行为模式：

• growing hash table (maybe in growing phase), with little or no removals
  • 当未指定（或未知）适当的容量时，哈希表的初始填充
• hash table that remains of the same or nearly the same size, number of removals is equal or nearly equal to number of insertions
  • 具有上限大小的缓存、LRU、具有条目过期的表

定义了两个阈值：

• max size（即存活条目的数量），table size * max load

• 空闲（即空的，没有活动条目或墓碑）插槽的最小数量, 通过魔法公式计算 https://github.com/OpenHFT/Koloboke/blob/0b4898817f41b0820e0d9a2839fb593f112f9edc/lib/impl/src/main/javaTemplates/net/openhft/koloboke/collect/impl/hash/MutableDHash.java#L35.

如果哈希表大小超过max size，我们假设我们处于“增长模式”，重新哈希表大小以能够存储current size * growth factor恩茨岛e.选择最接近的桌子尺寸current size * growth factor / target load.

如果空闲槽数低于空闲槽位的最小数量，我们处于“缓存模式”，重新哈希“到当前大小”，i。 e.尽可能接近的桌子尺寸current size / target load.

Read 上述所有逻辑的源代码 https://github.com/OpenHFT/Koloboke/blob/0b4898817f41b0820e0d9a2839fb593f112f9edc/lib/impl/src/main/javaTemplates/net/openhft/koloboke/collect/impl/hash/MutableDHash.java.

另外，文章从哈希表中清除墓碑：理论与实践 https://github.com/OpenHFT/Koloboke/wiki/Tombstones-purge-from-hashtable:-theory-and-practice提供了一些线索。

---

如果您开发专门用途的哈希表，哪些动态属性是已知的（或可以研究的），我建议您开发自己的模型，适合您的情况。不要依赖纯数学和计算机科学理论，在基准测试中评估你的模型。