如何计算哈希表中的碰撞次数？已知哈希值重复次数列表

哈希碰撞次数的核心是计算每个哈希值对应的重复数据组中，两两配对的数量总和，具体公式如下：

对于每个哈希值的重复次数n，该组产生的碰撞次数为：
碰撞数 = n * (n - 1) / 2

把所有哈希值对应的这个结果相加，就是整个数据集的总碰撞次数。

举个例子说明 #

假设你的重复次数列表是[1,3,2]：

• 重复次数1的哈希：没有碰撞（1*(1-1)/2=0）
• 重复次数3的哈希：3*(3-1)/2=3次碰撞（3条数据两两组合，共3对）
• 重复次数2的哈希：2*(2-1)/2=1次碰撞
  总碰撞次数就是0+3+1=4次

为什么直接加重复次数不对？ #

你之前把所有重复值相加得到总数据量，是因为n本身就是每个哈希对应的数据条数，所有n的和自然等于总数据量，但这和碰撞次数不是同一个概念——碰撞次数统计的是有多少对数据共享了同一个哈希值，而不是统计重复出现的数据条数。

内容的提问来源于stack exchange，提问作者Rajesh Kumar