Función hash para una cadena

Question

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

La primera de ellas:

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 el tamaño es 501 (el tamaño de la tabla hash) y la entrada proviene de un archivo de texto de 20.000 palabras.

Vi this pregunta con algunos ejemplos de código pero no estaba exactamente seguro 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 asignarle un número a la cadena y lo inserta en una tabla. Este proceso se realiza para aumentar la velocidad de búsqueda en la lista?

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

Answer 1

En primer lugar, por lo general no importa mucho en la práctica. La mayoría de las funciones hash son "lo suficientemente buenas".

Pero si realmente te importa, debes saber que es un tema de investigación en sí mismo. Hay miles de artículos sobre eso. Todavía puede obtener un doctorado hoy estudiando & diseñando algoritmos hash.

Su segunda función hash podría ser ligeramente 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 hash utilizadas para las cadenas de genoma son bastante diferentes a las utilizadas para el hash de los nombres de familia en las bases de datos telefónicas. Tal vez incluso algunas funciones 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 le ofrecen funciones hash suficientemente buenas, p. Qt tiene qhash, y C++ 11 tiene std::hash en <functional>, Glib tiene varios hash functions en C, y POCO tiene alguna función de hash.

A menudo tengo funciones hashing que involucran primos (consulte Bézout's identity) y xor, como p.

#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 deben ser preferiblemente 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 de hash.

La mayoría de los buenos libros sobre algoritmos tienen al menos un capítulo completo dedicado a hash. Comience con wikipages en hash function & hash table.

Answer 2

de String implements hashCode like this Java:

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 3

- El camino a seguir en estos días -

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

solicitar a Google "función de control de propósito general"

Answer 4

funciones hash para el uso de algoritmos tienen generalmente 2 goles, primero tienen que ser rápido, en segundo lugar, deben distribuir equitativamente los valores entre los números posibles. La función hash también requiere dar el mismo número para el mismo valor de entrada.

si sus valores son cadenas, he aquí algunos ejemplos de funciones hash malas:

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

Buenas funciones hash intenta utilizar cada bit de la entrada mientras se mantiene el tiempo de cálculo mínimo. Si solo necesita un código hash, intente multiplicar los bytes con números primos y sumézcalos.

Answer 5

Uso boost::hash

#include <boost\functional\hash.hpp> 

...

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