哈希冲突的预期数量

Question

我觉得我可能想得太复杂了，不过还是说说吧……

我有一个哈希表，里面有M个位置（槽）。我需要把N个元素放进这个哈希表。假设我有一个哈希函数，它可以随机把一个元素放到每个位置上，每个位置被选中的概率是一样的。那么，哈希冲突的总数的期望值是多少呢？

（抱歉，这个问题更像是数学问题，而不是编程问题）。

编辑：
我有一些用Python写的代码来模拟这个过程。我得到了数字答案，但在把它概括成公式和解释方面有点困难。

import random
import pdb

N = 5
M = 8

NUM_ITER = 100000

def get_collisions(table):
    col = 0
    for item in table:
        if item > 1:
            col += (item-1)
    return col

def run():
    table = [0 for x in range(M)]

    for i in range(N):
        table[int(random.random() * M)] += 1

    #print table
    return get_collisions(table)

# Main

total = 0
for i in range(NUM_ITER):
    total += run()

print float(total)/NUM_ITER

Answer 1

关于这个 SUM(x*(x+1)/2) 公式的详细信息，可以在 这里 找到。而这个 期望值 看起来是 (n/2m)* (n+2m -1)。

至于方差，我就不太清楚了，我不是这个领域的专家。

Answer 2

你可以在这里找到答案：Quora.com。对于m个桶和n次插入操作，预计会发生的碰撞次数可以用下面这个公式来计算：

n - m * (1 - ((m-1)/m)^n).