针对动态/静态/增量数据的特化哈希表算法
我有许多数据集具有键值模式 - 即字符串键和指向数据的指针。现在它被存储在散列表中，每个表都具有与散列键相对应的槽阵列，并且在碰撞时形成具有碰撞的每个槽（直接链接）下的链表。所有在C中实现（并应保持在C），如果它很重要。现在针对动态/静态/增量数据的特化哈希表算法
，该数据实际上是3种稍有不同类型的数据集：
- 某些套可随意
- 被改变（键添加，删除，替换等）对于一些数据集可以被添加但几乎不会被替换/删除（即它可能发生，但在实践中它是非常罕见的）
- 对于某些集合，数据只添加一次，然后只查找，一旦整个集合加载后它不会被更改。
所有的过程都必须尽可能快地支持查找，并消耗最少量的内存（虽然查找速度比大小更重要）。
所以问题是 - 是否有更好的散列表结构/实现，可以更好地适应特定情况？我怀疑对于第一种情况来说，链接是最好的，但不能确定其他两种情况。
回答：
如果您在哈希表中为每个存储桶使用链接列表，则您已经接受了现代CPU上相对较差的性能（链接列表的局部性较差，因此CPU缓存交互性较差）。所以我可能不会担心优化其他特殊情况。但是，如果您想要继续沿用正在使用的路径，请参阅以下几条提示：
对于'频繁更改'数据集和'几乎不会更改'的情况，每次从哈希表中读取项目，将其移动到该存储桶的链表列表的前面。对于一些更好的想法，这篇论文虽然专注于固定大小的键，但它是一个很好的起点Fast and Compact Hash Tables for Integer Keys。
对于'数据集永不改变'的情况下，你应该看看完美的哈希生成器。如果你在编译时知道你的密钥，我已经用gperf获得了很好的结果。如果您的密钥在运行时间之前不可用，请尝试C Minimal Perfect Hashing Library。
回答：
那些较小（几十个元素）的集合可能是使用二进制或甚至线性搜索存储在顺序存储器中的键的最快速度！
显然，关键的身体必须在顺序记忆，或他们的哈希值。但是如果你可以把它放到一个或两个L1 cache.lines中，它就会飞行。
至于更大的哈希，直接链接可能会失去开放地址？
您可以探索“cache conscious”哈希表并尝试。
wikipedia文章详细讨论了缓存行，描述了要考虑的各种权衡。
以上是 针对动态/静态/增量数据的特化哈希表算法 的全部内容， 来源链接： utcz.com/qa/265950.html
