función hash para cadena

Estoy trabajando en una tabla hash en lenguaje C y estoy probando la función hash para string.

La primera función que he intentado es agregar un código ASCII y usar el módulo (% 100), pero obtuve malos resultados con la primera prueba de datos: 40 colisiones por 130 palabras.

Los datos de entrada finales contendrán 8 000 palabras (es un almacén de archivos en un archivo). La tabla hash se declara como tabla int [10000] y contiene la posición de la palabra en un archivo txt.

La primera pregunta es ¿cuál es el mejor algoritmo para el hash string? y cómo determinar el tamaño de la tabla hash?

gracias por adelantado !

:-)

He tenido buenos resultados con djb2Dan Bernstein.

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Primero, generalmente no desea utilizar un hash criptográfico para una tabla hash. Un algoritmo que es muy rápido según los estándares criptográficos sigue siendo insoportablemente lento según los estándares de la tabla hash.

En segundo lugar, desea asegurarse de que cada bit de la entrada puede / afectará el resultado. Una manera fácil de hacerlo es rotar el resultado actual en un cierto número de bits, luego XOR el código hash actual con el byte actual. Repita hasta llegar al final de la cuerda. Tenga en cuenta que, en general, tampoco desea que la rotación sea un múltiplo par del tamaño del byte.

Por ejemplo, suponiendo el caso común de bytes de 8 bits, puede rotar en 5 bits:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

Editar: también tenga en cuenta que 10000 ranuras rara vez es una buena opción para un tamaño de tabla hash. Por lo general, desea una de dos cosas: desea un número primo como el tamaño (requerido para garantizar la corrección con algunos tipos de resolución hash) o una potencia de 2 (por lo que puede reducir el valor al rango correcto con un simple máscara de bits).

Wikipedia muestra una buena función hash de cadena llamada Jenkins One At A Time Hash. También cita versiones mejoradas de este hash.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

Existen varias implementaciones de tablas hash existentes para C, desde la biblioteca estándar C hcreate / hdestroy / hsearch, hasta las de APR y glib , que también proporcionan funciones hash preconstruidas. Recomiendo usarlos en lugar de inventar su propia tabla hash o función hash; Se han optimizado en gran medida para casos de uso comunes.

Sin embargo, si su conjunto de datos es estático, su mejor solución es probablemente usar un hash perfecto . gperf generará un hash perfecto para usted para un conjunto de datos dado.

djb2 ​​tiene 317 colisiones para este diccionario de inglés de 466k, mientras que MurmurHash no tiene ninguno para hashes de 64 bits y 21 para hashes de 32 bits (se esperan alrededor de 25 para hashes aleatorios de 466k de 32 bits). Mi recomendación es usar MurmurHash si está disponible, es muy rápido, ya que toma varios bytes a la vez. Pero si necesita una función hash simple y corta para copiar y pegar en su proyecto, le recomiendo usar soplos versión de un byte a la vez:

uint32_t inline MurmurOAAT32 ( const char * key)
{
  uint32_t h(3323198485ul);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  return h;
}

uint64_t inline MurmurOAAT64 ( const char * key)
{
  uint64_t h(525201411107845655ull);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e9955bd1e995;
    h ^= h >> 47;
  }
  return h;
}

El tamaño óptimo de una tabla hash es, en resumen, tan grande como sea posible sin dejar de encajar en la memoria. Debido a que generalmente no sabemos o queremos buscar cuánta memoria tenemos disponible, e incluso podría cambiar, el tamaño óptimo de la tabla hash es aproximadamente 2 veces el número esperado de elementos que se almacenarán en la tabla. Asignar mucho más que eso hará que su tabla hash sea más rápida pero con rendimientos decrecientes rápidamente, haciendo que su tabla hash sea más pequeña que eso, la hará exponencialmente más lenta. Esto se debe a que existe una compensación no lineal entre el espacio y la complejidad del tiempo para las tablas hash, con un factor de carga óptimo de 2-sqrt (2) = 0.58 ... aparentemente.

