c++ - example - ¿Cuál es el mejor algoritmo hash para usar en una cadena stl cuando se usa hash_map?

unordered_map c++

Question

Descubrí que la función de hash estándar en VS2005 es extremadamente lenta cuando intento lograr búsquedas de alto rendimiento. ¿Cuáles son algunos buenos ejemplos de algoritmos hashing rápidos y eficientes que deberían anular la mayoría de las colisiones?

Answer 1

Boost tiene una biblioteca boost::hash que puede proporcionar algunas funciones hash básicas para los tipos más comunes.

Answer 2

De algún viejo código mío:

/* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
static const size_t InitialFNV = 2166136261U;
static const size_t FNVMultiple = 16777619;

/* Fowler / Noll / Vo (FNV) Hash */
size_t myhash(const string &s)
{
    size_t hash = InitialFNV;
    for(size_t i = 0; i < s.length(); i++)
    {
        hash = hash ^ (s[i]);       /* xor  the low 8 bits */
        hash = hash * FNVMultiple;  /* multiply by the magic number */
    }
    return hash;
}

Es rápido. Realmente volviendo loco.

Answer 3

Desde funciones Hash hasta abajo :

MurmurHash hizo bastante popular, al menos en los círculos de desarrolladores de juegos, como una "función hash general".

Es una buena elección, pero veamos más adelante si podemos hacerlo mejor en general. Otra buena opción, especialmente si sabes más acerca de tus datos que "va a ser un número desconocido de bytes", es hacer tuyos (por ejemplo, ver las respuestas de Won Chun, o los xxHash / Murmur modificados de Rune que están especializados para teclas de 4 bytes etc.). Si conoce sus datos, siempre intente ver si ese conocimiento puede usarse para obtener buenos resultados.

Sin más información, recomendaría MurmurHash como una función hash no criptográfica de propósito general. Para cadenas pequeñas (del tamaño del identificador promedio en programas), los muy simples y famosos djb2 y FNV son muy buenos.

Aquí (tamaños de datos <10 bytes) podemos ver que la inteligencia de ILP de otros algoritmos no llega a mostrarse, y la súper simplicidad de FNV o djb2 gana en rendimiento.

djb2

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;
}

FNV-1

hash = FNV_offset_basis
for each byte_of_data to be hashed
     hash = hash × FNV_prime
     hash = hash XOR byte_of_data
return hash

FNV-1

hash = FNV_offset_basis
for each byte_of_data to be hashed
     hash = hash XOR byte_of_data
     hash = hash × FNV_prime
return hash

Una nota sobre seguridad y disponibilidad

Las funciones hash pueden hacer que su código sea vulnerable a ataques de denegación de servicio. Si un atacante puede forzar a su servidor a manejar demasiadas colisiones, es posible que su servidor no pueda hacer frente a las solicitudes.

Algunas funciones hash, como MurmurHash aceptan una semilla que puede proporcionar para reducir drásticamente la capacidad de los atacantes para predecir los hashes que está generando su software de servidor. Mantenlo en mente.

Answer 4

Eso siempre depende de su conjunto de datos.

Por mi parte, obtuve resultados sorprendentemente buenos al usar el CRC32 de la cuerda. Funciona muy bien con una amplia gama de conjuntos de entrada diferentes.

Muchas implementaciones de CRC32 son fáciles de encontrar en la red.

Editar: casi olvidado: esta página tiene un buen tiroteo con función hash con números de rendimiento y datos de prueba:

http://smallcode.weblogs.us/ <- más abajo en la página.

Answer 5

He usado el hash de Jenkins para escribir una biblioteca de filtros Bloom, tiene un gran rendimiento.

Los detalles y el código están disponibles aquí: http://burtleburtle.net/bob/c/lookup3.c

Esto es lo que Perl usa para su operación de hashing, fwiw.

Answer 6

Hice un poco de búsqueda y, curiosamente, el pequeño algoritmo de Paul Larson apareció aquí http://www.strchr.com/hash_functions teniendo la menor cantidad de colisiones probadas en una serie de condiciones, y es muy rápido para una que es desenrollado o conducido por la mesa.

Larson es el simple multiplicar por 101 y agregar el ciclo de arriba.

Answer 7

Python 3.4 incluye un nuevo algoritmo hash basado en SipHash . PEP 456 es muy informativo.

Answer 8

Si está mezclando un conjunto fijo de palabras, la mejor función hash es a menudo una función hash perfecta . Sin embargo, generalmente requieren que el conjunto de palabras que está intentando hacer hash sea conocido en tiempo de compilación. La detección de palabras clave en un lexer (y la traducción de palabras clave a tokens) es un uso común de funciones hash perfectas generadas con herramientas como gperf . Un hash perfecto también le permite reemplazar hash_map con una matriz o vector simple.

Si no has hasheado un conjunto fijo de palabras, obviamente esto no se aplica.

Answer 9

Si sus cadenas son, en promedio, más largas que una única línea de caché, pero su longitud + prefijo son razonablemente únicas, considere tener solo la longitud + los primeros 8/16 caracteres. (La longitud está contenida en el objeto std :: string en sí mismo y, por lo tanto, es económico de leer)

Answer 10

Trabajé con Paul Larson de Microsoft Research en algunas implementaciones de hashtable. Investigó una serie de funciones de hash de cadenas en una variedad de conjuntos de datos y descubrió que un simple multiplicar por 101 y agregar bucle funcionaba sorprendentemente bien.

unsigned int
hash(
    const char* s,
    unsigned int seed = 0)
{
    unsigned int hash = seed;
    while (*s)
    {
        hash = hash * 101  +  *s++;
    }
    return hash;
}

Answer 11

Una sugerencia clásica para un hash de cadena es recorrer las letras una por una agregando sus valores ascii / unicode a un acumulador, cada vez multiplicando el acumulador por un número primo. (permitiendo desbordamiento en el valor hash)

  template <> struct myhash{};

  template <> struct myhash<string>
    {
    size_t operator()(string &to_hash) const
      {
      const char * in = to_hash.c_str();
      size_t out=0;
      while(NULL != *in)
        {
        out*= 53; //just a prime number
        out+= *in;
        ++in;
        }
      return out;
      }
    };

  hash_map<string, int, myhash<string> > my_hash_map;

Es difícil llegar más rápido que eso sin tirar datos. Si sabe que sus cadenas se pueden diferenciar solo por unos pocos caracteres y no por todo su contenido, puede hacerlo más rápido.

Puede tratar de almacenar en caché el valor hash mejor mediante la creación de una nueva subclase de basic_string que recuerda su valor hash, si el valor se calcula con demasiada frecuencia. hash_map debería estar haciendo eso internamente, sin embargo.