c# - Probabilidad de obtener un valor duplicado al llamar a GetHashCode() en cadenas
hashcode equals c# (6)
Corrí una prueba en una base de datos de 466k palabras en inglés y obtuve 48 colisiones con string.GetHashCode() . MurmurHash da resultados ligeramente mejores. Más resultados están aquí: https://github.com/jitbit/MurmurHash.net
Quiero saber la probabilidad de obtener valores duplicados al llamar al método GetHashCode() en instancias de string . Por ejemplo, de acuerdo con esta publicación del blog, blair y brainlessness tienen el mismo código hash (1758039503) en una máquina x86.
Creo que todo lo que se puede decir es "pequeño, pero finito y definitivamente no es cero"; en otras palabras, no debe confiar en que GetHashCode() siempre devuelva valores únicos para dos instancias diferentes.
En mi opinión, los hashcodes se utilizan mejor cuando se quiere saber rápidamente si dos instancias son diferentes, no si son iguales.
En otras palabras, si dos objetos tienen códigos hash diferentes, sabes que son diferentes y no es necesario que realices una comparación más profunda (posiblemente costosa).
Sin embargo, si los códigos hash para dos objetos son iguales, debe continuar comparando los objetos para ver si realmente son lo mismo.
En caso de que su pregunta deba ser cuál es la probabilidad de una colisión en un grupo de cadenas,
Para n ranuras disponibles y m artículos que ocupan:
El problema de no colisión en la primera inserción es 1.
El problema de no colisión en la segunda inserción es (n - 1) / n
El problema de no colisión en la tercera inserción es (n - 2) / n
El problema de no colisión en la inserción mth es (n - (m - 1)) / n
La probabilidad de que no haya colisión después de m inserciones es el producto de los valores anteriores: (n - 1)! / ((N - m)! * N ^ (m - 1)).
lo que simplifica a (n elegir k) / (n ^ m).
Y todo el mundo tiene razón, no puede asumir 0 colisiones, por lo que decir que la probabilidad es "baja" puede ser cierto, pero no le permite asumir que no habrá colisiones. Si estás viendo una tabla hash, creo que la norma es que comienzas a tener problemas con colisiones significativas cuando tienes la tabla hash está a unos 2/3 de su capacidad.
La probabilidad de una colisión entre dos cadenas elegidas al azar es 1/2 1 / 2^(bits in hash code) , si el hash es perfecto, lo que es improbable o imposible.
Pequeño: si está hablando de la posibilidad de que dos cadenas desiguales arbitrarias tengan una colisión. (Dependerá de cuán "arbitrarias" sean las cadenas, por supuesto, los diferentes contextos usarán cadenas diferentes).
Grande: si está hablando de la posibilidad de que haya al menos una colisión en un grupo grande de cadenas arbitrarias. Las pequeñas probabilidades individuales no son compatibles con el problema del cumpleaños .
Eso es todo lo que necesitas saber. Definitivamente hay casos en los que habrá colisiones, y debe darse el caso de que solo hay 2 32 códigos hash posibles, y más que muchas cadenas, por lo que el principio del casillero demuestra que al menos un código hash debe tener más de una cadena. que lo genera. Sin embargo, debes confiar en que el hash ha sido diseñado para ser bastante razonable.
Puede confiar en que es una buena forma de reducir las posibles coincidencias para una cadena en particular. Sería un conjunto inusual de cadenas naturales que generaron muchas colisiones, e incluso cuando hay algunas colisiones, obviamente, si puede limitar una búsqueda de candidatos establecida de 50 K a menos de 10 cadenas, esa es una gran victoria. Pero no debe confiar en él como un valor único para cualquier cadena.
Tenga en cuenta que el algoritmo utilizado en .NET 4 difiere entre x86 y x64, por lo que ese ejemplo probablemente no sea válido en ambas plataformas.
Grande.
(Lo siento Jon!)
La probabilidad de obtener una colisión de hash entre cadenas cortas es extremadamente alta . Dado un conjunto de solo diez mil cadenas cortas distintas extraídas de palabras comunes, la probabilidad de que haya al menos una colisión en el conjunto es aproximadamente del 1%. Si tiene ochenta mil cadenas, la probabilidad de que haya al menos una colisión es más del 50%.
Para obtener un gráfico que muestre la relación entre el tamaño del conjunto y la probabilidad de colisión, vea mi artículo sobre el tema:
http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx