Así que tengo una tabla hash que puede contener 100 elementos. Actualmente almacena 30 elementos. ¿Cuál es la probabilidad de que las próximas 2 inserciones resulten en al menos una colisión?
Lo que hice fue calcular que el espacio muestral es 100*100=10000, lo que representa todo el número posible de inserciones diferentes para las 2 inserciones (por ejemplo: que la primera inserción esté en el 5º índice y que la segunda inserción esté en el 74º índice).
Luego traté de obtener los elementos del espacio muestral, que tiene la forma de (índice de la primera inserción, índice de la segunda inserción) que tienen colisiones. En primer lugar, conté 30 colisiones de la primera inserción y lo multipliqué por 100, ya que hay 100 posibilidades para la segunda inserción por cada una de la primera inserción. De este modo se obtiene el recuento de las colisiones que están garantizadas desde la primera inserción. Luego multipliqué esto por 2 ya que también hay 30 colisiones desde la segunda inserción y tuve que multiplicar eso por 100 ya que hay 100 posibilidades para la primera inserción para cada una de la segunda inserción. De este modo se obtiene el recuento de colisiones que se garantizan a partir de la segunda inserción. Como esto es sobrecontar el número de colisiones que son iguales (Por ejemplo: si hubo una colisión en el 5º índice, la primera y la segunda inserción están en el 5º índice), resté 30 ya que ese es el conteo de índices ocupados.
Entonces añadí 70 en el caso de que la primera inserción no causara colisión pero la segunda causara colisión al ser insertada en el mismo lugar que la primera.(Por ejemplo ambas inserciones estando en el índice 7 cuando originalmente el índice 7 no estaba ocupado antes de la primera inserción)
Obtuve 0,604 como respuesta final: (2*30*100-30+70)/10000
¿Es esta la respuesta y el enfoque correctos?
