Queremos cortar algunas cadenas minimizando las colisiones.
Como no tiene ningún requisito de seguridad, debe descartar inmediatamente el uso de una función hash criptográfica como lo sugiere Mahendran Kathirvel.
Las funciones hash recomendadas son los sospechosos habituales de las funciones hash no criptográficas:
- ¿Qué estructuras de datos y algoritmos básicos se deben aprender antes de comenzar la programación competitiva?
- ¿Hay alguien que enseñe estructuras de datos y algoritmos aquí en Hyderabad?
- ¿Qué otras formas fundamentales de compresión de datos, pero la omisión de patrones irrelevantes y la explotación de patrones repetitivos existen?
- ¿Cómo explicarías un 'arreglo' a un principiante en programación?
- ¿Quién sabe qué hay detrás de la API de Google Nearby Search? ¿Qué algoritmo usan? ¿Cómo encuentra Google una estación de servicio cercana?
- Cityhash
- Jenkins
- FNV
- Murmullo
En términos de colisiones, no hay absolutamente ninguna diferencia entre una función hash genérica y una función hash criptográfica . Ambos tienen la misma probabilidad de colisión para un resultado hash de n bits.
Ahora arrojemos algo de luz sobre por qué tanta gente está confundida acerca de las funciones hash criptográficas. Serían necesarios en los siguientes casos:
- Dado un valor hash, necesita que sea muy difícil encontrar una cadena que produzca ese valor hash.
- Si le dan una cadena y su hash, le gustaría que la tarea de encontrar otra cadena que produzca el mismo hash sea difícil. Tenga en cuenta que esto no está relacionado con la probabilidad de colisiones.
- No desea que alguien pueda encontrar dos cadenas que produzcan el mismo hash. Nuevamente, esto no está relacionado con la probabilidad de colisiones.
Si no tiene ninguna de esas necesidades, no necesita una función hash criptográfica y usar una será menos eficiente que usar una función hash genérica.
Podemos hacerlo aún mejor usando una función hash perfecta. Si ya conoce las cadenas que desea hacer hash, puede calcular un hash perfecto y asegurarse de que no habrá colisiones. La compensación es un poco de tiempo de preprocesamiento para construir la función. En general, las funciones hash perfectas son ideales cuando conoce todas las claves y son estáticas, pero existen métodos para crear funciones hash perfectas que admiten agregar nuevas claves dinámicamente.
