mapas - set string c++

Función hash para una cadena.

Question

Actualmente estamos tratando con la función hash en mi clase. Nuestro instructor nos solicitó una función hash en Internet para compararla con las dos que hemos utilizado en nuestro código.

El primero:

int HashTable::hash (string word)   
// POST: the index of entry is returned
{       int sum = 0;
        for (int k = 0; k < word.length(); k++)
            sum = sum + int(word[k]);
        return  sum % SIZE; 
}

Segundo:

int HashTable::hash (string word)
{
   int seed = 131; 
   unsigned long hash = 0;
   for(int i = 0; i < word.length(); i++)
   {
      hash = (hash * seed) + word[i];
   }
   return hash % SIZE;
}

Donde SIZE es 501 (el tamaño de la tabla hash) y la entrada proviene de un archivo de texto de más de 20,000 palabras.

Vi this pregunta con algunos ejemplos de código, pero no estaba exactamente segura de qué buscar en una función hash. Si entiendo correctamente, en mi caso, un hash toma una entrada (cadena) y hace un cálculo matemático para asignar un número a la cadena y lo inserta en una tabla. Este proceso se realiza para aumentar la velocidad de búsqueda de la lista?

Si mi lógica es sólida, ¿alguien tiene un buen ejemplo o un recurso que muestre una función hash diferente que involucre una cadena? O incluso el proceso de escribir mi propia función hash eficiente.

Answer 1

La String de Java implementa código hash de esta manera :

public int hashCode()

Returns a hash code for this string. The hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.) 

Así que algo como esto:

int HashTable::hash (string word) {
    int result = 0;
    for(size_t i = 0; i < word.length(); ++i) {
        result += word[i] * pow(31, i);
    }
    return result;
}

Answer 2

Las funciones de hash para uso algorítmico tienen generalmente 2 objetivos, primero deben ser rápidos, y luego deben distribuir los valores de manera equitativa entre los números posibles. La función hash también se requiere para proporcionar el mismo número para el mismo valor de entrada.

Si sus valores son cadenas, aquí hay algunos ejemplos de funciones de hash incorrectas:

1. string[0] - los caracteres ASCII aZ son mucho más frecuentes que otros
2. string.lengh() - el valor más probable es 1

Las buenas funciones de hash intentan usar cada bit de la entrada mientras mantienen el tiempo de cálculo mínimo. Si solo necesita un código hash, intente multiplicar los bytes con números primos y sumarlos.

Answer 3

Primero, generalmente no importa mucho en la práctica. La mayoría de las funciones de hash son "suficientemente buenas".

Pero si realmente te importa, debes saber que es un tema de investigación por sí mismo. Hay miles de papeles sobre eso. Aún puede obtener un doctorado hoy estudiando y diseñando algoritmos de hash.

Tu segunda función hash podría ser un poco mejor, porque probablemente debería separar la cadena "ab" de la cadena "ba" . Por otro lado, es probablemente menos rápido que la primera función hash. Puede, o no, ser relevante para su aplicación.

Supongo que las funciones de hash utilizadas para las cadenas del genoma son bastante diferentes de las utilizadas para los nombres de familia de hash en las bases de datos telefónicas. Tal vez incluso algunas funciones de hash de cadena son más adecuadas para el alemán que para las palabras en inglés o francés.

Muchas bibliotecas de software ofrecen funciones hash suficientemente buenas, por ejemplo, Qt tiene qhash , y C ++ 11 tiene std::hash en <functional> , Glib tiene varias funciones hash en C, y POCO tiene alguna función hash .

A menudo tengo funciones de hash que involucran números primos (ver la identidad de Bézout ) y xor, como por ejemplo

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */
unsigned hash_str(const char* s)
{
   unsigned h = FIRSTH;
   while (*s) {
     h = (h * A) ^ (s[0] * B);
     s++;
   }
   return h; // or return h % C;
}

Pero no pretendo ser un experto en hash. Por supuesto, los valores de A , B , C , FIRSTH deberían ser primos, pero podría haber elegido otros números primos.

Mire la implementación de MD5 para tener una idea de lo que pueden ser las funciones hash.

La mayoría de los buenos libros sobre algoritmos tienen al menos un capítulo entero dedicado al hash. Comience con wikipages en función hash y tabla hash .

Answer 4

Use boost::hash

#include <boost/functional/hash.hpp>

...

std::string a = "ABCDE";
size_t b = boost::hash_value(a);

Answer 5

- El camino a seguir en estos días.

Utilice SipHash . Para su propia protección.

- Viejo y peligroso -

unsigned int RSHash(const std::string& str)
{
    unsigned int b    = 378551;
    unsigned int a    = 63689;
    unsigned int hash = 0;

    for(std::size_t i = 0; i < str.length(); i++)
    {
        hash = hash * a + str[i];
        a    = a * b;
    }

    return (hash & 0x7FFFFFFF);
 }

 unsigned int JSHash(const std::string& str)
 {
      unsigned int hash = 1315423911;

      for(std::size_t i = 0; i < str.length(); i++)
      {
          hash ^= ((hash << 5) + str[i] + (hash >> 2));
      }

      return (hash & 0x7FFFFFFF);
 }

Pregunte a google por "función hash de propósito general"