algorithm - 为全迭代+键替换优化的哈希表

Question

我有一个哈希表，其中运行时的绝大多数访问都遵循以下模式之一:

• 遍历所有键/值对。 (此操作的速度至关重要。)
• 修改键(即删除一个键/值对并添加另一个具有相同值但键不同的键。检测重复键并在必要时合并值。)这是在一个循环中完成的，影响了数千个键，但是没有其他操作干预。

我也希望它消耗尽可能少的内存。

其他标准操作必须可用，尽管它们使用频率较低，例如

• 插入一个新的键/值对
• 给定一个键，查找对应的值
• 更改与现有键关联的值

当然，所有“标准”哈希表实现，包括大多数高级语言的标准库，都具有所有这些功能。我正在寻找的是针对第一个列表中的操作优化的实现。

常见实现问题:

• 大多数哈希表实现使用单独的链接(即每个存储桶的链表)。这是有效的，但我希望有一些占用更少内存和更好的引用位置的东西。注意:我的 key 很小(每个 13 个字节，填充为 16 个字节。)
• 大多数开放式寻址方案对我的应用程序都有一个主要缺点: key 在大组中被删除和替换。这留下了增加负载因子的删除标记，需要经常重建表。

可行但不太理想的方案:

• 每个桶用数组(而不是链表)单独链接:
  引用的局部性差，由于小数组被多次重新分配而导致内存碎片
• 线性探测/二次哈希/双重哈希(有或没有布伦特变分):
  表格很快就会被删除标记填满
• 布谷鸟哈希
  仅适用于 <50% 的负载因子，我想要高 LF 以节省内存并加快迭代速度。

是否有适合这种情况的专门哈希方案？

---

注意:我有一个很好的散列函数，可以很好地处理 2 的幂和素数表大小，并且可以用于双重散列，所以这应该不是问题。

Answer 1

会 Extendable Hashing帮助？通过遍历“目录”来遍历键应该很快。不确定“为值修改键”操作是否使用此方案更好。