una - tablas hash c++

¿Tiene una buena función hash para una tabla hash de 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.

Así es como será la mesa:

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 la búsqueda rápida (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é un encadenamiento separado como se describe here . Ya he consultado este artículo , pero quisiera una opinión de aquellos que ya han manejado esa tarea anteriormente.

Answer 1

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

¡Bien, entonces está utilizando la estructura de datos correcta, ya que buscar 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 2

¿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 de entrada. 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 3

Ahora suponiendo que quieres un hash, y quieres algo increíblemente rápido que funcione en tu caso, porque tus cadenas tienen solo 6 caracteres de largo podrías usar 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 lentos;)

Explicación: Esto funciona al convertir el contenido del puntero de cadena para "parecerse" a un size_t (int32 o int64 basado en la coincidencia óptima 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 buena es que cualquier compilador decente en hardware moderno compilará una cadena como esta en 1 instrucción de ensamblaje, difícil de superar;)

Answer 4

Como almacenas palabras en inglés, la mayoría de tus personajes serán letras y no habrá mucha variación en los dos bits más significativos de tus 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 en esta línea:

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, ¿has mirado std :: tr1 :: hash 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 5

Desde C ++ 11, C ++ ha proporcionado un std::hash< string >( string ) . Es probable que sea una función de hashing eficiente que proporcione una buena distribución de códigos hash 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 lugar.

Answer 6

El tamaño de su tabla dictará 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, ve 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 7

Este simple polinomio 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 inicializarse a algún valor elegido al azar antes de que se cree la tabla hash para defenderse de los ataques a la tabla hash . Si esto no es un problema para ti, simplemente usa 0.

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

Answer 8

Si necesita buscar cadenas cortas y la inserción no es un problema, tal vez podría usar 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 "a" para la "p", y los hijos para "p", y luego " l "y luego" e ". En situaciones en las que tenga "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, podrás obtener la palabra después de unos pocos pasos ("xilófono" => "x" -> "yófono"), para que puedas optimizar de esta manera. Esto puede ser más rápido que hashing

Answer 9

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

Boost también tiene una biblioteca CRC .

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

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