¿Por qué XOR es la forma predeterminada de combinar hashes?

Xor es una función predeterminada peligrosa para usar cuando se hace hash. Es mejor que y y o, pero eso no dice mucho.

Xor es simétrico, por lo que el orden de los elementos se pierde. Así que "bad" combinará el hash igual que "dab".

Xor asigna valores idénticos a cero, y debe evitar asignar valores "comunes" a cero:

Así que (a,a) se asigna a 0, y (b,b) también se asigna a 0. Como tales pares son más comunes que la aleatoriedad podría implicar, usted termina con lejos a muchas colisiones a cero de las que deberías.

Con estos dos problemas, xor termina siendo un combinador de hash que se ve medio decente en la superficie, pero no después de una inspección adicional.

En hardware moderno, añadiendo normalmente tan rápido como xor (probablemente usa más potencia para lograr esto, es cierto). La tabla de verdad de adición es similar a xor en el bit en cuestión, pero también envía un bit al siguiente bit cuando ambos valores son 1. Esto borra menos información.

So hash(a) + hash(b) es mejor en que si a==b, el resultado es en cambio hash(a)<<1 en lugar de 0.

Esto permanece simétrico. Podemos romper esta simetría por un costo modesto:

hash(a)<<1 + hash(a) + hash(b)

Aka hash(a)*3 + hash(b). (se recomienda calcular hash(a) una vez y almacenar si utiliza la solución shift). Cualquier constante impar en lugar de 3 se mapeará bijectivamente una size_t (o constante sin signo de k-bit) a sí misma, ya que map on unsigned constants is math modulo 2^k for some k, y cualquier constante impar es 2^k.

Para una versión aún más elegante, podemos examinar boost::hash_combine, que es efectivamente:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

Aquí sumamos algunas versiones cambiadas de seed con una constante (que es básicamente aleatoria 0 s y 1 s particular en particular, es la inversa de la proporción áurea como una fracción de punto fijo de 32 bits) con alguna adición y un xor. Esto rompe la simetría, e introduce algo de "ruido" si los valores hash entrantes son pobres ( es decir, imagine cada componente hashes a 0 the lo anterior lo maneja bien, generando una mancha de 1 y 0 s después de cada combinación. Mine simplemente produce un 0).

Para aquellos que no están familiarizados con C/C++, un size_t es un valor entero sin signo que es lo suficientemente grande como para describir el tamaño de cualquier objeto en memoria. En un sistema de 64 bits, generalmente es un entero sin signo de 64 bits. En un sistema de 32 bits, un entero sin signo de 32 bits.

A pesar de sus prácticas propiedades de mezcla de bits, XOR es no una buena manera de combinar hashes debido a su conmutatividad. Considerar qué sucedería si se almacenan las permutaciones de {1, 2, ..., 10} en una tabla hash de 10-tuplas.

Una opción mucho mejor es m * H(A) + H(B), donde m es un número impar grande.

Crédito: El combinador anterior fue un consejo de Bob Jenkins.

Xor puede ser la forma "predeterminada" de combinar hashes, pero la respuesta de Greg Hewgill también muestra por qué tiene sus trampas: El xor de dos valores hash idénticos es cero. En la vida real, hay hashes idénticos son más comunes de lo que uno podría haber esperado. Entonces puede encontrar que en estos casos de esquina (no tan infrecuentes), los hashes combinados resultantes son siempre los mismos (cero). Las colisiones de Hash serían mucho, mucho más frecuentes de lo que esperas.

En un ejemplo artificial, usted podría ser combinar contraseñas hash de usuarios de diferentes sitios web que administras. Desafortunadamente, un gran número de usuarios reutilizan sus contraseñas, ¡y una sorprendente proporción de los hashes resultantes son cero!

Hay algo que quiero señalar explícitamente para otros que encuentren esta página. Y y O restringir la salida como BlueRaja-Danny Pflughoe está tratando de señalar, pero se puede definir mejor:

Primero quiero definir dos funciones simples que usaré para explicar esto: Min() y Max().

Min(A, B) devolverá el valor que es menor entre A y B, por ejemplo: Min(1, 5) devuelve 1.

Max(A, B) devolverá el valor que es mayor entre A y B, por ejemplo: Max(1, 5) devuelve 5.

Si se le administra: C = A AND B

Entonces puedes encontrar que C <= Min(A, B) Sabemos esto porque no hay nada que puedas Y con los 0 bits de A o B para hacerlos 1s. Así que cada bit cero permanece como un bit cero y cada bit tiene una oportunidad de convertirse en un bit cero (y por lo tanto un valor más pequeño).

Con: C = A OR B

Lo contrario es cierto: C >= Max(A, B) Con esto, vemos el corolario de la función AND. Cualquier bit que ya es un uno no puede ser ored en ser un cero, por lo que sigue siendo un uno, pero cada bit cero tiene una oportunidad de convertirse en uno, y por lo tanto un número mayor.

Esto implica que el estado de la entrada aplica restricciones a la salida. Si usted Y cualquier cosa con 90, sabe que la salida será igual o inferior a 90 independientemente de cuál sea el otro valor.

Para XOR, no hay restricción implícita basada en las entradas. Hay casos especiales donde usted puede encontrar que si usted XOR un byte con 255 que usted consigue el inverso pero cualquier byte posible puede ser salida de eso. Cada bit tiene la oportunidad de cambiar de estado dependiendo del mismo bit en el otro operando.

Si XOR una entrada aleatoria con una entrada sesgada, la salida es aleatoria. Lo mismo no es cierto para AND o OR. Ejemplo:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR  11111111 = 11111111

Como menciona @Greg Hewgill, incluso si ambas entradas son aleatorias, usar AND o OR dará como resultado una salida sesgada.

La razón por la que usamos XOR sobre algo más complejo es que, bueno, no hay necesidad: XOR funciona perfectamente, y es increíblemente estúpido-rápido.

El código fuente para varias versiones de hashCode() en java.útil.Arrays es una gran referencia para algoritmos hash sólidos de uso general. Se entienden fácilmente y se traducen a otros lenguajes de programación.

En términos generales, la mayoría de las implementaciones de múltiples atributos hashCode() siguen este patrón:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

Puede buscar en otras preguntas y respuestas de StackOverflow para obtener más información sobre la magia detrás de 31 y por qué el código Java lo usa con tanta frecuencia. Es imperfecto, pero tiene muy buenas características generales de rendimiento.

Cubre las 2 columnas de la izquierda e intenta averiguar qué entradas están usando solo la salida.

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

Cuando vio un 1-bit debería haber averiguado que ambas entradas eran 1.

Ahora haga lo mismo para XOR

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

XOR no regala nada sobre sus entradas.