数据结构中的非对称散列

在本节中，我们将学习什么是非对称散列技术。在此技术中，散列表被拆分为 d 个块，每个拆分长度为 n/d。探测值 xi，0 ≤ i ≤ d，从 $$\lbrace\frac{i*n}{d},...,\frac{(i+1)*n}{d-1}\rbrace$$ 中均匀提取。与多选散列一样，要插入 x，算法将检查列表 A[x₀], A[x₁], . . ., A[x_{d – 1}] 的长度。然后将 x 附加到这些列表中最短的一个。如果出现平局，则将 x 插入具有最小索引的列表中。

根据 Vocking，非对称散列最长列表的预期长度为 −

$$E[W]\leq\frac{ln\:ln\:n}{d\:ln\:\phi_{2}}+O(1)$$

函数 𝜙_𝑑 是黄金比例的推广，因此 $$\phi_{2}=\frac{(1+\sqrt{5})}{2}$$

Arnab Chakraborty

更新于: 11-8-2020

220 次浏览

开启你的 职业

通过完成课程获得认证

开始吧