9
czuję jakbym sposób overthinking ten problem, ale tu idzie tak ...Przewidywana liczba kolizji hash
Mam tabeli mieszania ze szczelinami M w swojej wewnętrznej tablicy. Potrzebuję wstawić N elementów do tabeli mieszania. Zakładając, że mam funkcję skrótu, która losowo wstawia element am do slotu z równym prawdopodobieństwem dla każdego boksu, jaka jest oczekiwana wartość całkowitej liczby kolizji mieszania?
(Niestety, jest to raczej pytanie matematyczne niż pytanie dotyczące programowania).
Edytuj: Oto kod, który muszę zasymulować za pomocą Pythona. Otrzymuję odpowiedzi numeryczne, ale mam problem z uogólnieniem go do formuły i wyjaśnieniem.
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
Jak mierzyć kolizje "trójki"? – wildplasser
Cokolwiek ma największy sens, tak myślę. Więc liczę to jako dwie kolizje (jedna na każdy nowy element dodany po pierwszym) – numegil
Najlepszą miarą wydaje się ilość pracy do odzyskania wszystkich pozycji, czyli SUM (x * (x + 1)/2) 'with X to liczba elementów w wiadrze, a suma jest nad wszystkimi zasobnikami. – wildplasser