预期的哈希冲突数

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).