数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究静态完美哈希
完美哈希的定义
完美哈希被定义为一种哈希模型，其中任何一组 n 个元素都可以存储在大小相同的哈希表中，并且可以在恒定时间内执行查找操作。它是由 Fredman、Komlos 和 Szemeredi (1984) 特别发明和讨论的，因此被称为“FKS 哈希”。
静态哈希的定义
静态哈希定义了哈希问题的另一种形式，它允许用户对最终的字典集执行查找操作（这意味着字典中的所有对象都是最终的，并且不会更改）。
应用
由于静态哈希需要数据库、其对象和引用保持不变，因此其应用受到限制。包含很少更改的信息的数据库也符合条件，因为它只需要在极少数情况下对整个数据库进行重新哈希。这种哈希方案的各种示例包括特定语言的单词和定义集、组织人员的重要数据集等。
实现
在静态情况下，我们提前提供了一个包含 p 个条目的集合，每个条目都与一个唯一的键相关联。Fredman、Komlós 和 Szemerédi 选择一个第一级哈希表，大小为 s = 2(p-1) 个桶。为了构建，p 个条目由顶级哈希函数分成 q 个桶，其中 q = 2(p-1)。然后，对于每个包含 r 个条目的桶，分配一个包含 r2 个槽的二级表，并且其哈希函数是从一个通用哈希函数集中随机选择的，以便使其无冲突并与哈希表一起存储。如果随机选择的哈希函数创建了一个包含冲突的表，则会随机选择一个新的哈希函数，直到可以保证无冲突的表。最后，使用无冲突的哈希，将 r 个条目哈希到二级表中。
更新于: 2020年1月3日
2K+ 浏览量
广告