tablas - ¿Cómo escribir una función hash en C?

tablas hash aplicaciones

Question

Se dice que las tablas hash son la forma más rápida / mejor de almacenar / recuperar datos.

Mi comprensión de una tabla hash, hash es la siguiente (Corrígeme si me equivoco o añada si hay algo más):

• Una tabla Hash no es más que una matriz (simple o multidimensional) para almacenar valores.
• Hashing es el proceso para encontrar el índice / ubicación en la matriz para insertar / recuperar los datos. Usted toma un elemento (s) de datos y lo pasa como una clave (s) a una función hash y obtendrá el índice / ubicación donde insertar / recuperar los datos.

Tengo una pregunta:

¿La función hash se usa para almacenar / recuperar los datos DIFERENTE de una función hash criptográfica utilizada en aplicaciones de seguridad para autenticación como MD5, HMAC, SHA-1, etc.?

¿De qué manera son diferentes?

• ¿Cómo escribir una función hash en C?
• ¿Hay algún estándar o pautas para ello?
• ¿Cómo nos aseguramos de que la salida de una función hash, es decir, el índice, no esté fuera de rango?

Sería genial si pudieras mencionar algunos buenos enlaces para entenderlos mejor.

Answer 1

Bob Jenkins escribió una descripción en profundidad de su buena, aunque ligeramente anticuada, función hash . El artículo tiene enlaces a funciones hash más nuevas y mejores, pero la descripción aborda las preocupaciones de construir una buena.

Además, la mayoría de las implementaciones de tablas hash realmente usan una matriz de listas enlazadas para resolver colisiones. Si solo quieres usar una matriz, entonces la función hash necesita verificar las colisiones y crear un nuevo índice hash.

Las funciones hash criptográficas que mencione podrían usarse como funciones hash para una tabla hash, pero son mucho más lentas que las funciones hash diseñadas para una tabla hash. La velocidad hace que los ataques de fuerza bruta sean más fáciles.

Answer 2

Los objetivos de diseño son diferentes.

Con las funciones hash criptográficas , quiere, por ejemplo, que la función hash y la función hash no se puedan usar para determinar los datos originales o cualquier otro dato que produzca el mismo hash.

Las funciones hash usadas con tablas hash y otras estructuras de datos no necesitan tales propiedades de seguridad. A menudo es suficiente si la función hash es rápida y distribuirá el conjunto de entrada de manera uniforme en el conjunto de hashes posibles (para evitar clustering innecesarios / colisiones).

Answer 3

Un hash criptográfico hace hincapié en que sea difícil para cualquiera crear intencionalmente una colisión. Para una tabla hash, normalmente se hace hincapié en producir una distribución razonable de los resultados rápidamente . Como tal, los dos suelen ser bastante diferentes (en particular, un hash criptográfico es normalmente mucho más lento).

Para una función hash típica, el resultado está limitado solo por el tipo; por ejemplo, si devuelve un tamaño_t, está perfectamente bien para devolver cualquier size_t posible. Depende de usted reducir ese rango de salida al tamaño de su tabla (por ejemplo, utilizando el resto de la división por el tamaño de su tabla, que a menudo debe ser un número primo).

Como ejemplo, una función hash normal bastante típica podría ser algo así como:

// warning: untested code.
size_t hash(char const *input) { 

    const int ret_size = 32;
    size_t ret = 0x555555;
    const int per_char = 7;

    while (*input) { 
        ret ^= *input++;
        ret = ((ret << per_char) | (ret >> (ret_size - per_char));
   }
   return ret;
}

La idea básica aquí es hacer que cada bit de la cadena de entrada afecte el resultado, y para (tan rápido como sea posible) que cada parte del resultado se vea afectada por al menos parte de la entrada. Tenga en cuenta que no lo recomiendo particularmente como una gran función hash, solo intento ilustrar algunos de los conceptos básicos de lo que está tratando de lograr.