9
mi sento come sto modo overthinking questo problema, ma qui va comunque ...Numero previsto di collisioni hash
Ho una tabella hash con slot M nella sua matrice interna. Ho bisogno di inserire N elementi nella tabella hash. Supponendo che disponga di una funzione hash che inserisce casualmente un elemento in uno slot con uguale probabilità per ogni slot, qual è il valore atteso del numero totale di collisioni hash?
(Mi spiace che si tratti più di una questione di matematica che di una domanda di programmazione).
Modifica: Ecco un codice che devo simulare usando Python. Ricevo risposte numeriche, ma ho problemi a generalizzarlo a una formula e a spiegarla.
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
come si desidera misurare le collisioni "triplette"? – wildplasser
Indipendentemente da ciò che ha più senso. Quindi andrò contando come due collisioni (una per ogni nuovo elemento aggiunto dopo il primo) – numegil
La misura migliore sembra essere la quantità di lavoro per recuperare tutti gli elementi, che è 'SUM (x * (x + 1)/2) 'con X è il numero di elementi in un bucket e la somma è su tutti i bucket. – wildplasser