15
优化我有一个哈希表，其中在运行时，绝大多数的访问遵循以下模式之一：哈希表的完整的迭代+键更换
- 迭代通过所有键/值对。 （这个操作的速度很关键。）
- 修改键（即删除一个键/值对&添加另一个具有相同的值，但不同的键。检测重复键&结合值，如有必要）。这是在一个循环，影响成千上万的密钥，但没有其他操作干预。
我也希望它消耗尽可能少的内存。
其他标准操作必须可用，尽管它们使用较少，例如，
- 插入一个新的键/值对
- 给定一个键，查找相应的值
- 变化与现有的关键
当然所有的“标准”哈希表相关联的值包括大多数高级语言的标准库在内的实现具有所有这些功能。我正在寻找的是为第一个列表中的操作优化的实现。
与常见的实现问题：
- 大多数哈希表实现使用分离链这工作，但我希望的东西，有更好的地方占用的内存更少（即，每个桶的链接列表。）参考。注意：我的密钥很小（每个13个字节，填充为16个字节）。
- 大多数开放寻址方案对我的应用程序有一个主要缺点：密钥被删除并在大型组中被替换。这留下了增加载入因子的删除标记，需要经常重建表格。
方案即工作，但低于理想：每桶
- 分离链与阵列（而不是一个链表）：
的参考普尔局部性，从内存碎片导致因为小阵列被多次重新分配 - 线性探测/二次哈希/双哈希（有或没有布伦特变化）：
表快速填充删除标记 - 杜鹃散列
只适用于< 50％的加载因子，我想要一个高LF来节省内存并加速迭代。
是否有专门的散列方案可以很好地适用于这种情况？
注：我有一个很好的哈希函数，既素表大小的功率为2的和行之有效的，可用于双散列，所以这不应该是一个问题。
你似乎做了大量的研究，所以我没有一个真正的答案。然而，我确实质疑你的参考地点的目标。当然，这取决于你的表的大小和你的实现语言，但我的经验是，你只能保持哈希数组缓存（然后只有当你幸运）。对你来说，它可能有一个包含键和指向该值的指针的结构数组;即每个20字节，或2MB缓存约100,000个条目。当然，你需要一种能够给你布局控制的语言。而且负载因数相对较低。 – Anon 2011-05-12 18:46:48
如果你确实拥有一个足够容纳整个表的缓存，它不会真的伤害你（太多），因为没有指针的散列数组，而是在第二个连续的内存块中使用链表免费列表来恢复已删除的条目）。 – Anon 2011-05-12 18:53:46
您希望在表中存储多少个元素，以及您希望在每次批次密钥更新操作期间修改多少个密钥？ – 2011-05-13 03:51:20