Primero, ¿son 40 colisiones de 130 palabras hash a 0..99 mal? No puede esperar un hashing perfecto si no está tomando medidas específicas para que suceda. Una función hash ordinaria no tendrá menos colisiones que un generador aleatorio la mayor parte del tiempo.

Una función hash con buena reputación es MurmurHash3 .

Finalmente, con respecto al tamaño de la tabla hash, realmente depende del tipo de tabla hash que tenga en mente, especialmente si los cubos son extensibles o de una ranura. Si los depósitos son extensibles, nuevamente hay una opción: usted elige la longitud promedio del depósito para las restricciones de memoria / velocidad que tiene.

Sin embargo djb2, como se presenta en stackoverflow por cnicutar , es casi seguro que sea mejor, creo que vale la pena mostrar el K&R hashes de :

1) Aparentemente un algoritmo hash terrible , como se presenta en K&R 1st edition ( fuente )

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) Probablemente un algoritmo hash bastante decente, como se presenta en K&R versión 2 (verificado por mí en la página 144 del libro); NB: asegúrese de eliminar % HASHSIZEde la declaración de devolución si planea hacer el tamaño del módulo a la longitud de su matriz fuera del algoritmo hash. Además, te recomiendo que hagas el tipo return y "hashval" en unsigned longlugar del simple unsigned(int).

unsigned hash(char *s)
{
    unsigned hashval;

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

Tenga en cuenta que, a partir de los dos algoritmos, está claro que una razón por la que el hash de la primera edición es tan terrible es porque NO toma en consideración el orden de los caracteres de la cadena , por hash("ab")lo que devolvería el mismo valor que hash("ba"). Sin embargo, esto no es así con el hash de la 2da edición, que (¡mucho mejor!) Devolvería dos valores diferentes para esas cadenas.

Las funciones de hash GCC C ++ 11 utilizadas para unordered_map(una plantilla de tabla hash) y unordered_set(una plantilla de conjunto hash) parecen ser las siguientes.

• Esta es una respuesta parcial a la pregunta de cuáles son las funciones hash de GCC C ++ 11 , indicando que GCC usa una implementación de "MurmurHashUnaligned2", por Austin Appleby ( http://murmurhash.googlepages.com/ ).
• En el archivo "gcc / libstdc ++ - v3 / libsupc ++ / hash_bytes.cc", aquí ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc ), encontré Las implementaciones. Aquí está el del valor de retorno "32-bit size_t", por ejemplo (obtenido el 11 de agosto de 2017):

Código:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

He probado estas funciones hash y obtuve el siguiente resultado. Tengo alrededor de 960 ^ 3 entradas, cada una de 64 bytes de largo, 64 caracteres en diferente orden, valor hash de 32 bits. Códigos de aquí .

Hash function    | collision rate | how many minutes to finish
==============================================================
MurmurHash3      |           6.?% |                      4m15s
Jenkins One..    |           6.1% |                      6m54s   
Bob, 1st in link |          6.16% |                      5m34s
SuperFastHash    |            10% |                      4m58s
bernstein        |            20% |       14s only finish 1/20
one_at_a_time    |          6.16% |                       7m5s
crc              |          6.16% |                      7m56s

Una cosa extraña es que casi todas las funciones hash tienen una tasa de colisión del 6% para mis datos.

Una cosa que he usado con buenos resultados es la siguiente (no sé si ya se mencionó porque no recuerdo su nombre).

Precalcula una tabla T con un número aleatorio para cada carácter en el alfabeto de su clave [0,255]. Hash tu clave 'k0 k1 k2 ... kN' tomando T [k0] xor T [k1] xor ... xor T [kN]. Puede demostrar fácilmente que esto es tan aleatorio como su generador de números aleatorios y que es computacionalmente muy factible y si realmente se encuentra con una instancia muy mala con muchas colisiones, puede repetir todo usando un nuevo lote de números aleatorios.