Pourquoi XOR est-il le moyen par défaut de combiner les hachages?

Disons que vous avez deux hachages H(A) et H(B) et que vous voulez les combiner. J’ai lu qu’une bonne façon de combiner deux hachages est de les XOR , par exemple XOR( H(A), H(B) ) .

La meilleure explication que j’ai trouvée est brièvement abordée ici sur ces directives de fonction de hachage :

XORing deux nombres avec une dissortingbution approximativement aléatoire donne un autre nombre encore avec une dissortingbution approximativement aléatoire *, mais qui dépend maintenant des deux valeurs.

* A chaque bit des deux nombres à combiner, un 0 est émis si les deux bits sont égaux, sinon a 1. En d’autres termes, dans 50% des combinaisons, un 1 sera émis. Donc, si les deux bits d’entrée ont chacun une chance d’environ 50-50 d’être 0 ou 1, le bit de sortie le sera également.

Pouvez-vous expliquer l’intuition et / ou les mathématiques expliquant pourquoi XOR devrait être l’opération par défaut pour combiner des fonctions de hachage (plutôt qu’OR ou AND, etc.)?

En supposant des entrées uniformément aléatoires (1 bit), la dissortingbution de probabilité de sortie de la fonction AND est de 75% 0 et 25% 1 . Inversement, OR est 25% 0 et 75% 1 .

La fonction XOR est de 50% 0 et 50% 1 , donc bonne pour combiner des dissortingbutions de probabilités uniformes.

Cela peut être vu en écrivant des tables de vérité:

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

Exercice: Combien de fonctions logiques de deux entrées à 1 bit a et b ont cette dissortingbution de sortie uniforme? Pourquoi XOR est-il le plus adapté à l’objective indiqué dans votre question?

xor est une fonction par défaut dangereuse à utiliser lors du hachage. C’est mieux que et et ou, mais cela ne dit pas grand chose.

xor est symésortingque, donc l’ordre des éléments est perdu. Donc, "bad" sera le même que "dab" .

xor mappe des valeurs identiques à zéro et vous devez éviter de mapper les valeurs “communes” à zéro:

Donc, (a,a) est mappé sur 0, et (b,b) également mappé sur 0. Comme ces paires sont plus courantes que le hasard peut l’impliquer, vous vous retrouvez avec beaucoup de collisions à zéro.

Avec ces deux problèmes, xor finit par être un combineur de hachage qui semble à moitié décent en surface, mais pas après une inspection plus poussée.

Sur le matériel moderne, en ajoutant généralement à peu près aussi vite que xor (il faut probablement plus de puissance pour le retirer, certes). L’ajout de la table de vérité est similaire à xor sur le bit en question, mais il envoie également un bit au bit suivant lorsque les deux valeurs sont 1. Cela efface moins d’informations.

Ainsi, le hash(a) + hash(b) est meilleur en ce sens que si a==b , le résultat est à la place hash(a)<<1 au lieu de 0.

Cela rest symésortingque. Nous pouvons briser cette symésortinge pour un coût modique:

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

aka hash(a)*3 + hash(b) . (le calcul du hash(a) une fois et le stockage est conseillé si vous utilisez la solution shift). Toute constante impaire au lieu de 3 size_t bijectivement une size_t (ou k-unsigned constant) à elle-même, car la carte sur les constantes non signées est math modulo 2^k pour certaines k et toute constante impaire à 2^k .

Pour une version encore plus sophistiquée, nous pouvons examiner boost::hash_combine , qui est effectivement:

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

