Función Hash Intercalar

Question

En el objeto local no es una faceta de clasificado.

La faceta de intercalación tiene un método hash que vuelve mucho.
http://www.cplusplus.com/reference/std/locale/collate/ de hash /

Dos preguntas:

• ¿Alguien sabe qué método se utiliza hash.
• necesito un valor de 32 bits.
  Si mi tiempo es más largo que 32 bits, ¿alguien sabe acerca de las técnicas para plegar el hash en una versión más corta. Puedo ver que si se hace incorrectamente que el plegamiento podría generar gran cantidad de enfrentamientos (y aunque puedo hacer frente a los choques ya que necesito tener esto en cuenta de todos modos, yo preferiría si se redujeran al mínimo).

Nota: No puedo usar C ++ 0x cuenta
Boost puede estar bien.

Answer 1

No, nadie sabe realmente - que puede variar de una aplicación a otra. Los requisitos principales son (N3092, §20.8.15):

Para todos los tipos de objetos clave para las que existe un hash especialización, el hash de instancias deberá:

1. satisfacer los requisitos Hash (20.2.4), con Key como el tipo de argumento de llamada de función, los requisitos DefaultConstructible (33), los requisitos CopyAssignable (37),
2. ser intercambiables (20.2.2) para lvalues,
3. proporcionan dos tipos anidados result_type y argument_type que deberá ser sinónimos de size_t y Key, respectivamente,
4. satisface el requisito de que si k1 == k2 es cierto, h (k1) == h (k2) es también cierto, donde h es un objeto de tipo hash y k1 y k2 son los objetos de tipo Key.

y (N3092, §20.2.4):

Un tipo H cumple con los requisitos Hash si:

1. se trata de un tipo de objeto de función (20.8),
2. que satisifes los requisitos de CopyConstructible y Destructible (20.2.1),
3. las expresiones que se muestran en la siguiente tabla son válidos y tienen la semántica indicados, y
4. satisfaga los demás requisitos de esta subcláusula.

§20.8.15 cubre los requisitos sobre el resultado de hash, §20.2.4 en el propio hash. Como se puede ver, sin embargo, ambos son bastante general. La tabla que se menciona cubre básicamente tres requisitos más:

1. Una función hash debe ser "pura" (es decir, el resultado depende sólo de la entrada, no cualquier contexto, historia, etc.)
2. La función no debe modificar el argumento que se pasa a ella, y
3. No debe lanzar ninguna excepción.

algoritmos exactos son definitivamente no especifica sin embargo - ya pesar de la longitud, la mayor parte de los requisitos anteriormente son en realidad sólo se establezcan los requisitos que (al menos a mí) parece bastante obvio. En resumen, la aplicación es libre de implementar hash casi cualquier forma que quiera.

Answer 2

Si la aplicación utiliza una función hash razonable, no debe haber bits en el valor hash que tiene una correlación especial con la entrada. Así que si la función hash que da 64 bits "al azar", pero solo quiere 32 de ellos, sólo puede tomar la primera / última / ... 32 bits del valor a su gusto. Cuáles se toma no importa ya que cada bit es tan aleatorio como la siguiente (que es lo que hace una función de hash buena).

Así que la forma más simple y sin embargo totalmente razonable para obtener un valor hash de 32 bits sería:

int32_t value = hash(...);

(Por supuesto, esto se derrumba grupos de 4 mil millones de valores a una sola, que se parece mucho, pero que no se pueden evitar si hay cuatro mil millones de veces más valores de origen como valores objetivo.)