¿Tiene una buena función hash para una tabla hash C++?

Question

Necesito una implementación de función hash orientada al rendimiento en C++ para una tabla hash que voy a codificar. Miré a mi alrededor y solo encontré preguntas preguntando qué es una buena función hash "en general". He considerado CRC32 (¿pero dónde encontrar una buena implementación?) Y algunos algoritmos de criptografía. Mi mesa, sin embargo, tiene requisitos muy específicos.

Esto es lo que la mesa será como:

100,000 items max 
200,000 capacity (so the load is 0.5) 
hashing a 6-character string which is a part of English sentence 
    examples: "become" "and he" ", not " 

La prioridad número uno de mi tabla hash es búsqueda rápida (de recuperación). La inserción rápida no es importante, pero vendrá junto con la búsqueda rápida. La eliminación no es importante, y volver a mezclar no es algo que investigue. Para manejar colisiones, probablemente usaré encadenamiento separado como se describe here. Ya he consultado this article, pero me gustaría obtener una opinión de aquellos que ya han manejado esa tarea anteriormente.

Answer 1

Ahora assumming desea un hash, y quieren algo rápida ardiente que funcionaría en su caso, debido a que sus cadenas son sólo 6 caracteres de largo que podría utilizar esta magia:

size_t precision = 2; //change the precision with this 
size_t hash(const char* str) 
{ 
    return (*(size_t*)str)>> precision; 
} 

CRC es para slowpokes ;)

Explicación: Esto funciona mediante la fundición del contenido del puntero de cadena de "ven como" un size_t (int32 o Int64 basado en el partido óptimo para su hardware). Entonces, el contenido de la cadena se interpreta como un número sin formato, ya no se preocupan por los caracteres, y luego se cambia la precisión necesaria (se ajusta este número al mejor rendimiento, he encontrado que 2 funcionan bien para las cadenas hash en conjunto de algunos miles).

también la parte realmente interesante es cualquier compilador decente en el hardware moderno se hash de una cadena como esta en 1 instrucciones de montaje, difícil de superar que;)

Answer 2

Boost.Functional/Hash puede ser de utilidad para usted. No lo he probado, así que no puedo responder por su desempeño.

Boost también tiene un CRC library.

Miraría primero un Boost.Unordered (es decir, boost :: unordered_map <>). Utiliza mapas hash en lugar de árboles binarios para contenedores.

Creo que algunas implementaciones de STL tienen un contenedor hash_map <> en el espacio de nombres stdext.

Answer 3

Si necesita buscar cadenas cortas y la inserción no es un problema, tal vez podría utilizar un B-tree o un árbol de 2-3, no gana mucho haciendo hash en su caso.

La forma en que harías esto es colocando una letra en cada nodo, por lo que primero verificas el nodo "a", luego seleccionas los hijos "a" para "p", y los secundarios para "p" , y luego "l" y luego "e". En situaciones en las que tiene "apple" y "apply", debe buscar el último nodo, (ya que la única diferencia está en la última "e" e "y")

Pero, en la mayoría de los casos, ser capaz de obtener la palabra después de unos pocos pasos ("xilófono" => "x" -> "ylophone"), para que pueda optimizar de esta manera. Esto puede ser más rápido que hash

Answer 4

El tamaño de su tabla determinará qué hash de tamaño debe usar. Le gustaría minimizar las colisiones, por supuesto. No estoy seguro de lo que está especificando por elementos máximos y capacidad (me parecen lo mismo) En cualquier caso, cualquiera de esos números sugiere que un hash de 32 bits sería suficiente. Puede salirse con la CRC16 (~ 65,000 posibilidades) pero probablemente tenga que lidiar con muchas colisiones. Por otro lado, una colisión puede ser más rápida de manejar que un hash CRC32.

Yo diría, vaya con CRC32. No encontrará escasez de documentación ni código de muestra. Dado que tiene sus máximos calculados y la velocidad es una prioridad, vaya con una serie de punteros. Usa el hash para generar un índice. En colisión, incremente el índice hasta que golpee un cubo vacío ... rápido y simple.

Answer 5

La prioridad número uno de mi tabla hash es la búsqueda rápida (recuperación).

Bueno, entonces está utilizando la estructura de datos correcta, ya que la búsqueda en una tabla hash es O (1)!:)

El CRC32 debería estar bien. La implementación no es tan compleja, se basa principalmente en XOR. Solo asegúrate de usar un buen polinomio.

Answer 6

¿Qué tal algo simple:

// Initialize hash lookup so that it maps the characters 
// in your string to integers between 0 and 31 
int hashLookup[256]; 

// Hash function for six character strings. 
int hash(const char *str) 
{ 
    int ret = 0, mult = 1; 
    for (const char *p = str; *p; *p++, mult *= 32) { 
     assert(*p >= 0 && *p < 256); 
     ret += mult * hashLookup[*p]; 
    } 

    return ret; 
} 

Esto supone 32 bits enteros. Utiliza 5 bits por carácter, por lo que el valor hash solo tiene 30 bits. Puede arreglar esto, quizás, generando seis bits para el primer uno o dos caracteres. Si su conjunto de caracteres es lo suficientemente pequeño, es posible que no necesite más de 30 bits.

Answer 7

Desde que almacena palabras en inglés, la mayor parte de sus caracteres serán letras y no habrá mucha variación en los dos bits más significativos de sus datos. Además de eso, lo mantendría muy simple, simplemente usando XOR. Después de todo, no estás buscando la fuerza criptográfica, sino solo para una distribución razonablemente pareja. Algo a lo largo de estas líneas:

size_t hash(const std::string &data) { 
    size_t h(0); 
    for (int i=0; i<data.length(); i++) 
    h = (h << 6)^(h >> 26)^data[i]; 
    } 
    return h; 
} 

Además de eso, ¿ha mirado std :: TR1 :: almohadilla, como una función hash y/o std :: TR1 :: unordered_map como una implementación de una tabla hash? Usar estos probablemente sería ahorrar mucho trabajo opuesto a la implementación de sus propias clases.

Answer 8

Este polinomio simple funciona sorprendentemente bien. Lo obtuve de Paul Larson, de Microsoft Research, quien estudió una amplia variedad de funciones hash y multiplicadores hash.

unsigned hash(const char* s, unsigned salt) 
{ 
    unsigned h = salt; 
    while (*s) 
     h = h * 101 + (unsigned) *s++; 
    return h; 
} 

salt debe ser inicializado a algunos al azar valor elegido antes de la creación de la tabla hash para defenderse de hash table attacks. Si esto no es un problema para usted, simplemente use 0.

El tamaño de la mesa también es importante para minimizar las colisiones. Parece que el tuyo está bien.

Answer 9

Desde C++ 11, C++ ha proporcionado un std::hash<string>(string). Es probable que sea una función de hashing eficiente que proporciona un good distribution of hash-codes para la mayoría de las cadenas.

Además, si está pensando en implementar una tabla hash, ahora debería considerar el uso de C++ std::unordered_map.