数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法学数据结构中的 LCFS 哈希
在本节中，我们将了解什么是 LCFS 哈希。这是开放寻址策略之一，该策略更改了冲突解决策略。如果我们检查开放地址方案中的哈希算法，我们可以发现如果两个元素发生冲突，那么优先级较高的一项将被插入到表中，而后续元素必须继续。因此，我们可以说开放寻址方案中的哈希是先进先出标准。
使用 LCFS（后进先出）方案。任务将以相反的方式执行。当我们插入一个元素时，它将放置在位置 x0。如果该位置已被元素 y 占据，因为 yj = x0，那么我们将 y 放置在位置 yj+1，可能会替换一些元素 z，依此类推。
根据 Poblete 和 Munro 的说法，在空表中插入 n 个元素后的预期搜索时间可以通过以下公式限制。
$$E[W]=1+\Gamma^{-1}(\alpha n)\lgroup1+\frac{ln\:ln\:\frac{1}{1+\alpha}}{ln\:\Gamma^{-1}(\alpha n)}+O(\frac{1}{ln^{2}\:\Gamma^{2}(\alpha n)})\rgroup$$
此处 Γ 是伽马函数，且
$$\Gamma^{-1}(\alpha n)=\frac{ln\:n}{ln\:ln\:n}\lgroup1+\frac{ln\:ln\:ln\:n}{ln\:ln\:n}+O(\frac{1}{ln\:ln\:n})\rgroup$$
更新于: 2020-08-11
422 次浏览
广告