I feel like I'm way overthinking this problem, but here goes anyway...
I have a hash table with M slots in its internal array. I need to insert N elements into the hash table. Assuming that I have a hash function that randomly inserts am element into a slot with equal probability for each slot, what's the expected value of the total number of hash collisions?
(Sorry that this is more of a math question than a programming question).
Edit: Here's some code I have to simulate it using Python. I'm getting numerical answers, but having trouble generalizing it to a formula and explaining it.
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
SUM(x * (x+1) /2)
with X is the number of items in a bucket, and the sum is over all buckets.