数据结构中的LCFS散列

在本节中,我们将看到什么是LCFS散列。这是一种开放式寻址策略,它改变了冲突解决策略。如果我们检查开放地址方案中的哈希算法,我们会发现如果两个元素冲突,那么优先级更高的元素将被插入表中,随后的元素必须继续前进。因此,我们可以说开放寻址方案中的哈希是FCFS标准。

采用LCFS(后到先服务)方案。任务完全以相反的方式执行。当我们插入一个元素时,它将被放置在x 0位置。如果该位置已被元素y占据,因为y j = x 0,则我们将y放置在位置y j + 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 $$