L'ordre des éléments dans une HashMap diffère lorsque le même programme est exécuté dans JVM5 par rapport à JVM6

Question

J'ai une application qui affiche une collection d'objets en lignes, un objet = une ligne. Les objets sont stockés dans une HashMap. L'ordre des lignes n'affecte pas la fonctionnalité de l'application (c'est pourquoi une HashMap a été utilisée au lieu d'une collection triable).

Cependant, j'ai remarqué que la même application se comporte différemment lorsqu'elle est exécutée avec deux versions différentes de la Machine Virtuelle Java. L'application est compilée avec JDK 5, et peut être exécutée avec les exécuteurs Java 5 ou Java 6, sans aucune différence fonctionnelle.

L'objet en question remplace java.lang.Object#hashCode() et évidemment des précautions ont été prises pour suivre le contrat spécifié dans l'API Java. Cela est prouvé par le fait qu'ils apparaissent toujours dans le même ordre à chaque exécution de l'application (dans le même environnement d'exécution Java).

Par curiosité, pourquoi le choix de l'environnement d'exécution Java affecte-t-il l'ordre?

Answer 1

Les détails de mise en œuvre de HashMap peuvent et changent. Il est fort probable que cette méthode privée de package ait changé (c'est à partir de JDK 1.6.0_16) :

/**
 * Applique une fonction de hachage supplémentaire à un hachage donné, qui
 * protège contre les fonctions de hachage de mauvaise qualité. C'est critique
 * car HashMap utilise des tables de hachage de longueur puissance de deux,
 * qui sinon rencontrent des collisions pour les hachages qui ne diffèrent pas
 * dans les bits inférieurs. Note : Les clés nulles sont toujours mappées sur le hachage 0, donc l'index 0.
 */
static int hash(int h) {
    // Cette fonction garantit que les hachages qui ne diffèrent que de
    // constantes multiples à chaque position de bit ont un nombre limité
    // de collisions (environ 8 au facteur de charge par défaut).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Pour référence, l'équivalent dans JDK 1.5.0_06 est :

/**
 * Retourne une valeur de hachage pour l'objet spécifié. En plus du
 * propre hachage de l'objet, cette méthode applique une "fonction de hachage
 * supplémentaire" qui protège contre les fonctions de hachage de mauvaise qualité.
 * C'est critique car HashMap utilise des tables de hachage de longueur
 * puissance de deux.

Answer 2

Sans doute parce qu'une Map n'est pas définie pour avoir un ordre d'itération particulier ; l'ordre dans lequel les éléments reviennent est probablement un artefact de son implémentation interne et n'a pas besoin de rester cohérent.

Si l'implémentation est mise à jour entre Java 5 et 6 (en particulier pour des raisons de performances), il n'y a aucun avantage ou obligation pour Sun de garantir que l'ordre d'itération reste cohérent entre les deux.

MISE À JOUR : Je viens de trouver un extrait intéressant dans l'une des premières versions de Java 6 (malheureusement je ne suis pas sûr de la version exacte mais il s'agit apparemment de HashMap 1.68 de juin 2006) :

 /**
  * Si l'ancienne fonction de hachage supplémentaire doit être privilégiée, pour
  * la compatibilité avec les applications défectueuses qui reposent sur l'ordre de hachage interne.
  *
  * Défini sur vrai uniquement par HotSpot lorsqu'il est invoqué via
  * -XX:+UseNewHashFunction ou -XX:+AggressiveOpts
  */
 private static final boolean useNewHash;
 static { useNewHash = false; }

 private static int oldHash(int h) {
     h += ~(h << 9);
     h ^= (h >>> 14);
     h += (h << 4);
     h ^= (h >>> 10);
     return h;
 }

 private static int newHash(int h) {
     // Cette fonction garantit que les hashCode qui diffèrent uniquement par
     // des multiples constants à chaque position de bit ont un nombre limité
     // de collisions (environ 8 au facteur de charge par défaut).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

Il semble donc que malgré mes affirmations ci-dessus, Sun a effectivement pris en compte la cohérence de l'ordre d'itération - à un moment ultérieur, ce code a probablement été abandonné et le nouvel ordre est devenu le définitif.

Answer 3

HashMap n'est pas attaché à un ordre particulier, mais l'implémentation de LinkedHashMap de Map devrait préserver l'ordre.