动态完美哈希

定义

动态完美哈希被定义为一种解决哈希表数据结构中冲突的编程方法。

应用

虽然这种方法比其哈希表对应方法更占用内存，但它非常适合需要对大量元素执行快速查询、插入和删除操作的情况。

实现

Dietzfelbinger 等人解释了一种动态字典算法，当一组 m 个项目被增量追加到字典中时，成员资格查询始终消耗恒定时间，因此最坏情况时间为 O(1)，所需的总存储空间为 O(m)（线性），并且插入和删除的预期摊销时间为 O(1)（摊销常数时间）。在动态情况下，当一个键被插入到哈希表中时，如果其在相应子表中的条目被占用，则会发生冲突，并且子表将根据其新的总条目计数和随机选择的哈希函数进行重建。由于二级表的负载因子保持较低，因此重建并不频繁，并且插入的摊销预期成本以及删除的摊销预期成本均为 O(1)。

此外，在动态情况下，顶级表或任何子表的最终大小事先并不知道。维护表预期 O(m) 空间的一种技术是在发生足够多的插入和删除操作时提示完全重建。只要插入或删除的总数超过上次构建时元素的数量，通过考虑完全重新哈希，插入和删除的摊销预期成本仍然为 O(1)。

更新于: 2020年1月3日

673 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告