为全迭代+密钥替换优化的哈希表

Question

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

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

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

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

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

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

常见实现的问题：

• 大多数哈希表实现使用单独的链接(即每个桶的链接列表)。这是可行的，但我希望的东西，占用较少的内存和更好的局部性参考。注意:我的键很小(每个13字节，填充到16个字节)。
• 大多数开放的寻址方案对我的应用程序都有一个主要的缺点:键被移除并在大组中被替换。这就使得删除标记增加了加载因子，需要频繁地重新构建表。

有效但不太理想的方案：

• 使用数组(而不是链接列表)对每个桶进行单独的链接： 引用的局部性差，这是由于小数组的内存碎片多次重新分配的结果。
• 线性探测/二次散列/双哈希(不论是否有Brent的变化)： 表中快速填充删除标记。
• 杜鹃散列 只工作在<50%的负载因子，我想要一个较高的LF节省内存和加快迭代。

是否有一种专门的散列方案可以很好地适用于这种情况？

注意:我有一个很好的散列函数，它可以很好地工作在2的幂和素表大小上，并且可以用于双哈希，所以这不应该是一个问题。

Answer 1

可扩展散列能帮上忙吗？通过遍历“目录”来迭代键应该是快速的。不确定“为值修改键”操作对此方案是否更好。

Answer 2

根据您访问数据的方式，使用哈希表真的有意义吗？

由于您是主要用例，因此需要迭代--排序列表或btree可能是更好的数据结构。

您似乎并不需要构建哈希表所需的恒定时间随机数据访问。

Answer 3

你可以做得比50%的负载因子杜鹃哈希。

两个包含四个项的散列函数可以让您轻松完成90%以上的任务。见本文：

http://www.ru.is/faculty/ulfar/CuckooHash.pdf

我正在构建一个预先计算的字典，使用一个布谷鸟散列，得到一个超过99%的负载因子，每个桶包含两个哈希函数和7个条目。