为什么在使用开放寻址作为冲突解决技术和线性探测的散列中的主聚类上下文中，接下来填充 i 个满槽的空槽的概率是 (i + 1)/m？这是算法简介 CLRS 的摘录“占用槽的长运行会累积，增加平均搜索时间。簇的出现是因为前面有 i 个满槽的空槽接下来会以 (i + 1)/m 的概率填充。长运行占用的槽位往往会变长，平均搜索时间也会增加。” 请帮忙。
我想我得到了答案。
对于前面有 i 个满槽的空槽（例如 j），接下来要填充的元素应该散列到任何 i 个槽或槽 j。书上说：
我们假设任何给定的元素都同样可能散列到 m 个槽中的任何一个，而与任何其他元素散列到的位置无关。
即一个元素散列到任意槽 k 的概率是 1/m。
所以，所需的概率是
( 1/m + 1/m + ... i 次 ) + 1/m {对于插槽 j} = (i+1)/m