数据结构中的非对称哈希
在本节中,我们将了解什么是非对称哈希技术。在这种技术中,哈希表被分为d个块。每个分割的长度为n/d。探测值xi0≤i≤d从$$\lbrace\frac{i*n}{d},...,\frac{(i+1)*n}{d-1}统一得出\rbrace$$。与多选散列一样,要插入x,该算法将检查列表A[x0],A[x1],...的长度。。。,A[xd–1]。然后将x附加到这些列表中最短的列表。如果存在平局,则它将x插入到索引最小的列表中。
根据Vocking,不对称哈希的最长列表的预期长度为-
$$E[W]\leq\frac{ln\:ln\:n}{d\:ln\:\phi_{2}}+O(1)$$
功能