¿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 codificaré. Ya miré a mi alrededor y solo encontré preguntas sobre qué es una buena función hash & Quot; en general & Quot ;. He considerado CRC32 (pero ¿dónde encontrar una buena implementación?) Y algunos algoritmos de criptografía. Sin embargo, mi tabla tiene requisitos muy específicos.

Así es como será la tabla:

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 hacer hash no es algo que voy a investigar. Para manejar las colisiones, probablemente usaré encadenamiento separado como se describe aquí . Ya he visto este artículo , pero me gustaría una opinión de quienes han manejado tales tarea antes.

Answer 1

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 slowpokes;)

Explicación: Esto funciona convirtiendo el contenido del puntero de cadena a & Quot; se parece a & Quot; un size_t (int32 o int64 basado en la coincidencia óptima para su hardware). Por lo tanto, el contenido de la cadena se interpreta como un número sin procesar, ya no tiene que preocuparse por los caracteres, y luego cambia la precisión necesaria (ajusta este número para obtener el mejor rendimiento, he encontrado que 2 funciona bien para las cadenas de hash en conjunto de unos pocos miles).

Además, la parte realmente interesante es que cualquier compilador decente en hardware moderno picará una cadena como esta en 1 instrucción de ensamblaje, difícil de superar;)

Answer 2

Este polinomio simple funciona sorprendentemente bien. Lo obtuve de Paul Larson, de Microsoft Research, que 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 se debe inicializar a algún valor aleatorio elegido antes de que se cree la tabla hash para defenderse de ataques de tabla hash . Si esto no es un problema para usted, simplemente use 0.

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

Answer 3

Boost.Functional / Hash podría ser de utilízalo No lo he probado, así que no puedo garantizar su rendimiento.

Boost también tiene una biblioteca CRC .

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

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

Answer 4

El tamaño de su tabla determinará qué tamaño de hash debe usar. Por supuesto, le gustaría minimizar las colisiones. 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 suya con CRC16 (~ 65,000 posibilidades) pero probablemente tenga muchas colisiones con las que lidiar. Por otro lado, una colisión puede ser más rápida de tratar que un hash CRC32.

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

Answer 5

Dado que almacena palabras en inglés, la mayoría 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, solo usando XOR. Después de todo, no está buscando fuerza criptográfica sino solo una distribución razonablemente uniforme. Algo en este sentido:

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 visto std :: tr1 :: hash como una función de hashing y / o std :: tr1 :: unordered_map como una implementación de una tabla hash? El uso de estos probablemente ahorrará mucho trabajo en lugar de implementar sus propias clases.

Answer 6

  

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 buscar en una tabla hash es O (1). :)

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

Answer 7

¿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 entradas de 32 bits. Utiliza 5 bits por carácter, por lo que el valor hash solo tiene 30 bits. Quizás pueda solucionar esto, generando seis bits para el primero o los dos caracteres. Si su conjunto de caracteres es lo suficientemente pequeño, es posible que no necesite más de 30 bits.

Answer 8

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

La forma en que haría esto es colocando una letra en cada nodo para que primero verifique el nodo " a " ;, luego marque " a " 's children para " p " ;, y son children para " p " ;, y luego " l " y luego " e " ;. En situaciones donde tiene & Quot; apple & Quot; y " aplique " necesita buscar el último nodo, (ya que la única diferencia está en el último " e " y " y ")

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

Answer 9

Desde C ++ 11, C ++ ha proporcionado un std::hash< string >( string ) . Es probable que sea una función de hash 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 usar un C ++ std::unordered_map en su lugar.