Mise en œuvre du code de hachage du tableau Java

Question

C'est curieux. Un collègue m'a interrogé sur l'implémentation de myArray.hashCode() en Java. Je pensais le savoir, mais j'ai fait quelques tests. Regardez le code ci-dessous. La chose étrange que j'ai remarquée est que lorsque j'ai écrit le premier sys out, les résultats étaient différents. Notez que c'est presque comme s'il rapportait une adresse mémoire et que la modification de la classe déplaçait l'adresse ou quelque chose comme ça. J'ai juste pensé à partager cette information.

int[] foo = new int[100000];
java.util.Random rand = new java.util.Random();

for(int a = 0; a < foo.length; a++) foo[a] = rand.nextInt();

int[] bar = new int[100000];
int[] baz = new int[100000];
int[] bax = new int[100000];
for(int a = 0; a < foo.length; a++) bar[a] = baz[a] = bax[a] = foo[a];

System.out.println(foo.hashCode() + " ----- " + bar.hashCode() + " ----- " + baz.hashCode() +  " ----- " + bax.hashCode());

// returns 4097744 ----- 328041 ----- 2083945 ----- 2438296
// Consistently unless you modify the class.  Very weird
// Before adding the comments below it returned this:
// 4177328 ----- 4097744 ----- 328041 ----- 2083945

System.out.println("Equal ?? " +
  (java.util.Arrays.equals(foo, bar) && java.util.Arrays.equals(bar, baz) &&
  java.util.Arrays.equals(baz, bax) && java.util.Arrays.equals(foo, bax)));

Answer 1

En java.lang.Array hashCode est héritée de la méthode Object ce qui signifie que le code de hachage dépend de la référence. Pour obtenir le code de hachage en fonction du contenu du tableau, utilisez Arrays.hashCode .

Attention cependant, il s'agit d'une implémentation peu profonde du hashcode. Une implémentation profonde est également présente Arrays.deepHashCode .

Answer 2

Les tableaux utilisent le code de hachage par défaut, qui est basé sur l'emplacement de la mémoire (mais ce n'est pas nécessairement le cas). les puisqu'il s'agit seulement d'un emplacement de mémoire int et toutes les adresses de mémoire ne tiendront pas). Vous pouvez le constater en imprimant également le résultat de System.identityHashCode(foo) .

Les tableaux sont uniquement equal s'il s'agit du même tableau. Ainsi, les codes de hachage d'un tableau ne seront généralement égaux que s'il s'agit d'un tableau identique.

Answer 3

L'implémentation par défaut de Object.hashCode() est en effet de retourner la valeur du pointeur de l'objet, bien que cela dépende de l'implémentation. Par exemple, une JVM 64 bits peut prendre le pointeur et faire un XOR entre les mots d'ordre haut et bas. Les sous-classes sont encouragées à surcharger ce comportement s'il est judicieux.

Cependant, il n'est pas logique d'effectuer des comparaisons d'égalité sur des tableaux mutables. Si un élément change, les deux tableaux ne sont plus égaux. Pour maintenir l'invariant selon lequel un même tableau renverra toujours le même code de hachage, quoi qu'il arrive à ses éléments, les tableaux ne remplacent pas le comportement par défaut du code de hachage.

Notez que java.util.Arrays fournit une implémentation de deepHashCode() pour les cas où le hachage basé sur le contenu du tableau, plutôt que sur l'identité du tableau lui-même, est important.

Answer 4

Je suis d'accord pour utiliser java.util.Arrays.hashCode (ou le wrapper générique de google guava Objects.hashcode) mais sachez que cela peut poser des problèmes si vous utilisez Terracotta - voir ce lien