Usar un prime como radix, especialmente en Rabin-Karp, es muy popular pero totalmente incorrecto .
Lo que debería hacer en su lugar es usar un primo (aleatorio) como módulo , por ejemplo, como el tamaño de su tabla hash en una estructura de datos o como el rango de valores hash válidos en Rabin-Karp. En el hash de estilo Rabin-Karp, para cualquier raíz y para cualquiera de las dos cadenas diferentes, es probable que solo haya un pequeño número finito de módulos primos que producen una colisión. (Si considera las dos cadenas como números grandes, los números primos que producen una colisión son precisamente los números primos que dividen la diferencia de esos dos números). Casi todos los números primos descubrirán que las dos cadenas son distintas. Por lo tanto, un primo seleccionado al azar de un rango adecuado funcionará con una probabilidad muy alta.
(Debido a la paradoja del cumpleaños, si desea esperar cero colisiones, el tamaño de su prima para Rabin-Karp debe ser aproximadamente n ^ 2 o más, donde n es la longitud de la cadena de “pajar”).
- ¿Puede un niño menor de 14 años que es malo en matemáticas aprender a programar juegos?
- No quiero usar las bibliotecas de Python. Quiero hacer los cálculos y escribir el código yo mismo. ¿Qué libros explican las matemáticas y entra en detalles?
- ¿Cuál es la utilidad de gomutra?
- ¿Cuál es la correlación entre las matemáticas y la informática? ¿Por qué es necesario?
- ¿Por qué es tan difícil encontrar documentaciones útiles y completas sobre métodos criptográficos en Internet?
Por otro lado, una mala implementación muy común de Rabin-Karp usa 2 ^ 32 (o 2 ^ 64) como módulo, y algunos primos como radix. ¿Por qué es mala esta implementación? Porque, por ejemplo, es posible construir dos (o incluso múltiples) cadenas diferentes de la misma longitud (muy pequeña) de modo que formen una colisión para cualquier raíz principal impar . Por lo tanto, no hay una función hash de este tipo incorrecto que realmente distinga entre esas dos cadenas. No importa cuán grandes primos intentes, no importa si eliges uno al azar, siempre tendrás una colisión.
