Considere una tabla hash con 100 ranuras. Las colisiones se resuelven mediante enstringmiento. Suponiendo un hashing uniforme simple, ¿cuál es la probabilidad de que las primeras 3 ranuras estén vacías después de las primeras 3 inserciones?
(A) (97 × 97 × 97)/100 3
(B) (99 × 98 × 97)/100 3
(C) (97 × 96 × 95)/100 3
(D) (97 × 96 × 95)/ (3! × 100 3 )
Respuesta: (A)
Explicación: La función hash uniforme simple es una función hash hipotética que distribuye uniformemente los elementos en las ranuras de una tabla hash. Además, cada elemento que se va a codificar tiene la misma probabilidad de colocarse en una ranura, independientemente de los otros elementos ya colocados. (Fuente:https://en.wikipedia.org/wiki/SUHA_%28computer_science%29 ).
Probability that the first 3 slots are unfilled after the first 3 insertions =
(probability that first item doesn't go in any of the first 3 slots)*
(probability that second item doesn't go in any of the first 3 slots)*
(probability that third item doesn't go in any of the first 3 slots)
= (97/100) * (97/100) * (97/100)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA