c - tipos - huella hash

Funciones hash simples

Question

Estoy tratando de escribir un programa en C que use una tabla hash para almacenar diferentes palabras y podría usar algo de ayuda.

En primer lugar, creo una tabla hash con el tamaño de un número primo que es el más cercano al número de palabras que tengo que almacenar, y luego uso una función hash para encontrar una dirección para cada palabra. Comencé con la función más simple, agregando las letras juntas, que terminó con un 88% de colisión. Entonces comencé a experimentar con la función y descubrí que, independientemente de lo que cambie, las colisiones no son inferiores al 35%. Ahora mismo estoy usando

unsigned int stringToHash(char *word, unsigned int hashTableSize){
  unsigned int counter, hashAddress =0;
  for (counter =0; word[counter]!=''/0''; counter++){
    hashAddress = hashAddress*word[counter] + word[counter] + counter;
  }
  return (hashAddress%hashTableSize);
}

que es solo una función aleatoria que se me ocurrió, pero me da los mejores resultados: alrededor del 35% de colisión.

He estado leyendo artículos sobre funciones hash durante las últimas horas y traté de usar algunas sencillas, como djb2, pero todas me dieron resultados aún peores (djb2 produjo una colisión del 37%, que es '' Mucho peor, pero esperaba algo mejor que peor. Tampoco sé cómo usar algunos de los otros más complejos, como el murmur2, porque no sé cuáles son los parámetros (key, len , semilla) que toman son.

¿Es normal obtener más del 35% de colisiones, incluso con el uso del djb2, o estoy haciendo algo mal? ¿Cuáles son los valores clave, len y semilla?

Answer 1

En primer lugar, creo una tabla hash con el tamaño de un número primo que es el número de las palabras que tengo que almacenar, y luego uso una función hash para encontrar una dirección para cada palabra.

...

return (hashAddress% hashTableSize);

Dado que el número de hashes diferentes es comparable al número de palabras, no puede esperar tener colisiones mucho más bajas.

Hice una prueba estadística simple con un hash aleatorio (que es lo mejor que podrías lograr) y descubrí que el 26% es la tasa de colisión límite si tienes #words == #hashes diferentes.

Answer 2

Prueba sdbm:

hashAddress = 0;
for (counter = 0; word[counter]!=''/0''; counter++){
    hashAddress = word[counter] + (hashAddress << 6) + (hashAddress << 16) - hashAddress;
}

O djb2:

hashAddress = 5381;
for (counter = 0; word[counter]!=''/0''; counter++){
    hashAddress = ((hashAddress << 5) + hashAddress) + word[counter];
}

O Adler32:

uint32_t adler32(const void *buf, size_t buflength) {
     const uint8_t *buffer = (const uint8_t*)buf;

     uint32_t s1 = 1;
     uint32_t s2 = 0;

     for (size_t n = 0; n < buflength; n++) {
        s1 = (s1 + buffer[n]) % 65521;
        s2 = (s2 + s1) % 65521;
     }     
     return (s2 << 16) | s1;
}

// ...

hashAddress = adler32(word, strlen(word));

Sin embargo, ninguno de estos es realmente genial. Si realmente desea buenos hashes, necesita, por ejemplo, algo más complejo como lookup3 .

Tenga en cuenta que se espera que una tabla hash tenga muchas colisiones tan pronto como se llene en más del 70-80% . Esto es perfectamente normal e incluso sucederá si utiliza un algoritmo hash muy bueno. Es por eso que la mayoría de las implementaciones de tabla hash aumentan la capacidad de la tabla hash (por ejemplo, capacity * 1.5 o incluso capacity * 2 ) tan pronto como se agrega algo a la tabla hash y la relación size / capacity ya está por encima de 0.7 a 0.8. Aumentar la capacidad significa que se crea una nueva tabla hash con una capacidad más alta, todos los valores de la actual se agregan a la nueva (por lo tanto, deben volver a aparecer, ya que su nuevo índice será diferente en la mayoría de los casos), la nueva matriz hastable reemplaza al antiguo y el antiguo se libera / libera. Si planea hacer un hash de 1000 palabras, una capacidad de hashtable de 1250 menos recomendada, mejor de 1400 o incluso de 1500.

Las tablas hash no deben estar "llenas hasta el borde", al menos no si son rápidas y eficientes (por lo tanto, siempre deben tener capacidad de reserva). Esa es la reducción del tamaño de las tablas hash, son rápidas ( O(1) ), aunque normalmente desperdiciarán más espacio del que sería necesario para almacenar los mismos datos en otra estructura (cuando los almacena como una matriz ordenada, solo necesitará una capacidad de 1000 por 1000 palabras; el tamaño reducido es que la búsqueda no puede ser más rápida que O(log n) en ese caso). Una tabla hash sin colisiones no es posible en la mayoría de los casos de ninguna manera. Casi todas las implementaciones de hashtable esperan que se produzcan colisiones y, por lo general, tienen algún tipo de forma de lidiar con ellas (normalmente, las colisiones hacen que la búsqueda sea un poco más lenta, pero la tabla de hash todavía funcionará y en muchos casos superará otras estructuras de datos).

También tenga en cuenta que si está utilizando una función hash bastante buena, no hay ningún requisito, sin embargo, ni siquiera una ventaja, si la tabla hash tiene una capacidad de 2 si está recortando valores hash usando el módulo ( % ) al final. La razón por la que muchas implementaciones de hashtable siempre usan una potencia de 2 capacidades es porque no usan módulo , en lugar de que usan AND ( & ) para recortar porque una operación AND es una de las operaciones más rápidas que encontrará en la mayoría de las CPU (el módulo nunca es más rápido que Y, en el mejor de los casos, sería igualmente rápido, en la mayoría de los casos es mucho más lento). Si su tabla hash utiliza una potencia de 2 tamaños, puede reemplazar cualquier módulo con una operación AND:

x % 4  == x & 3
x % 8  == x & 7
x % 16 == x & 15
x % 32 == x & 31
...

Sin embargo, esto solo funciona para una potencia de 2 tamaños. Si usa el módulo, la potencia de 2 tamaños solo puede comprar algo, si el hash es un hash muy malo con una "distribución de bits" muy mala. Una mala distribución de bits suele deberse a hashes que no utilizan ningún tipo de desplazamiento de bits ( >> o << ) o cualquier otra operación que tenga un efecto similar al desplazamiento de bits.

Creé una implementación de lookup3 simplificada para ti:

#include <stdint.h>
#include <stdlib.h>

#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

#define mix(a,b,c) /
{ /
  a -= c;  a ^= rot(c, 4);  c += b; /
  b -= a;  b ^= rot(a, 6);  a += c; /
  c -= b;  c ^= rot(b, 8);  b += a; /
  a -= c;  a ^= rot(c,16);  c += b; /
  b -= a;  b ^= rot(a,19);  a += c; /
  c -= b;  c ^= rot(b, 4);  b += a; /
}

#define final(a,b,c) /
{ /
  c ^= b; c -= rot(b,14); /
  a ^= c; a -= rot(c,11); /
  b ^= a; b -= rot(a,25); /
  c ^= b; c -= rot(b,16); /
  a ^= c; a -= rot(c,4);  /
  b ^= a; b -= rot(a,14); /
  c ^= b; c -= rot(b,24); /
}

uint32_t lookup3 (
  const void *key,
  size_t      length,
  uint32_t    initval
) {
  uint32_t  a,b,c;
  const uint8_t  *k;
  const uint32_t *data32Bit;

  data32Bit = key;
  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;

  while (length > 12) {
    a += *(data32Bit++);
    b += *(data32Bit++);
    c += *(data32Bit++);
    mix(a,b,c);
    length -= 12;
  }

  k = (const uint8_t *)data32Bit;
  switch (length) {
    case 12: c += ((uint32_t)k[11])<<24;
    case 11: c += ((uint32_t)k[10])<<16;
    case 10: c += ((uint32_t)k[9])<<8;
    case 9 : c += k[8];
    case 8 : b += ((uint32_t)k[7])<<24;
    case 7 : b += ((uint32_t)k[6])<<16;
    case 6 : b += ((uint32_t)k[5])<<8;
    case 5 : b += k[4];
    case 4 : a += ((uint32_t)k[3])<<24;
    case 3 : a += ((uint32_t)k[2])<<16;
    case 2 : a += ((uint32_t)k[1])<<8;
    case 1 : a += k[0];
             break;
    case 0 : return c;
  }
  final(a,b,c);
  return c;
}

Este código no está tan optimizado para el rendimiento como el código original, por lo que es mucho más simple. Tampoco es tan portátil como el código original, pero sí lo es para todas las principales plataformas de consumo que se usan en la actualidad. También está ignorando por completo al endian de la CPU, aunque eso no es realmente un problema, funcionará en las CPU endian grandes y pequeñas. Solo tenga en cuenta que no calculará el mismo hash para los mismos datos en las CPU endian grandes y pequeñas, pero eso no es un requisito; calculará un buen hash en ambos tipos de CPU y solo es importante que siempre calcule el mismo hash para los mismos datos de entrada en una sola máquina.

Deberías usar esta función de la siguiente manera:

unsigned int stringToHash(char *word, unsigned int hashTableSize){
  unsigned int initval;
  unsigned int hashAddress;

  initval = 12345;
  hashAddress = lookup3(word, strlen(word), initval);
  return (hashAddress%hashTableSize);
  // If hashtable is guaranteed to always have a size that is a power of 2,
  // replace the line above with the following more effective line:
  //     return (hashAddress & (hashTableSize - 1));
}

Usted se pregunta qué es initval . Bueno, es lo que quieras que sea. Podrías llamarlo una sal. Influirá en los valores de hash, sin embargo, los valores de hash no mejorarán o empeorarán en calidad debido a esto (aunque al menos no en el caso promedio, puede llevar a más o menos colisiones para datos muy específicos). Por ejemplo, puede usar diferentes valores de initval si desea hacer un hash de los mismos datos dos veces, pero cada vez debe producir un valor de hash diferente (no hay garantía de que lo haga, pero es bastante probable que initval sea ​​diferente; si crea el mismo valor , esto sería una coincidencia muy desafortunada que debes tratar eso como una especie de colisión). No es aconsejable usar diferentes valores de initval valores al hacer hash de los datos para la misma tabla hash (esto causará más colisiones en promedio). Otro uso de initval es si desea combinar un hash con algunos otros datos, en cuyo caso el hash existente se convierte en initval cuando initval los otros datos (por lo tanto, tanto los otros datos como el hash anterior influyen en el resultado del hash). función). Incluso puede establecer initval en 0 si le gusta o elige un valor aleatorio cuando se crea la tabla hash (y siempre use este valor aleatorio para esta instancia de tabla hash, sin embargo, cada tabla hash tiene su propio valor aleatorio).

