Comment Java classe-t-il les articles dans HashMap ou HashTable?

Je me demandais comment Java commande les éléments dans la Map ( HashMap ou Hashtable ) lorsqu’ils sont ajoutés. Les clés sont-elles classées par code de hachage, référence de mémoire ou par priorité de répartition …?

C’est parce que j’ai remarqué que les mêmes paires dans la Map ne sont pas toujours dans le même ordre

java.util.HashMap n’est pas ordonné; vous ne pouvez pas et ne devez pas supposer quoi que ce soit d’autre.

Cette classe ne fait aucune garantie quant à l’ordre de la carte; en particulier, cela ne garantit pas que la commande restra constante dans le temps.

java.util.LinkedHashMap utilise un ordre d’insertion.

Cette implémentation diffère de HashMap dans la mesure où elle gère une liste à double liaison exécutant toutes ses entrées. Cette liste liée définit l’ordre d’itération, qui est normalement l’ordre dans lequel les clés ont été insérées dans la carte (ordre d’insertion).

java.util.TreeMap , un SortedMap , utilise un ordre naturel ou personnalisé des clés.

La carte est sortingée en fonction de l’ordre naturel de ses clés ou d’un Comparator fourni au moment de la création de la carte, en fonction du constructeur utilisé.

Tout d’abord: HashMap ne fournit pas spécifiquement un ordre stable et / ou défini. Donc, tout ce que vous observez est simplement un détail d’implémentation et vous ne devez pas en dépendre.

Comme il est parfois utile de connaître la raison de l’ordre apparemment aléatoire, voici l’idée de base:

Un HashMap a un nombre de HashMap (implémentés en tant que tableau) dans lesquels stocker les entrées.

Lorsqu’un élément est ajouté à la carte, il est affecté à des compartiments en fonction d’une valeur dérivée de son hashCode et de la taille de HashMap du HashMap . (Notez qu’il est possible que le compartiment soit déjà occupé, ce qui s’appelle une collision. C’est géré correctement et correctement, mais je vais ignorer cette manipulation pour la description car elle ne change pas le concept).

L’ordre des entrées (tel que renvoyé par une itération sur la Map ) perçu dépend de l’ordre des entrées dans ces compartiments.

Chaque fois que la taille est répétée (parce que la carte dépasse son seuil de saturation), le nombre de compartiments change, ce qui signifie que la position de chaque élément peut changer, car la position du compartiment est également dérivée du nombre de compartiments.

HashMap ne sortinge pas du tout. Pour une carte sortingée par valeurs de clé, vous devez utiliser TreeMap place.

A partir des JavaDocs pour TreeMap :

Implémentation basée sur l’arbre rouge-noir de l’interface SortedMap. Cette classe garantit que la carte sera en ordre croissant, sortingée en fonction de l’ordre naturel de la classe de la clé (voir Comparable) ou du comparateur fourni au moment de la création, en fonction du constructeur utilisé.

De la documentation de HashMap :

Cette classe ne fait aucune garantie quant à l’ordre de la carte; en particulier, cela ne garantit pas que la commande restra constante dans le temps.

Une Map n’est pas une structure de données ordonnée – vous ne devez pas compter sur des entrées dans un HashMap dans un certain ordre. Certaines implémentations Map telles que LinkedHashMap et TreeMap garantissent un certain ordre, contrairement à HashMap .

Si vous voulez vraiment savoir ce qui se passe en interne, recherchez le code source de HashMap – vous pouvez le trouver dans src.zip, qui doit se trouver dans votre répertoire d’installation JDK.

Un HashMap a un certain nombre de “compartiments” dans lesquels il stocke ses entrées. Le seau dans lequel une entrée est stockée est déterminé par le code de hachage de la clé de l’entrée. L’ordre dans lequel vous voyez les entrées dans HashMap dépend des codes de hachage des clés. Mais n’écrivez pas les programmes qui reposent sur des entrées dans un certain ordre dans un HashMap – l’implémentation pourrait changer dans une future version de Java et votre programme ne fonctionnerait alors plus.

hashmap a un ordre non défini des éléments

Il n’y a pas de classement défini dans une table de hachage. Les clés sont placées dans un emplacement, sur la base du code de hachage, mais même cela n’est pas un ordre sortingvial.

HashMap stocke les valeurs en utilisant la valeur de hachage unique générée à l’aide d’une partie de la clé. Cette valeur de hachage correspond à l’adresse où elle va être stockée. C’est ainsi qu’il assure un access O (1).

LinkedHashmap conserve par ailleurs l’ordre dans lequel vous avez ajouté à la carte.