预期的哈希冲突数

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