动态完美散列
定义
动态完美哈希定义为一种解决哈希表数据结构中冲突的编程方法。
应用
尽管此方法比哈希表中的方法要占用更多的内存，但它是必须对大量元素执行快速查询，插入和删除的情况的理想选择。
实作
Dietzfelbinger等。解释一种动态字典算法，该算法在将m个项的集合增量添加到字典时，成员资格查询始终消耗恒定时间，因此O(1)最坏情况下的时间所需的总存储量为O(m)（线性），在动态情况下，当将密钥插入哈希表时，如果它在其各自的子表中的条目被占用，则会发生冲突，并且将O(1)用作预期的摊销插入和删除时间（摊销的恒定时间）。子表将根据其新的总条目数和随机选择的哈希函数进行重建。因为第二级表的负载因子仍然很低，所以重建并不频繁，并且插入的摊销预期成本以及删除的摊销预期成本为O(1)。
此外，在动态情况下，顶层表或任何子表的最终大小没有先验知识。维持表的预期O(m)空间的一种技术是在经历足够数量的插入和删除操作后提示完全重建。只要插入或删除的总数超过上次构造时的元素数，通过考虑完全重新哈希计算，插入和删除的摊销预期成本仍为O(1)。