python - 哈希冲突的预期数量

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