ici nous ajoutons quelques versions décalées de la seed avec une constante (qui est fondamentalement aléatoire 0 s et 1 s - en particulier c'est l'inverse du nombre d'or en tant que fraction de point fixe de 32 bits) avec une addition et un xor. Cela brise la symésortinge et introduit du "bruit" si les valeurs de hachage entrantes sont médiocres (par exemple, imaginez que chaque composant soit haché à 0 - ce qui est bien géré, générant un frottis de 1 et 0 s après chaque combinaison). 0 ).

Pour ceux qui ne sont pas familiers avec C / C ++, une size_t est une valeur entière non signée suffisamment grande pour décrire la taille de tout object en mémoire. Sur un système 64 bits, il s'agit généralement d'un entier non signé de 64 bits. Sur un système 32 bits, un entier non signé 32 bits.

Malgré ses propriétés pratiques de mélange de bits, XOR n’est pas un bon moyen de combiner les hachages dus à sa commutativité. Considérez ce qui se passerait si vous stockiez les permutations de {1, 2,…, 10} dans une table de hachage de 10 tuples.

Un choix bien meilleur est m * H(A) + H(B) , où m est un grand nombre impair.

Crédit: Le combiner ci-dessus était une astuce de Bob Jenkins.

Xor est peut-être le moyen “par défaut” de combiner les hachages, mais la réponse de Greg Hewgill montre également pourquoi elle présente des pièges: le xor de deux valeurs de hachage identiques est zéro. Dans la vraie vie, il y a des hachages identiques qui sont plus fréquents qu’on aurait pu s’y attendre. Vous pourriez alors trouver que dans ces cas de coin (pas si peu fréquents), les hachages combinés résultants sont toujours les mêmes (zéro). Les collisions de hachage seraient beaucoup, beaucoup plus fréquentes que prévu.

Dans un exemple artificiel, vous combinez peut-être des mots de passe hachés d’utilisateurs provenant de différents sites Web que vous gérez. Malheureusement, un grand nombre d’utilisateurs réutilisent leurs mots de passe, et une proportion surprenante des hachages résultants sont nuls!

Il y a quelque chose que je veux explicitement souligner pour ceux qui trouvent cette page. ET et OU limiter la production comme BlueRaja – Danny Pflughoe essaie de souligner, mais peut être mieux défini:

Je veux d’abord définir deux fonctions simples que j’utiliserai pour expliquer ceci: Min () et Max ().

Min (A, B) renverra la valeur plus petite entre A et B, par exemple: Min (1, 5) renvoie 1.

Max (A, B) renvoie la valeur supérieure entre A et B, par exemple: Max (1, 5) renvoie 5.

Si vous êtes donné: C = A AND B

Alors vous pouvez trouver que C <= Min(A, B) Nous le soaps car il n'y a rien que vous pouvez ET avec les 0 bits de A ou B pour les faire 1s. Donc, chaque bit zéro rest un bit zéro et chaque bit a une chance de devenir un bit zéro (et donc une valeur inférieure).

Avec: C = A OR B

Le contraire est vrai: C >= Max(A, B) Avec cela, nous voyons le corollaire de la fonction AND. Tout bit qui est déjà un ne peut pas être réglé sur zéro, donc il rest un, mais chaque bit zéro a une chance de devenir un, et donc un plus grand nombre.

Cela implique que l'état de l'entrée applique des ressortingctions sur la sortie. Si vous avez quelque chose avec 90, vous savez que la sortie sera égale ou inférieure à 90 quelle que soit l'autre valeur.

Pour XOR, il n'y a pas de ressortingction implicite basée sur les entrées. Il y a des cas spéciaux où vous pouvez trouver que si vous XOR un octet avec 255 que vous obtenez l'inverse mais n'importe quel octet possible peut être sorti de cela. Chaque bit a une chance de changer d'état en fonction du même bit dans l'autre opérande.

Si vous XOR une entrée aléatoire avec une entrée polarisée, la sortie est aléatoire. La même chose n’est pas vraie pour AND ou OR . Exemple:

 00101001 XOR 00000000 = 00101001
 00101001 AND 00000000 = 00000000
 00101001 OU 11111111 = 11111111

Comme @Greg Hewgill le mentionne, même si les deux entrées sont aléatoires, l’utilisation de AND ou OR entraînera une sortie biaisée.

La raison pour laquelle nous utilisons XOR sur quelque chose de plus complexe est que, bien, il n’y a aucun besoin: XOR fonctionne parfaitement, et il est extrêmement rapide.

Le code source des différentes versions de hashCode() dans java.util.Arrays est une excellente référence pour les algorithmes de hachage solides et à usage général. Ils sont facilement compris et traduits dans d’autres langages de programmation.

En gros, la plupart des implémentations de hashCode() multi-atsortingbuts suivent ce modèle:

 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; } 

Vous pouvez rechercher d’autres questions et réponses sur StackOverflow pour plus d’informations sur la magie derrière 31 , et pourquoi le code Java l’utilise si fréquemment. Il est imparfait, mais présente de très bonnes performances générales.

Couvrir les 2 colonnes de gauche et essayer de déterminer quelles entrées utilisent uniquement la sortie.

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

Lorsque vous avez vu un bit 1, vous devriez avoir compris que les deux entrées étaient 1.

Maintenant, faites la même chose pour XOR

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

XOR ne donne rien à son sujet.