静态完美哈希

完美哈希的定义

完美哈希定义为哈希模型,在该模型中,n个元素的任何集合都可以存储在大小相等的哈希表中,并且可以在固定时间内执行查找。它是Fredman,Komlos和Szemeredi(1984)专门发明和讨论的,因此被昵称为“ FKS Hashing”。

静态哈希的定义

静态散列定义了散列问题的另一种形式,它允许用户在最终的字典集上完成查找(这意味着字典中的所有对象都是最终的,而且不会改变)。

应用

由于静态哈希要求数据库,其对象和引用保持不变,因此其应用程序受到限制。包含经历极少更改的信息的数据库也是有资格的,因为它仅在极少数情况下需要整个数据库的完整哈希值。此哈希方案的各种示例包括单词集和特定语言的定义,组织人员的重要数据集等。

实作

在静态情况下,我们提前提供了一个集合,其中包含总共p个条目,每个条目与一个唯一的密钥相关联。Fredman,Komlós和Szemerédi选择大小为s = 2(p-1)个存储桶的一级哈希表。为了构造,通过顶级散列函数将p个条目分成q个存储桶,其中q = 2(p-1)。然后,对于每个具有r个条目的存储桶,为第二层表分配了r2个插槽,并从通用哈希函数集中随机选择其哈希函数,使其无冲突,并与哈希表一起存储。如果随机选择的哈希函数创建具有冲突的表,则将随机选择一个新的哈希函数,直到可以确保无冲突的表为止。最后,使用无冲突哈希,将r个条目哈希到第二级表中。