考虑一个可扩展哈希索引，它的每个bin都适合N条目。溢出的垃圾箱应该是多少对待追溯?"对待retroactively"意思是所有的bin记录都要转移到创建的两个新箱子之一。
我为N = 2,3,4创建了箱子，但我找不到一个模式。对于N = 2，我创建了6个箱子，对于N = 3，我创建了14个箱子，对于N = 4，我创建了28个箱子。概率大概是这样的:2/.....，因为我们有两个箱子可以存储分裂后的所有原始值，但是我不能把N放在概率中。
任何帮助都是感激的!
溢出的容器应该被追溯处理的概率取决于容器中的条目数和哈希表中的容器数
假设我们在哈希表中有m个桶，每个桶最多可以存储N个条目——一个桶溢出k个条目的概率由二项分布的概率质量函数
给出P(k) = C(N,k) * (1/m)^k * (1 - 1/m)^(N-k) //where C(N,k) is the binomial coefficient
如果一个容器溢出了k个条目——我们需要创建两个新容器并将所有k个条目转移到其中一个——我们选择正确的容器的概率是1/2——溢出的容器应该被追溯处理的概率是
P_retro = sum(k=0 to N-1) P(k) * 1/2
我们对所有可能的k值求和，从0到N-1，因为如果一个bin溢出了N个或更多的条目——我们不能追溯处理
插入值查找模式
- for N=2 and m=6
P_retro = sum(k=0 to 1) C(2,k) * (1/6)^k * (5/6)^(2-k) * 1/2
= (1/6)^0 * (5/6)^2 * 1/2 + C(2,1) * (1/6)^1 * (5/6)^1 * 1/2
= 5/24
- for N=3 and m=14
P_retro = sum(k=0 to 2) C(3,k) * (1/14)^k * (13/14)^(3-k) * 1/2
= (1/14)^0 * (13/14)^3 * 1/2 + C(3,1) * (1/14)^1 * (13/14)^2 * 1/2 + C(3,2) * (1/14)^2 * (13/14)^1 * 1/2
= 71/364
- for N=4 and m=28
P_retro = sum(k=0 to 3) C(4,k) * (1/28)^k * (27/28)^(4-k) * 1/2
= (1/28)^0 * (27/28)^4 * 1/2 + C(4,1) * (1/28)^1 * (27/28)^3 * 1/2 + C(4,2) * (1/28)^2 * (27/28)^2 * 1/2 + C(4,3) * (1/28)^3 * (27/28)^1 * 1/2
= 1073/54912
随着N和m的增加——追溯处理的概率应该会降低(因为一个满是许多条目的容器的概率变小了)
随着N的增加——追溯处理的概率应该会增加(更有可能有N-1或更少的条目溢出)
N, m和P_retro之间的确切关系尚不清楚，需要进一步分析