Una nota sobre colisiones:

Por lo general, las colisiones no son un problema tan grande en la práctica, por lo general no vale la pena desperdiciar toneladas de memoria para evitarlas. La pregunta es, más bien, cómo vas a tratar con ellos de una manera eficiente.

Usted dijo que actualmente está tratando con 9000 palabras. Si estaba usando una matriz no clasificada, encontrar una palabra en la matriz necesitará 4500 comparaciones en promedio. En mi sistema, las comparaciones de 4500 cadenas (suponiendo que las palabras tienen entre 3 y 20 caracteres de longitud) necesitan 38 microsegundos (0,000038 segundos). Así que incluso un algoritmo tan simple e ineficaz es lo suficientemente rápido para la mayoría de los propósitos. Suponiendo que usted está ordenando la lista de palabras y utiliza una búsqueda binaria, encontrar una palabra en la matriz solo necesitará 13 comparaciones en promedio. 13 las comparaciones son casi nulas en términos de tiempo, es muy poco como para compararlo de manera confiable. Entonces, si encontrar una palabra en una tabla hash necesita comparaciones de 2 a 4, ni siquiera perdería ni un segundo en la pregunta de si ese podría ser un gran problema de rendimiento.

En su caso, una lista ordenada con búsqueda binaria puede incluso superar una tabla hash de lejos. Claro, 13 comparaciones necesitan más tiempo que 2 a 4 comparaciones, sin embargo, en el caso de una tabla hash, primero debe codificar los datos de entrada para realizar una búsqueda. ¡Hashing solo puede llevar más de 13 comparaciones! Cuanto mejor sea el hash, más tardará la hash de la misma cantidad de datos. Por lo tanto, una tabla hash solo se amortiza en cuanto al rendimiento si tiene una gran cantidad de datos o si debe actualizarlos con frecuencia (por ejemplo, agregar / eliminar palabras de la tabla constantemente, ya que estas operaciones son menos costosas para una tabla hash que son para una lista ordenada). El hecho de que un hashatble sea O(1) solo significa que, independientemente de su tamaño, la búsqueda se realizará aprox. Siempre necesita la misma cantidad de tiempo. O(log n) solo significa que la búsqueda crece logarítmicamente con el número de palabras, es decir, más palabras, búsqueda más lenta. ¡Sin embargo, la notación Big-O no dice nada acerca de la velocidad absoluta! Este es un gran malentendido. No se dice que un algoritmo O(1) siempre funcione más rápido que uno O(log n) . La notación Big-O solo le dice que si el algoritmo O(log n) es más rápido para un cierto número de valores y usted continúa aumentando el número de valores, el algoritmo O(1) ciertamente superará al algoritmo O(log n) en algún momento, pero el recuento de palabras actual puede estar muy por debajo de ese punto. Sin una evaluación comparativa de ambos enfoques, no puede decir cuál es más rápido con solo mirar la notación Big-O.

