我觉得我已经过度思考这个问题,但无论如何……

我有一个哈希表,其内部数组有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

解决方法:

你会在这里找到答案：Quora.com.m桶和n个插入物的预期碰撞次数是

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