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

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étrique, donc l'ordre des éléments est perdu. Donc {[2] } va combiner le même hachage que "dab".

Xor mappe des valeurs identiques à zéro, et vous devriez éviter de mapper des valeurs "communes" à zéro:

Donc (a,a) est mappé à 0, et (b,b) est également mappé à 0. Que ces paires sont plus fréquentes que le hasard pourrait impliquer, vous vous retrouvez avec beaucoup de beaucoup de collisions à zéro que vous devriez.

Avec ces deux problèmes, xor finit par être un combineur de hachage qui semble à moitié décent sur la 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 utilise probablement plus de puissance pour le retirer, certes). La table de vérité d'Adding est similaire à xor sur le bit en question, mais elle envoie également un bit au bit suivant lorsque les deux valeurs sont 1. Cela efface moins d'informations.

Donc {[6] } est meilleur en ce que si a==b, le résultat est à la place hash(a)<<1 au lieu de 0.

Cela reste symétrique. Nous pouvons briser cette symétrie pour un coût modeste:

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

Alias hash(a)*3 + hash(b). (calculer hash(a) une fois et stocker est conseillé si vous utilisez la solution shift). Toute constante impaire au lieu de 3 mappera bijectivement une size_t (ou une constante non signée k-bit) à elle-même, car la carte sur les constantes non signées est math modulo 2^k pour certains k, et toute constante impaire est relativement première à 2^k.

Pour une version encore plus fantaisiste, 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 additionnons quelques versions décalées de seed avec une constante (qui est fondamentalement aléatoire 0 s et 1s-en particulier c'est l'inverse du nombre d'or en tant que fraction de point fixe 32 bits) avec un ajout et un xor. Cela rompt la symétrie et introduit du "bruit" si les valeurs hachées entrantes sont mauvaises (c'est-à-dire, imaginez que chaque composant Hache à 0 - ce qui précède il gère bien, générant un frottis de 1 et 0s après chaque combinaison. Le mien produit simplement un 0).

Pour ceux qui ne sont pas familiers avec C / C++, Un size_t est une valeur entière non signée qui est assez grande pour décrire la taille de n'importe quel objet 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, 32 bits entier non signé.

Malgré ses propriétés de mélange de bits pratiques, 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 de m * H(A) + H(B), où m est un grand nombre impair.

Crédit: le combineur ci-dessus était une astuce de Bob Jenkins.

Xor peut être le moyen "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 nul. Dans la vraie vie, il y a des hachages identiques sont plus fréquents que l'on aurait pu s'y attendre. Vous pourriez alors constater que dans ces cas de Coin (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 être la combinaison des mots de passe hachés des 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 sont nuls!

Il y a quelque chose que je veux souligner explicitement pour les autres qui trouvent cette page. Et et ou restreindre 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 je vais utiliser pour expliquer ceci: Min () et Max ().

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

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

Si l'on vous donne: C = A AND B

Alors vous pouvez trouver que C <= Min(A, B) nous le savons parce qu'il n'y a rien que vous pouvez et avec les 0 bits De A ou B pour les rendre 1s. donc 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 ne peut pas être ored en étant un zéro, donc il reste 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 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 pas de restriction 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 tout 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 biaisé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 OR  11111111 = 11111111

Comme le mentionne @Greg Hewgill, 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, eh bien, il n'y a pas besoin: XOR fonctionne parfaitement, et c'est incroyablement stupide-rapide.

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

Grosso modo, la plupart des implémentations multi-attributs hashCode() 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-réponses 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 il est très bonnes caractéristiques de performances générales.

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.

Faites maintenant 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 à ce sujet entrées.