哈希表有 m 个槽，使用开放寻址和线性探测来解决冲突。表最初是空的。密钥 k1 被插入到表中，然后是 k2，然后是 k3。解释插入这些键时有 4 个探针的条件？得到 4 个探针的概率是多少？
问问题
585 次
1 回答
0
其实这不是你家庭工作的地方，下次你发布问题时，分析它请专注于研究型问题
但是我创建了一些图表，希望它会有所帮助，
这里有图表的整个问题和答案：kelums.wordpress.com
1 如果 1st 2 键发生冲突
图_1：www.kelums.files.wordpress.com/2014/01/1.png
2 如果 1st 2 键不碰撞 , 1st 键 3rd 键碰撞
图_2：www.kelums.files.wordpress.com/2014/01/2.png
3 如果 1st 2 键不碰撞，则 2nd 键 3rd 键碰撞：
Diagram_3：www.kelums.files.wordpress.com/2014/01/3.png
资源：麻省理工学院讲义
由于每个元素的插入至少需要一个（本术语中只有一个）探针，因此要有 4 个探针，至少需要发生一次碰撞。
如果前两个键发生冲突，我们甚至不需要知道第三个键的散列位置——已经发生了冲突。前两个键碰撞的概率是1/m。
如果前两个键不冲突，则第三个键需要散列到前两个键散列到的两个槽之一，以便发生冲突。发生这种情况的概率是前两个键不冲突的概率与第三个键进入前两个键散列到的两个槽之一的概率的乘积： (m-1)/m *2 /米
至少有 4 个探针的总概率为1/m + (m-1)/m *2/m
于 2013-12-27T05:08:14.803 回答