9
は、私はその内部配列におけるMスロットでハッシュテーブルを持っている予想される数
...私は方法この問題をoverthinkingてるように感じるが、ここではとにかく行きます。私はハッシュテーブルに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
"トリプレット"衝突の測定方法を教えてください。 – wildplasser
私が思うところは何でも一番意味があります。だから私は2つの衝突（最初の要素の後に追加された新しい要素につき1つ）を数えて行くつもりです – numegil
最良の尺度は、すべての項目を取り出すための仕事の量であるように見えます。これは 'SUM（x *（x + 1）/ 2） 'Xはバケット内の項目の数であり、合計はすべてのバケット上にあります。 – wildplasser