example - función hash para cadena

hashing c++

Question

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

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

Los datos de entrada finales contendrán 8 000 palabras (es un dictionario almacena 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 hash string? y cómo determinar el tamaño de la tabla hash?

gracias por adelantado !

:-)

Answer 1

Aunque djb2 , como se presenta en por cnicutar , es casi seguro que mejor, creo que vale la pena mostrar también los hashes de K&R :

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

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 % HASHSIZE de la declaración return si planea hacer el módulo sizing-to-your-array-length fuera del algoritmo hash. Además, te recomiendo que hagas el retorno y el tipo "hashval" unsigned long lugar 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 es claro a partir de los dos algoritmos que una razón por la cual el hash de 1ra edición es tan terrible es porque NO toma en consideración el orden de caracteres de cadena, por lo que hash("ab") devolvería el mismo valor que hash("ba") . Sin embargo, esto no es así con el hash de 2ª 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 de hash) parecen ser las siguientes.

• This es una respuesta parcial a la pregunta de cuáles son las funciones de hash GCC C ++ 11 utilizadas , indicando que GCC usa una implementación de "MurmurHashUnaligned2", de 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 (retirado 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;
}

Answer 2

En primer lugar, ¿son malas 40 colisiones para 130 palabras hashed a 0..99? No se puede esperar un hash perfecto si no se toman medidas específicas para que ocurra. 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 segmentos son extensibles o de una ranura. Si los cubos son extensibles, nuevamente hay una opción: usted elige la longitud promedio del cucharón para las restricciones de memoria / velocidad que tiene.

Answer 3

En primer lugar, 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.

Segundo, quiere asegurarse de que cada bit de la entrada pueda / afectará el resultado. Una manera fácil de hacerlo es girar el resultado actual por un número de bits, luego XOR el código hash actual con el byte actual. Repita hasta llegar al final de la cadena. Tenga en cuenta que generalmente no desea que la rotación sea un múltiplo par del tamaño del byte tampoco.

Por ejemplo, asumiendo 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: o bien desea un número primo como el tamaño (necesario 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).

Answer 4

Hay una cantidad de implementaciones de tablas hash para C, desde la biblioteca estándar de C hcreate / hdestroy / hsearch, hasta las de APR y glib , que también proporcionan funciones de hash precompiladas. Recomiendo usarlos en lugar de inventar tu propia función hashtable o hash; han sido optimizados en gran medida para casos de uso comunes.

Si su conjunto de datos es estático, sin embargo, su mejor solución es, probablemente, utilizar un hash perfecto . gperf generará un hash perfecto para ti para un conjunto de datos determinado.

Answer 5

Probé estas funciones hash y obtuve el siguiente resultado. Tengo alrededor de 960 ^ 3 entradas, cada una de 64 bytes de longitud, 64 caracteres en orden diferente, valor hash de 32 bits. Códigos de here .

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.

Answer 6

Una cosa que he usado con buenos resultados es la siguiente (no sé si ya se menciona 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] xo 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 muy factible desde el punto de vista computacional, y si realmente se encuentra con una instancia muy mala con muchas colisiones, puede repetir todo con un nuevo lote de números aleatorios.

Answer 7

Wikipedia muestra una bonita función de hash de cuerda 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;
}

Answer 8

He tenido buenos resultados con djb2 de Dan 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;
}