Pourquoi le XOR est souvent utilisé en java hashCode() alors que les autres opérateurs binaires sont rarement utilisés ?

Question

Je vois souvent du code comme

int hashCode(){
  return a^b;
}

Pourquoi XOR ?

Answer 1

De toutes les opérations sur les bits, XOR est celle qui présente les meilleures propriétés de brassage des bits.

Cette table de vérité explique pourquoi :

A B AND
0 0  0
0 1  0
1 0  0
1 1  1

A B OR
0 0  0
0 1  1
1 0  1
1 1  1

A B XOR
0 0  0
0 1  1
1 0  1
1 1  0

Comme vous pouvez le constater, AND et OR ne parviennent pas à mélanger les bits.

OR produira en moyenne 3/4 one-bits. AND, quant à lui, produira en moyenne 3/4 null-bits. Seul XOR a une répartition égale entre les bits de poids fort et les bits de poids faible. C'est ce qui le rend si précieux pour la génération de codes de hachage.

Rappelez-vous que pour un code de hachage, vous voulez utiliser autant d'informations que possible sur la clé et obtenir une bonne distribution des valeurs de hachage. Si vous utilisez AND ou OR, vous obtiendrez des nombres qui sont biaisés vers des nombres avec beaucoup de zéros ou des nombres avec beaucoup de uns.

Answer 2

La méthode XOR présente les avantages suivants :

• Il ne dépend pas de l'ordre de calcul, c'est-à-dire a^b = b^a.
• Il ne "gaspille" pas de bits. Si vous changez ne serait-ce qu'un seul bit dans l'un des composants, la valeur finale sera modifiée.
• C'est rapide, un seul cycle sur l'ordinateur le plus primitif.
• Il préserve une distribution uniforme. Si les deux morceaux que vous combinez sont distribués uniformément, il en sera de même pour la combinaison. En d'autres termes, elle n'a pas tendance à réduire l'étendue du condensé à une bande plus étroite.

Plus d'informations aquí .

Answer 3

L'opérateur XOR est réversible, c'est-à-dire que si j'ai une chaîne de bits comme 0 0 1 et je l'associe à une autre chaîne de bits 1 1 1 le résultat est

0 xor 1 = 1
0     1 = 1
1     1 = 0

Maintenant, je peux à nouveau xor la première chaîne avec le résultat pour obtenir la deuxième chaîne, à savoir

0   1 = 1
0   1 = 1
1   0 = 1

Donc, cela fait de la 2ème corde une clé. Ce comportement ne se retrouve pas avec les autres opérateurs de bit

Veuillez voir ceci pour plus d'informations --> Pourquoi le XOR est utilisé en cryptographie ?

Answer 4

Il existe un autre cas d'utilisation : les objets dans lequel (certains) champs doivent être comparés sans tenir compte de leur ordre . Par exemple, si vous voulez une paire (a, b) est toujours égale à la paire (b, a) .
XOR a la propriété que a ^ b = b ^ a Il peut donc être utilisé dans une fonction de hachage dans de tels cas.

Exemples : (code complet aquí )

définition :

final class Connection {
    public final int A;
    public final int B;

    // some code omitted

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Connection that = (Connection) o;

        return (A == that.A && B == that.B || A == that.B && B == that.A);
    }

    @Override
    public int hashCode() {
        return A ^ B;
    }

    // some code omitted
}

l'usage :

        HashSet<Connection> s = new HashSet<>();
        s.add(new Connection(1, 3));
        s.add(new Connection(2, 3));
        s.add(new Connection(3, 2));
        s.add(new Connection(1, 3));
        s.add(new Connection(2, 1));

        s.remove(new Connection(1, 2));

        for (Connection x : s) {
            System.out.println(x);
        }

        // output:
        // Connection{A=2, B=3}
        // Connection{A=1, B=3}