Pourquoi XOR est-il souvent utilisé dans java hashCode() mais d'autres opérateurs bit-bit 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 de bits, XOR a les meilleures propriétés de réarrangement de 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 voir pour ET et OU faire un mauvais travail à des bits de mélange. OU produira en moyenne 3/4 bits d'une valeur de 1 à 4 bits. ET d'autre part produira en moyenne 3/4 bits-zéro. Seul XOR a une distribution égale à un bit ou nulle. Cela le rend si précieux pour la génération de code de hachage. N'oubliez pas que pour un code de hachage, vous voulez utiliser le plus d'informations 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 de nombres avec beaucoup de uns.

Answer 2

XOR opertpr sont réversibles, à savoir suppose que j'ai une chaîne de bits comme 0 0 1 et je XOR avec une autre chaîne de bits 1 1 1, la sortie est

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

maintenant je peux Agan XOR la ​​1ère chaîne avec le résultat pour obtenir la 2ème chaîne. c'est-à-dire

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

donc, cela fait de la 2ème chaîne une clé. Ce comportement ne se trouve pas avec un autre opérateur bit

S'il vous plaît voir ceci pour plus d'informations ->Why is XOR used on Cryptography?

Answer 3

XOR présente les avantages suivants:

• Il ne dépend pas de l'ordre de calcul soit un^b = b^a
• Il ne "gaspille" pas de bits. Si vous changez même un bit dans l'un des composants, la valeur finale changera.
• C'est rapide, un seul cycle sur même l'ordinateur le plus primitif.
• Il préserve la distribution uniforme. Si les deux pièces que vous combinez sont uniformément réparties, la combinaison le sera. En d'autres termes, il n'a pas tendance à réduire la portée du condensé dans une bande plus étroite.

Plus d'infos here.

Answer 4

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

Exemples: (code complet here)

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 
} 

utilisation:

 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}