预期哈希冲突的数量

Question

我感觉自己对这个问题过于深思熟虑了，但还是来发一波...

我有一个哈希表，在它的内部数组中有M个插槽。 我需要将N个元素插入哈希表中。 假设我有一个哈希函数，以相同概率将元素随机插入到每个插槽中，那么哈希冲突的总数的期望值是多少？

（很抱歉这更像是一个数学问题而不是一个编程问题）。

编辑：

这里有一些我用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

- numegil

---

你希望如何测量“三元组”碰撞？ - wildplasser

无论哪种方式最合理，我想我会将其视为两次碰撞（每个新元素添加后一次）。 - numegil

最佳度量似乎是检索所有项所需的工作量，其公式为 SUM(x * (x+1) /2)，其中 X 是桶中项目的数量，总和是所有桶的总和。 - wildplasser

Answer 1

你可以在这里找到答案：Quora.com。对于 m 个桶和 n 次插入，预期的碰撞次数为 n - m * (1 - ((m-1)/m)^n)。

- Felix Gessert

---

这也在Math StackExchange上有证明。 - ShreevatsaR

以下是编程相关的内容，需要从英语翻译成中文。请只返回翻译后的文本，不要进行解释。Proof: 证明： - MVTC

是否有适用于通用 m 值（如 2^32）的表可用？ - Cyan

在我看来，碰撞数量并不等同于共享同一桶或位置的元素数量。在生日悖论的情境中，如果有4个人共享同一天生日，那么回答后一个问题（共享同一天生日的人数）将是4。然而，对于前一个问题，生日碰撞的数量通常被认为是4-1=3。这背后的原理是，在这四个人当中任意去掉其中的三个，就不会发生碰撞。这个差别很小，但值得注意，以免混淆。 - KGhatak

有没有一种方法可以显示碰撞次数的方差？ - zyxue

Answer 2

SUM(x*(x+1)/2)指标的公式可以在这里找到，而期望值似乎是(n/2m)* (n+2m -1)。

不知道方差，我不是专业人士。

- wildplasser