随机预言机模型下哈希函数碰撞的概率qi^2/q怎么来的

对于一个给定的哈希函数，我们可以假设它将任何输入散列到 0 到 q-1 的整数范围内。如果我们有 n 个关键字，那么每个关键字 k 可能被哈希到 q 个位置中的一个位置。随机指定两个关键字 k1 和 k2，它们分别被哈希到哈希表的位置 i1 和 i2，同时假设哈希函数是均匀随机的，则

Pr (i1 = i2) = 1/q

因此，碰撞的概率是：

Pr (k1 和 k2 碰撞) = Pr (i1 = i2) = 1/q

根据定义，随机预言机模型下的哈希函数预言的速度等同于根据概率计算。因此，概率 qi^2/q 表示对于它哈希表中的每个哈希值 qi，我们有 "冲突" n^2/qi 种情况，其中 n 是关键字的数量。所以我们对 qi 进行求和，得到总的冲突数量为 n^2/q。