Colisiones de Hash
Las funciones de hash no son perfectas; a veces, datos completamente distintos pueden generar el mismo resultado de hash. Esto rompe la correspondencia uno a uno entre los datos originales y el valor resultante. En ocasiones, puede que distintas cadenas produzcan el mismo hash, o que un par de números comparta el mismo valor de hash. Las colisiones de hash pueden generar problemas de seguridad y afectar el rendimiento, según el contexto en el que ocurran. Por ejemplo, una función de hash sencilla que asigne un par de enteros a un valor de hash puede mapear muchos pares (a, b) al mismo valor de hash:
Aquí presentamos varios ejemplos de pares
(a, b) que producen el mismo valor de hash:- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Entonces, si tuviéramos una lista de pares diseñados específicamente para tener el mismo hash, surgirían muchas colisiones, y buscar un valor o verificar si el par
(a, b) está en la lista podría volverse muy ineficiente o incluso erróneo (dependiendo de la implementación).Las colisiones de hash también pueden ser una fuente de vulnerabilidades de seguridad. Normalmente, las contraseñas de los usuarios se guardan como hashes por razones de seguridad (para evitar que se filtren las contraseñas incluso si la base de datos es hackeada). Si la función de hash no es buena y provoca muchas colisiones, los atacantes podrían ingresar sin acertar la contraseña real. Si el hash de una contraseña aleatoria coincide con el de la contraseña original, el sistema considera que es la misma persona.
Una buena función de hash ayuda a minimizar la probabilidad de colisiones. Por lo general, las funciones de hash integradas funcionan bastante bien para datos aleatorios. Sin embargo, si los datos de entrada tienen algunas características particulares, o el problema presenta requisitos específicos, será necesario implementar una función de hash personalizada.
Desafío: Verificar Colisiones
Dada una función de hash
h que asigna un par de enteros (a, b) a un entero, se te pide determinar si la función h es lo suficientemente buena. El programa debe revisar si hay colisiones y mostrar Yes si no existen colisiones, o No en caso contrario. La función de hash se define como:Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ 10 000), que representa el número de pares.Las siguientes
n líneas contienen los pares de enteros separados por espacio (0 ≤ ≤ ). Se garantiza que los pares dados son únicos.Salida
El programa debe imprimir
Yes si h(a, b) logra evitar colisiones para los datos proporcionados, y No en caso contrario.Ejemplos
Entrada | Salida |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB