9
me siento como que estoy pensando demasiado manera este problema, pero aquí va de todos modos ...Número esperado de colisiones hash
Tengo una tabla hash con ranuras M en su matriz interna. Necesito insertar N elementos en la tabla hash. Suponiendo que tengo una función hash que inserta aleatoriamente un elemento en un espacio con la misma probabilidad para cada espacio, ¿cuál es el valor esperado del número total de colisiones hash?
(Disculpa que esto es más una pregunta matemática que una pregunta de programación).
Editar: Aquí hay un código que tengo que simular usando Python. Recibo respuestas numéricas, pero tengo problemas para generalizarla y explicarla.
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
¿cómo se miden las colisiones "triplete"? – wildplasser
Lo que sea que tenga más sentido, supongo. Voy a contarlo como dos colisiones (una por elemento nuevo añadido después de la primera) – numegil
La mejor medida parece ser la cantidad de trabajo para recuperar todos los elementos, que es 'SUM (x * (x + 1)/2) 'con X es la cantidad de elementos en un cubo, y la suma es sobre todos los segmentos. – wildplasser