Structure de stockage
Tout d'abord, Hashmap est stocké sur la base d'une table de hachage. Il y a un tableau à l'intérieur. Lorsqu'un élément doit être stocké, calculez d'abord la valeur de hachage de sa clé et trouvez l'indice correspondant de l'élément dans le tableau en fonction de la valeur de hachage. S'il n'y a pas d'élément à cette position, placez directement l'élément actuel. S'il y a un élément (rappelé comme un ici), liez l'élément actuel vers l'avant de l'élément A, puis placez l'élément actuel dans le tableau. Donc, dans Hashmap, le tableau enregistre en fait le premier nœud de la liste liée. Vous trouverez ci-dessous une image de Baidu Encyclopedia:
Comme le montre la figure ci-dessus, chaque élément est un objet d'entrée, où la clé et la valeur de l'élément sont enregistrées, et il y a un pointeur qui peut être utilisé pour pointer vers l'objet suivant. Toutes les clés avec la même valeur de hachage (c'est-à-dire le conflit) les enchaînent en utilisant une liste liée, qui est la méthode de la fermeture à glissière.
Variables internes
// Capacité initiale par défaut statique final int default_initial_capacity = 16; // Capacité maximale static final int maximum_capacity = 1 << 30; // facteur de charge par défaut statique float final default_load_factor = 0.75f; // TABLE HAST Entrée transitoire <k, v> [] Tableau; // Nombre de paires de clés; Hash Array Final Float LoadFactor;
Dans les variables ci-dessus, la capacité se réfère à la longueur de la table de hachage, c'est-à-dire la taille de la table, et la valeur par défaut est 16. Le facteur de charge de chargement est le "degré complet" de la table de hachage, et la documentation du JDK dit ceci:
Le facteur de charge est une mesure de la façon dont la table de hachage est pleine avant que sa capacité ne soit automatiquement augmentée. Lorsque le nombre d'entrées dans le tableau de hachage dépasse le produit du facteur de charge et de la capacité actuelle, le tableau de hachage est rétabli (c'est-à-dire que les structures de données internes sont reconstruites) afin que le tableau de hachage ait environ le double du nombre de seaux.
La signification générale est: le facteur de chargement est la mesure de la façon dont la table de hachage peut être installée avant l'expansion. Lorsque le nombre de «paires de valeurs clés» dans le tableau de hachage dépasse le produit de la capacité actuelle et du facteur de chargement, la table de hachage a haché (c'est-à-dire que la structure de données interne est reconstruite), et que la capacité de la table de hachage devient environ deux fois l'original.
Comme on peut le voir à partir de la définition de variable ci-dessus, le facteur de chargement par défaut default_load_factor est de 0,75. Plus cette valeur est grande, plus le taux d'utilisation de l'espace est élevé, mais la vitesse de requête (y compris Get and Put) ralentira. Après avoir compris le facteur de chargement, le seuil peut également le comprendre. Il est en fait égal au facteur de chargement de capacité *.
Constructeur
public hashmap (int initialCapacity, float loadfactor) {if (initialCapacity <0) lance un nouveau IllégalArgumentException ("Capacité initiale illégale:" + InitialCapacity); if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; if (loadFactor <= 0 || float.isnan (loadfactor)) lancez un nouveau IllégalArgumentException ("Facteur de charge illégal:" + LoadFactor); // Trouvez une puissance de 2> = InitialCapacity int Capacité = 1; tandis que (capacité <initialCapacity) // calculez la plus petite puissance de 2 qui est supérieure à la capacité de capacité spécifiée << = 1; this.loadFactor = LoadFactor; threshold = (int) math.min (capacité * chargefactor, maximum_capacity + 1); table = nouvelle entrée [capacité]; // allouer de l'espace à la table de hachage usEalthashing = Sun.Misc.vm.isbooted () && (capacité> = holder.alternative_hashing_threshold); init ();}Il y a plusieurs constructeurs, et ils finiront par appeler ce qui précède. Il accepte deux paramètres, l'un est la capacité initiale et l'autre est le facteur de chargement. Au début, nous déterminons d'abord si la combinaison de valeur est légale, et s'il y a un problème, une exception sera lancée. Ce qui est important, c'est le calcul de la capacité ci-dessous, sa logique est de calculer la plus petite puissance de 2 supérieure à la capacité initiale. En fait, le but est de rendre la capacité supérieure ou égale à la capacité initiale spécifiée, mais cette valeur doit être un multiple exponentiel de 2, ce qui est un problème clé. La raison en est principalement de cartographier les valeurs de hachage. Voyons d'abord la méthode de hachage dans Hashmap:
final int hash (objet k) {int h = 0; if (usailsalashing) {if (k instanceof String) {return Sun.Misc.Hashing.StringHash32 ((String) K); } h = graines de hashsh; } h ^ = k.hashcode (); // Cette fonction garantit que les codes de hashs qui différents sont différents par // les multiples constants à chaque position de bits ont un nombre de collisions délimitées (environ 8 au facteur de charge par défaut). h ^ = (h >>> 20) ^ (h >>> 12); retour h ^ (h >>> 7) ^ (h >>> 4);} static int indexfor (int h, int longueur) {return h & (longueur-1);}La méthode hash () recalcule la valeur de hachage de la clé et utilise des opérations de bits relativement complexes. Je ne connais pas la logique spécifique. Quoi qu'il en soit, c'est certainement une meilleure méthode, ce qui peut réduire les conflits ou quelque chose.
L'indexfor () ci-dessous est l'indice de l'élément dans le tableau de hachage en fonction de la valeur de hachage. Généralement, dans une table de hachage, vous utilisez des valeurs de hachage pour moduler la longueur du tableau. Lorsque la longueur (c'est-à-dire la capacité) est une puissance de 2, H & (longueur-1) est le même effet. De plus, la puissance de 2 doit être un nombre pair, puis après soustraire 1, c'est un nombre impair, et le dernier bit du binaire doit être 1. Ensuite, le dernier bit de H & (longueur-1) peut être 1 ou 0, ce qui peut être haché uniformément. Si la longueur est un nombre impair, alors la longueur-1 est un nombre pair et que le dernier bit est 0. À l'heure actuelle, le dernier bit de H & (longueur-1) peut être seulement 0, et toutes les indices résultants sont égaux, donc la moitié de l'espace est gaspillé. Par conséquent, la capacité de hashmap doit être une puissance de 2. Vous pouvez voir que la valeur par défaut_Initial_Capacity = 16 et maximum_capacity = 1 << 30 sont tous les deux comme ceci.
Objet d'entrée
Les paires de valeurs clés dans HashMap sont encapsulées dans des objets d'entrée, qui est une classe interne dans HashMap. Jetons un coup d'œil à sa mise en œuvre:
Entrée de classe statique <k, v> implémente Map.Entry <k, v> {Final K Key; V valeur v; Entrée <k, v> Suivant; int hash; Entrée (int h, k k, v v, entrée <k, v> n) {value = v; suivant = n; clé = k; hash = h; } public final k getkey () {return key; } public final v getValue () {return Value; } public final v setValue (v newValue) {v oldvalue = value; valeur = newValue; Retour OldValue; } public final booléen égaux (objet o) {if (! (o instanceof map.entry)) return false; Map.entry e = (map.entry) o; Objet k1 = getKey (); Objet k2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {objet v1 = getValue (); Objet v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) return true; } return false; } public final int hashcode () {return (key == null? 0: key.hashcode ()) ^ (value == null? 0: value.hashcode ()); } public final String toString () {return getKey () + "=" + getValue (); } void RecordAccess (hashmap <k, v> m) {}}L'implémentation de cette classe est simple et facile à comprendre. Des méthodes telles que getKey (), getValue () sont fournies pour l'appel. Pour déterminer l'égalité, il est nécessaire que la clé et la valeur soient égales.
opération
Mettez d'abord avant de l'obtenir, alors regardez la méthode put () d'abord:
public v put (k key, v valeur) {if (key == null) return putFornullKey (value); int hash = hash (key); int i = indexfor (hash, table.length); pour (entrée <k, v> e = table [i]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; Addentry (hachage, clé, valeur, i); retourner null;}Dans cette méthode, déterminez d'abord si la clé est nul. Si oui, appelez la méthode PutFornullkey (), ce qui signifie que HashMap permet à la clé d'être nulle (en fait, la valeur peut être). Si ce n'est pas nul, calculez la valeur de hachage et obtenez l'indice dans le tableau. Ensuite, accédez à la liste liée correspondante pour demander si la même clé existe déjà. S'il existe déjà, la valeur sera directement mise à jour. Sinon, appelez la méthode Addentry () pour l'insertion.
Jetez un œil à la méthode PutFornullkey ():
private v putFornullKey (V valeur) {pour (entrée <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) {v OldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; Addentry (0, null, valeur, 0); retourner null;}On peut voir que lorsque la clé est nul, la valeur sera mise à jour si elle existe, sinon Addentry () sera appelé à insérer.
Ce qui suit est la mise en œuvre de la méthode Addentry ():
void Addentry (int hash, k key, v valeur, int bucketIndex) {if ((size> = threshold) && (null! = table [bucketIndex])) {redimensit (2 * table.length); hash = (null! = key)? hash (clé): 0; BucketIndex = indexFor (hash, table.length); } CreateEntry (hash, key, valeur, bucketIndex);} void CreateEntry (int hash, k key, v valeur, int bucketIndex) {entrée <k, v> e = table [bucketIndex]; table [bucketIndex] = nouvelle entrée <> (hachage, clé, valeur, e); taille ++;}Tout d'abord, déterminez s'il faut étendre la capacité (la capacité en expansion recalculera la valeur de l'indice et copiera l'élément), puis calculera l'indice du tableau, et enfin insérer l'élément à l'aide de la méthode d'insertion d'en-tête dans CreateEntry ().
faire fonctionner
public v get (object key) {if (key == null) return getFornullKey (); Entrée <k, v> entrée = GetEntry (clé); retourner null == entrée? null: entry.getValue ();} private v getFornullkey () {for (entrée <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) return e.value; } return null;} entrée finale <k, v> gentry (clé d'objet) {int hash = (key == null)? 0: Hash (clé); pour (entrée <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e; } retourner null;}C'est plus simple que put (). Vous devez également déterminer si la clé est nul, puis la requête de traversée de la liste liée.
Optimisation des performances
Hashmap est une structure de données efficace et universelle qui peut être vue partout dans chaque programme Java. Présentons d'abord quelques connaissances de base. Comme vous pouvez également le savoir, HashMap utilise les méthodes de clé HashCode () et Equals () pour diviser les valeurs en différents seaux. Le nombre de seaux est généralement légèrement plus grand que le nombre d'enregistrements dans la carte, de sorte que chaque seau comprendra moins de valeurs (de préférence une). Lors de la recherche de touches, nous pouvons rapidement localiser un seau (en utilisant HashCode () pour modulo le nombre de seaux) et l'objet que nous recherchons en temps constant.
Vous devriez déjà savoir toutes ces choses. Vous savez peut-être également que les collisions de hachage peuvent avoir un impact catastrophique sur les performances de HashMap. Si plusieurs valeurs HashCode () entrent dans le même seau, ces valeurs sont stockées dans une liste liée. Dans le pire des cas, toutes les clés sont cartographiées dans le même seau, donc le hashmap dégénère en une liste liée - le temps de recherche est de O (1) à O (n). Tissons d'abord les performances de Hashmap dans Java 7 et Java 8 dans des circonstances normales. Afin de contrôler le comportement de la méthode HashCode (), nous définissons une classe clé comme suit:
Classe Key implémente Comparable <Tey> {private final int Value; Key (int Value) {this.value = value;} @ OverRidepublic int compareto (key o) {return Integer.Compare (this.value, o.value);} @ overdepublic boolean equals (objet o) {if (this == o) return; o.getClass ()) return false; key key = (key) o; return value == key.value;} @ overRidepublic int hashcode () {return value;}}La mise en œuvre de la classe clé est assez standard: il réécrit la méthode equals () et fournit une méthode HashCode () assez décente. Pour éviter un GC excessif, j'ai mis en cache l'objet de clé immuable au lieu de recommencer à le créer à chaque fois:
Class Key implémente comparable <yey> {public class Keys {public static final int max_key = 10_000_000; touche finale statique privée [] keys_cache = new Key [max_key]; statique {for (int i = 0; i <max_key; ++ i) {keys_cache [i] = new key (i);}} Keys_cache [valeur];}Maintenant, nous pouvons commencer à tester. Notre référence utilise des valeurs de clés continues pour créer des hachages de différentes tailles (multiplicateur pour 10, de 1 à 1 million). Dans le test, nous utiliserons également des clés pour rechercher et mesurer le temps nécessaire pour les hashmaps de différentes tailles:
import com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper.simplebenchmark; classe publique MapBenchmark étend SimpleBenchmark {private hashmap <key, induger> map; @paramprivate int mapsize; @overRideProtected Void SetUp () lève exception {maphy Hashmap <> (mapSize); for (int i = 0; i <mapSize; ++ i) {map.put (keys.of (i), i);}} public void timeMapGet (int représentants) {for (int i% mapsize));}}}}Fait intéressant, dans ce simple hashmap.get.get (), Java 8 est 20% plus rapide que Java 7. La performance globale est également assez bonne: bien qu'il y ait un million d'enregistrements dans Hashmap, une seule requête n'a pris que moins de 10 nanosecondes, ce qui représente environ 20 cycles de processeur sur ma machine. Très choquant! Mais ce n'est pas ce que nous voulons mesurer.
Supposons qu'il y ait une mauvaise clé, elle renvoie toujours la même valeur. C'est le pire scénario, et vous ne devriez pas du tout utiliser Hashmap:
La clé de classe implémente comparable <yey> {//...@overridepublic int hashcode () {return 0;}}Les résultats de Java 7 sont attendus. À mesure que la taille de Hashmap augmente, les frais généraux de la méthode get () deviennent de plus en plus gros. Étant donné que tous les enregistrements se trouvent dans la liste des liens ultra-longs dans le même seau, la recherche d'une moyenne d'un enregistrement nécessite la traversée de la moitié de la liste. Par conséquent, on peut voir à partir de la figure que sa complexité temporelle est O (n).
Cependant, Java 8 fonctionne beaucoup mieux! Il s'agit d'une courbe de journal, donc ses performances sont mieux les ordres de grandeur. Malgré le pire des cas de collisions sévères de hachage, cette même référence a une complexité temporelle dans JDK8 d'O (Log). Si vous regardez la courbe de JDK 8 seule, ce sera plus clair. Ceci est une distribution linéaire logarithmique:
Pourquoi y a-t-il une si grande amélioration des performances, même si le symbole Big O est utilisé ici (Big O décrit la limite supérieure asymptotique)? En fait, cette optimisation a été mentionnée dans JEP-180. Si l'enregistrement dans un seau est trop grand (actuellement Treeny_Threshold = 8), Hashmap le remplacera dynamiquement par une implémentation TREEMAP spéciale. Cela se traduira par de meilleurs résultats, O (Logn), pas mal o (n). Comment ça marche? Les enregistrements correspondant à la clé qui ont des conflits devant sont simplement annexés à une liste liée, et ces enregistrements ne peuvent être trouvés que via la traversée. Cependant, après avoir dépassé ce seuil, HashMap commence à mettre à niveau la liste en arbre binaire, en utilisant la valeur de hachage comme variable de branche de l'arbre. Si les deux valeurs de hachage ne sont pas égales mais pointant vers le même seau, la plus grande sera insérée dans le sous-arbre droit. Si les valeurs de hachage sont égales, HashMap espère que la valeur de clé est mieux implémentée par l'interface comparable afin qu'elle puisse être insérée dans l'ordre. Ce n'est pas nécessaire pour la clé de Hashmap, mais c'est bien sûr le meilleur s'il est mis en œuvre. Si cette interface n'est pas mise en œuvre, vous ne devez pas vous attendre à obtenir des améliorations de performances en cas de collisions de hachage sévères.
À quoi sert cette amélioration des performances? Par exemple, un programme malveillant, s'il sait que nous utilisons un algorithme de hachage, il peut envoyer un grand nombre de demandes, ce qui entraîne de graves collisions de hachage. Ensuite, l'accès constamment à ces clés peut affecter considérablement les performances du serveur, ce qui conduit à une attaque de déni de service (DOS). Le saut de O (n) à O (Logn) dans JDK 8 peut prévenir efficacement des attaques similaires, tout en améliorant légèrement la prévisibilité des performances de hashmap. J'espère que cette amélioration convaincra finalement votre patron d'accepter de passer à JDK 8.
L'environnement utilisé pour le test est: Intel Core i7-3635qm @ 2,4 GHz, mémoire 8 Go, disque dur SSD, en utilisant des paramètres JVM par défaut, fonctionnant sur un système Windows 8.1 64 bits.
Résumer
La mise en œuvre de base de HashMap est comme analysée ci-dessus, et enfin le résumé est fait: