2

所以就出现了计算哈希表的负载因子时是否应该包括墓碑的问题。

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

但是你可以看看这个并认为所有的墓碑查找都会很慢（可能搜索几乎整个空间）。

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

4

1 回答 1

2

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

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

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

另请参阅我对负载因子模型的回答。我更喜欢[最小负载，目标负载，最大负载] + 增长因子框架模型。

如果你用墓碑开发通用哈希表，我想你可以拿起我的结果（下）。我可能会花费数周时间单独开发此模型。也许您可以进行一些改进或进一步研究，我会很高兴。

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

  • 增长的哈希表（可能处于增长阶段），很少或没有删除
    • 当未指定（或未知）适当容量时，哈希表的初始填充
  • 保持相同或几乎相同大小的哈希表，删除次数等于或几乎等于插入次数
    • 具有大小上限的缓存、LRU、条目过期的表

定义了两个阈值：

  • 最大大小（即活动条目的数量），table size * max load

  • 由魔术公式计算的空闲（即空，没有活动条目或墓碑）插槽的最小数量。

如果散列表大小超过最大大小，我们假设我们处于“增长模式”，重新散列到表大小以便能够存储current size * growth factor条目，即选择最接近的表大小current size * growth factor / target load。

如果空闲槽数低于最小空闲槽数，我们处于“缓存模式”，重新哈希“到当前大小”，即最接近的表大小current size / target load。

阅读所有上述逻辑编码的源代码。

此外，文章Tombstones purge from hashtable: theory and practice 提供了一些启示。

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

于 2015-04-26T22:01:05.117 回答