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

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 el siguiente (Por favor, corríjanme si estoy equivocado o por favor agregue 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:

es la función hash utilizado para almacenar/recuperar los datos distintas de una función hash criptográfica utilizado en aplicaciones de seguridad para la autenticación como MD5, HMAC, SHA-1, etc. ..?

¿En qué forma (s) 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 grandioso si pudiera mencionar algunos buenos enlaces para entenderlos mejor.

Answer 1

Bob Jenkins escribió una descripción en profundidad de su buena, aunque ligeramente obsoleta, hash function. 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 vinculadas 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 menciona podrían utilizarse 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

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

Para una función hash típica, el resultado está limitado solo por el tipo, p. Ej. si devuelve un size_t, está perfectamente bien para devolver cualquier posible tamaño_t. 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 debería ser un número primo).

A modo de ejemplo, una función bastante típico de hash normal, podría ser algo 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 tener cada parte de la cadena de entrada afectar el resultado, y (lo más rápido posible) tienen cada parte del resultado afectado 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.

Answer 3

Los objetivos de diseño son diferentes.

Con cryptographic hash functions desea, por ejemplo, que la función hash y la función hash no se puedan utilizar para determinar los datos originales o cualquier otro dato que produzca el mismo hash.

Las funciones hash usadas con tablas hash & 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).