Ожидаемое количество хеш-коллизий

Question

Я чувствую, что переосмысливаю эту проблему, но все равно ...

У меня есть хеш-таблица с М слотами во внутреннем массиве. Мне нужно вставить N элементов в хэш-таблицу. Предполагая, что у меня есть хеш-функция, которая случайным образом вставляет элемент am в слот с равной вероятностью для каждого слота, каково ожидаемое значение общего числа коллизий хеша?

(Извините, это вопрос математики, а не вопроса программирования).

Edit: Вот некоторый код, который я должен имитировать, используя 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) может быть найдена здесь , а ожидаемое значение выглядит как (n/2m)* (n+2m -1).

Не знаю о дисперсии, IANAM.