Funciones de Hash
Una función de hash es aquella que convierte una serie de datos en otra serie de datos más corta (generalmente en una simple variable entera de 32 o 64 bits).
Esto es especialmente útil para poder identificar/representar una secuencia de datos de una forma mucho más rápida y eficiente. Pero hay que tener en cuenta que existen infinitas secuencias de datos que dan como resultado el mismo código de hash por lo que no es un proceso reversible, es decir, es prácticamente imposible obtener la secuencia de datos con la que fue calculado el hash a partir del propio hash.
Por ejemplo, es muy útil para codificar cadenas de caracteres y de esta forma poder realizar búsquedas mucho más rápidamente, o como simple sistema de indexación de datos.
También se utilizan en criptografía y como sistemas de comprobación de integridad de los datos, algunos ejemplos de este tipo de funciones de hash son la CRC, MD5, MD4, Tiger, RMD, SHA, etc.
El principal problema surge cuando es imprescindible que cada secuencia de datos tenga un identificador hash único, si dos o más secuencias tienen el mismo hash se produce una colisión de hash. En este ejemplo las cadenas “Jirafa” y “Tigre” tienen el mismo hash, 02.
Existen infinitas formas de hacer una función de hash y puedes crear la tuya propia fácilmente, el problema es conseguir que la función genere una buena distribución de los hashes y, a ser posible, que produzca las menores colisiones posibles incluso con secuencias de datos muy cortas y similares. Por eso es recomendable utilizar alguna de las muchas funciones de hash que se utilizan desde hace tiempo y están muy probadas.
Aqui dejo un video del MIT de introducción a las técnicas de hashing:
Sin mas historias vamos con algunas de las funciones de hashing de 32 bits más básicas y utilizadas:
Esta surgió de una idea presentada al comité del IEEE POSIX P1003.2 por Glenn Fowler y Phong Vo en 1991, luego Landon Curt Noll la mejoró.
Funciona muy bien, es rápida y produce pocas colisiones. Realiza una buena dispersión de los hashes y va muy bien para hacer hashing en cadenas casi idénticas como URLs, URIs, IPs, nombres de archivo, etc.
1 2 3 4 5 6 7 8 9 10 11 12 | UI32 HashFNV(const char *data, UI32 len) { const UI32 fnv_prime = 0x811C9DC5; UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash *= fnv_prime; hash ^= (*data); } return(hash); } |
Esta es del profesor Daniel J. Bernstein, es una de las más eficientes:
1 2 3 4 5 6 7 8 9 10 | UI32 HashDJB(const char *data, UI32 len) { UI32 hash = 5381; for(UI32 i=0; i < len; data++, i++) { hash = ((hash << 5) + hash) + (*data); } return(hash); } |
Esta es de Donald E. Knuth, está en el volumen III de su libro “The Art of Computer Programming”:
1 2 3 4 5 6 7 8 9 10 | UI32 HashDEK(const char *data, UI32 len) { UI32 hash = len; for(UI32 i=0; i < len; data++, i++) { hash = ((hash << 5) ^ (hash >> 27)) ^ (*data); } return(hash); } |
Esta está basada en el trabajo de Peter J. Weinberger de los laboratorios AT&T.
En el libro “Compilers (Principles, Techniques and Tools)” se recomienda su uso:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | UI32 HashPJW(const char *data, UI32 len) { const UI32 bits_in_ui32 = (UI32)(sizeof(UI32) * 8); const UI32 three_quarters = (UI32)((bits_in_ui32 * 3) / 4); const UI32 one_eighth = (UI32)(bits_in_ui32 / 8); const UI32 high_bits = (UI32)(0xFFFFFFFF) << (bits_in_ui32 - one_eighth); UI32 test = 0; UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash = (hash << one_eighth) + (*data); if((test = hash & high_bits) != 0) { hash = ((hash ^ (test >> three_quarters)) & (~high_bits)); } } return(hash); } |
Esta es muy similar a la PJW, pero está optimizada para procesadores de 32 bits.
Se utiliza en la mayoría de los sistemas UNIX:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | UI32 HashELF(const char *data, UI32 len) { UI32 x = 0; UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash = (hash << 4) + (*data); if((x = hash & 0xF0000000) != 0) { hash ^= (x >> 24); } hash &= ~x; } return(hash); } |
Esta es del libro “The C Programming Language” de Dennis Ritchie y Brian Kernighan:
1 2 3 4 5 6 7 8 9 10 11 | UI32 HashBKDR(const char *data, UI32 len) { const UI32 seed = 131; UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash = (hash * seed) + (*data); } return(hash); } |
Esta es una función de hash del libro “Algorithms in C” de Robert Sedgwicks:
1 2 3 4 5 6 7 8 9 10 11 12 13 | UI32 HashRS(const char *data, UI32 len) { UI32 a = 63689; UI32 b = 378551; UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash = hash * a + (*data); a = a * b; } return(hash); } |
Esta es una función de hash de Justin Sobel:
1 2 3 4 5 6 7 8 9 10 | UI32 HashJS(const char *data, UI32 len) { UI32 hash = 1315423911; for(UI32 i=0; i < len; data++, i++) { hash ^= ((hash << 5) + (*data) + (hash >> 2)); } return(hash); } |
Esta realiza una buena distribución de los hash en muchos tipos diferentes de secuencias de datos:
1 2 3 4 5 6 7 8 9 10 | UI32 HashSDBM(const char *data, UI32 len) { UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash = (*data) + (hash << 6) + (hash << 16) - hash; } return(hash); } |
Esta realiza un simple hashing rotativo/aditivo:
1 2 3 4 5 6 7 8 9 10 | UI32 HashBP(const char *data, UI32 len) { UI32 hash = 0; for(UI32 i=0; i < len; data++, i++) { hash = (hash << 7) ^ (*data); } return(hash); } |
Y por último, ésta hecha a partir de las anteriores, también es una mezcla de hash rotativo y aditivo:
1 2 3 4 5 6 7 8 9 10 11 | UI32 HashAP(const char *data, UI32 len) { UI32 hash = 0xAAAAAAAA; for(UI32 i=0; i < len; data++, i++) { hash ^= ((i & 1) == 0) ? ((hash << 7) ^ (*data) * (hash >> 3)) : (~((hash << 11) + ((*data) ^ (hash >> 5)))); } return(hash); |