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

Disons que vous avez deux hachages H(A)et H(B)que vous souhaitez les combiner. J'ai lu qu'une bonne façon de combiner deux hachages est de XORles utiliser , 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 :

Le XOR de deux nombres avec une distribution approximativement aléatoire donne un autre nombre toujours avec une distribution 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 un 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 derrière pourquoi XOR devrait être l'opération par défaut pour combiner des fonctions de hachage (plutôt que OR ou AND etc.)?

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

La fonction XOR est de 50% 0et 50% 1, elle est donc bonne pour combiner des distributions de probabilité 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 aet bont cette distribution de sortie uniforme? Pourquoi XOR est-il le plus adapté à l'objectif indiqué dans votre question?

xorest une fonction par défaut dangereuse à utiliser lors du hachage. C'est mieux que andet or, mais cela ne dit pas grand-chose.

xorest symétrique, donc l'ordre des éléments est perdu. Ainsi, "bad"le hachage se combinera de la même manière que "dab".

xor mappe des valeurs identiques par paires à zéro, et vous devez éviter de mapper des valeurs "communes" à zéro:

Donc, (a,a)est mappé à 0, et est (b,b)également mappé à 0. Comme ces paires sont presque toujours plus courantes que le hasard pourrait l'impliquer, vous vous retrouvez avec beaucoup de collisions à zéro que vous ne le devriez.

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

Sur le matériel moderne, l'ajout est généralement aussi rapide que xor(il utilise probablement plus d'énergie pour y parvenir, certes). L'ajout de la table de vérité est similaire à celui xordu bit en question, mais il envoie également un bit au bit suivant lorsque les deux valeurs sont 1. Cela signifie qu'il efface moins d'informations.

C'est donc hash(a) + hash(b)mieux hash(a) xor hash(b)que si a==b, le résultat est hash(a)<<1au lieu de 0.

Cela reste symétrique; donc le "bad"et "dab"obtenir le même résultat reste un problème. On peut casser cette symétrie pour un coût modique:

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

aka hash(a)*3 + hash(b). ( hash(a)il est conseillé de calculer une fois et de stocker si vous utilisez la solution de décalage). Toute constante impaire au lieu de 3mappera bijectivement un kentier non signé « -bit» à elle-même, car la mappe sur des entiers non signés est mathématique modulo 2^kpour certains k, et toute constante impaire est relativement première 2^k.

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

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

ici nous additionnons quelques versions décalées de seedavec une constante (qui est fondamentalement aléatoire 0s et 1s - en particulier c'est l'inverse du nombre d'or comme une fraction de virgule fixe de 32 bits) avec un ajout et un xor. Cette symétrie pauses et présente quelques « bruit » si les valeurs sont pauvres entrants hachés (c. -à imaginer tous les composants hash à 0 - les poignées au- dessus bien, générer un frottis de 1et 0. S après chaque moissonneuse - batteuse Mon naïve 3*hash(a)+hash(b)sorties simplement 0en ce cas).

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

Malgré ses propriétés pratiques de mélange de bits, XOR n'est pas un bon moyen de combiner les hachages en raison de 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 bien meilleur choix est m * H(A) + H(B), où m est un grand nombre impair.

Crédit: Le combinateur ci-dessus était un conseil de Bob Jenkins.

Xor est peut-être la manière "par défaut" de combiner les hachages, mais la réponse de Greg Hewgill montre également pourquoi il a ses 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 courants qu'on aurait pu s'y attendre. Vous pourriez alors constater que dans ces cas d'angle (pas si rares), 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 pourriez combiner des mots de passe hachés d'utilisateurs 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 est nulle!

Il y a quelque chose que je veux souligner explicitement pour les autres qui trouvent cette page. AND et OR restreignent la sortie comme BlueRaja - Danny Pflughoe essaie de le 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 qui est plus petite entre A et B, par exemple: Min (1, 5) renvoie 1.

Max (A, B) renverra la valeur qui est plus grande entre A et B, par exemple: Max (1, 5) renvoie 5.

Si vous recevez: C = A AND B

Alors tu peux trouver ça C <= Min(A, B) Nous le savons car il n'y a rien que vous puissiez ET avec les 0 bits de A ou B pour les rendre 1. Ainsi, chaque bit zéro reste un bit zéro et chaque bit a une chance de devenir un bit zéro (et donc une valeur plus petite).

Avec: C = A OR B

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

Cela implique que l'état de l'entrée applique des restrictions sur la sortie. Si vous ET 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 aucune restriction implicite basée sur les entrées. Il existe des cas particuliers où vous pouvez constater que si vous effectuez un XOR sur un octet avec 255, vous obtenez l'inverse, mais n'importe quel octet possible peut en être sorti. Chaque bit a une chance de changer d'état en fonction du même bit dans l'autre opérande.

Si vous avez XORune entrée aléatoire avec une entrée biaisée, la sortie est aléatoire. La même chose n'est pas vraie pour ANDou OR. Exemple:

00101001 XOR 00000000 = 00101001
00101001 ET 00000000 = 00000000
00101001 OU 11111111 = 11111111

Comme le mentionne @Greg Hewgill, même si les deux entrées sont aléatoires, l'utilisation de ANDou ORentraînera une sortie biaisée.

La raison pour laquelle nous utilisons XORquelque chose de plus complexe est que, eh bien, il n'y a pas besoin: XORfonctionne parfaitement, et c'est incroyablement stupide-rapide.

Couvrez les 2 colonnes de gauche et essayez de déterminer ce que les 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 auriez dû comprendre que les deux entrées étaient 1.

Maintenant, faites de même pour XOR

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

XOR ne donne rien sur ses entrées.

Le code source des différentes versions de hashCode()in 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 hashCode()implémentations multi-attributs 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 StackOverflow pour plus d'informations sur la magie derrière 31et pourquoi le code Java l'utilise si fréquemment. Il est imparfait, mais présente de très bonnes caractéristiques de performances générales.

XOR n'ignore pas certaines des entrées comme OR et AND .

Si vous prenez AND (X, Y) par exemple, et alimentez l'entrée X avec false, alors l'entrée Y n'a pas d'importance ... et on voudrait probablement que l'entrée ait de l'importance lors de la combinaison de hachages.

Si vous prenez XOR (X, Y) puis DEUX entrées TOUJOURS question. Il n'y aurait aucune valeur de X où Y n'a pas d'importance. Si X ou Y est modifié, la sortie reflétera cela.