c - 动态/静态/增量数据的专用哈希表算法

Question

我有许多具有键值模式的数据集——即一个字符串键和一个指向数据的指针。现在它存储在哈希表中，每个表都有与哈希键对应的槽数组，并且在碰撞时在每个有碰撞的槽下形成一个链表(直接链接)。如果重要的话，全部用 C 实现(并且应该留在 C 中)。

现在，数据实际上是 3 种略有不同的数据集:

1. 有些集合可以随意更改(添加、删除、替换 key 等)
2. 对于某些集合，数据可以添加但几乎不会被替换/删除(即它可能发生，但在实践中非常罕见)
3. 对于某些集合，数据只添加一次，然后只查找，一旦加载整个集合就永远不会改变。

当然，所有集合都必须尽可能快地支持查找，并消耗最少的内存(尽管查找速度比大小更重要)。

所以问题是 - 是否有更好的哈希表结构/实现更适合特定情况？我怀疑第一种情况下链接是最好的，但不确定其他两种情况。

Answer 1

如果您为哈希表中的每个桶使用链表，您已经接受了现代 CPU 上相对较差的性能(链表的局部性较差，因此 CPU 缓存交互较差)。所以我可能不会担心优化其他特殊情况。但是，如果您想继续沿着您正在使用的路径前进，这里有一些提示:

对于'经常变化'的数据集和'几乎从不变化'的情况，每次从哈希表中读取一个项目，将其移动到该桶的链表链的前面。对于一些更好的想法，尽管这篇论文关注的是固定大小的键，但它是一个很好的起点 Fast and Compact Hash Tables for Integer Keys .

对于“数据集永不改变”的情况，您应该研究完美的哈希生成器。如果你在编译时知道你的 key ，我用 gperf 得到了很好的结果。 .如果您的 key 在运行时之前不可用，请尝试 C Minimal Perfect Hashing Library .