Volver a las colisiones. ¿Qué debes hacer si te topas con una colisión? Si el número de colisiones es pequeño, y aquí no me refiero al número total de colisiones (el número de palabras que colisionan en la tabla hash), sino a la del índice (la cantidad de palabras almacenadas en el mismo índice de tabla hash, por lo que en su caso, tal vez 2-4), el enfoque más simple es almacenarlos como una lista enlazada. Si no hubo colisión hasta ahora para este índice de tabla, solo hay un único par clave / valor. Si hubo una colisión, hay una lista enlazada de pares clave / valor. En ese caso, su código debe iterar sobre la lista vinculada y verificar cada una de las claves y devolver el valor si coincide. A juzgar por sus números, esta lista vinculada no tendrá más de 4 entradas y hacer 4 comparaciones es insignificante en términos de rendimiento. Entonces, encontrar el índice es O(1) , encontrar el valor (o detectar que esta clave no está en la tabla) es O(n) , pero aquí n es solo el número de entradas de la lista enlazada (por lo tanto, es 4 como máximo) .

Si el número de colisiones aumenta, una lista enlazada puede reducirse y también puede almacenar una matriz ordenada de pares de clave / valor de tamaño dinámico, lo que permite búsquedas de O(log n) y nuevamente, n es solo el número de claves en esa matriz, no de todas las claves en el hastable. Incluso si hubo 100 colisiones en un índice, encontrar el par clave / valor correcto toma como máximo 7 comparaciones. Eso sigue siendo casi nada. A pesar del hecho de que si realmente tiene 100 colisiones en un índice, o su algoritmo hash no es adecuado para sus datos clave o la tabla hash es demasiado pequeña en capacidad. La desventaja de una matriz ordenada de tamaño dinámico es que agregar / eliminar claves es un poco más trabajo que en el caso de una lista enlazada (código-código, no necesariamente de rendimiento). Por lo tanto, usar una lista vinculada suele ser suficiente si mantiene el número de colisiones lo suficientemente bajo y es casi trivial implementar esa lista vinculada usted mismo en C y agregarla a una implementación de tabla hash existente.

Parece que la mayoría de las implementaciones de tabla hash utilizan un "respaldo a una estructura de datos alternativa" para hacer frente a las colisiones. La desventaja es que requieren un poco más de memoria para almacenar la estructura de datos alternativa y un poco más de código para buscar también claves en esa estructura. También hay soluciones que almacenan colisiones dentro de la tabla hash y que no requieren ninguna memoria adicional. Sin embargo, estas soluciones tienen un par de inconvenientes. El primer inconveniente es que cada colisión aumenta las posibilidades de incluso más colisiones a medida que se agregan más datos. El segundo inconveniente es que mientras los tiempos de búsqueda para las claves disminuyen linealmente con el número de colisiones hasta el momento (y como dije antes, cada colisión lleva a más colisiones a medida que se agregan datos), los tiempos de búsqueda para las claves que no están en la tabla hash disminuyen aún más y al final, si realiza una búsqueda de una clave que no está en la tabla hash (sin embargo, no puede saberlo sin realizar la búsqueda), la búsqueda puede llevar tanto tiempo como una búsqueda lineal en toda la tabla hash (¡¡¡YUCK !!!) . Entonces, si puedes ahorrar la memoria extra, ve a una estructura alternativa para manejar las colisiones.