programacion - ¿Cómo funciona esta función hash? ¿Estos números son aleatorios?

huella hash

Question

Actualmente estoy leyendo el libro de K & R "The C Programming Language". En el capítulo "Estructuras", bajo el subtema de "Búsqueda de tabla" (Página 144) encontré esta función de generación de hash

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
}

static struct nlist *hashtab[HASHSIZE];

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != ''/0''; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

Lo que no entiendo es lo que esta función realmente hace.

Creo que genera una dirección única (como un índice en hashtab) para la cadena dada (char * s).

Pero creo que a dos cadenas diferentes se les puede dar el mismo índice ya que (hashval% HASHSIZE) es la dirección dada (203% 101 = 405% 101 = 1).

¿Y por qué HASHSIZE 101 y hashval se multiplicaron por 31? ¿Por qué no 100 o 32?

Answer 1

Lo que no entiendo es lo que esta función realmente hace?

Básicamente, hashecha la cadena señalada por el puntero de char *s , hasta que encuentra el final de la cadena, que está marcado por el carácter nulo ''/0'' . En otras palabras, calcula (o mapea ) una cadena de entrada dada a un valor entero.

También puede ver que lo hace examinando cada carácter de la cadena (es decir, el s++ ), haciendo que la complejidad del tiempo de esta función dependa linealmente de la longitud de la cadena --o O(N) - y que evite generar un valor que va más allá de los límites de la matriz con la operación de módulo final.

Creo que genera una dirección única (como un índice en hashtab) para la cadena dada (char * s).

Toma el valor de entrada (es decir, la cadena que se está procesando) y lo utiliza para encontrar el índice dentro de la matriz en la que debe colocarse la cadena. Por lo tanto, técnicamente no se genera una dirección porque la función no devuelve un puntero . La palabra offset sería más precisa aquí.

Pero creo que a dos cadenas diferentes se les puede dar el mismo índice ya que (hashval% HASHSIZE) es la dirección dada (203% 101 = 405% 101 = 1).

Cierto. Esto se llama colisión . Escribir funciones hash que son buenas para evitar colisiones no es fácil. En la mayoría de las discusiones, verá los métodos de resolución de colisiones para manejar estos casos.

Por ejemplo, un método podría consistir en convertir cada elemento de la matriz en un puntero a una lista vinculada donde se añaden los elementos que han colisionado (es decir, hash el mismo valor de índice). Hay otros métodos, pero esa es una discusión diferente.

Idealmente, se usarían funciones hash perfectas porque nunca se generará el mismo valor hash para dos entradas diferentes , lo que hace innecesaria la resolución de colisión.

Hay capítulos de libros escritos sobre estos temas, principalmente cuando se trata de búsquedas, por lo que es posible que desee darles una lectura.

Y ¿Por qué HASHSIZE es 101 y hashval se multiplica por 31 (por qué no 100 o 32)?

Porque 101 y 31 son números primos y, por lo tanto, es menos probable que terminen generando colisiones multiplicándose / dividiéndose en el mismo cubo que una cadena anterior y diferente.

Answer 2

Las funciones hash en general pueden generar el mismo valor hash para diferentes cadenas. Es por eso que se necesita una resolución de colisión .

Sobre el valor de HASHSIZE y hashval: No soy un experto en funciones hash, pero en las pocas que he leído, los números utilizados se obtuvieron empíricamente. Puede leer la respuesta a este otro tema, esto podría ayudarlo.