预期的哈希冲突数

Question

我觉得我对这个问题想得太多了，但不管怎样……

我有一个哈希表，它的内部数组中有M个槽。我需要在哈希表中插入N个元素。假设我有一个散列函数，它以相等的概率将am元素随机插入到一个插槽中，那么散列冲突总数的期望值是多少？

(抱歉，这更像是一个数学问题，而不是编程问题)。

编辑:下面是我用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

你可以在这里找到答案：Quora.com。m存储桶和n插入的预期冲突数为

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

Answer 2

SUM(x*(x+1)/2)指标的公式可以找到here，并且期望值看起来是(n/2m)* (n+2m -1)。

不知道方差，IANAM。