Quel est le mécanisme d'expansion de hashmap ?

Le mécanisme d'expansion de hashmap est le suivant : recalculer la capacité et remplacer le tableau d'origine par un nouveau tableau. Recalculez toutes les données du tableau d'origine et insérez un nouveau tableau, puis pointez vers le nouveau tableau ; si le tableau a atteint la valeur maximale avant l'expansion de la capacité, définissez directement le seuil sur l'entier maximum et renvoyez-le.

L'environnement d'exploitation de ce tutoriel : système windows7, java8, ordinateur Dell G3.

Qu'est-ce que le redimensionnement ?

Expansion (redimensionnement) : il s'agit de recalculer la capacité et d'ajouter continuellement des éléments à l'objet HashMap. Lorsque le tableau à l'intérieur de l'objet HashMap ne peut pas charger plus d'éléments, l'objet doit étendre la longueur du tableau pour pouvoir. être chargé. Plus d’éléments. Bien sûr, les tableaux en Java ne peuvent pas être automatiquement étendus. La méthode consiste à utiliser un nouveau tableau pour remplacer le tableau existant avec une petite capacité. Tout comme nous utilisons un petit seau pour contenir de l'eau, si nous voulons contenir plus d'eau, nous en avons. pour passer à un seau plus grand.

Quand la capacité sera-t-elle augmentée ?

Lors de l'ajout d'éléments à un conteneur, le nombre d'éléments dans le conteneur actuel sera jugé s'il est supérieur ou égal au seuil (seuil), c'est-à-dire lorsque le nombre d'éléments dans le conteneur actuel est. supérieure à la longueur du tableau actuel multipliée par la valeur du facteur de chargement, il sera automatiquement étendu.

Principe d'expansion de hashmap

L'expansion de hashMap consiste à recalculer la capacité et à ajouter continuellement des éléments à hashMap. Lorsque hashMap ne peut pas charger de nouveaux éléments, l'objet devra augmenter la capacité du tableau afin de charger plus d'éléments.

Caractéristiques d'expansion de la capacité HashMap, plus le facteur de chargement est grand, plus l'utilisation de l'espace est élevée, plus il faut remplir d'éléments avant l'expansion, plus l'opération de mise est rapide, mais la liste chaînée est facile à être trop longue, le la probabilité de collision de hachage est élevée et l'opération d'obtention est lente. Plus le facteur de chargement est petit, plus l'opération d'obtention est rapide, plus la liste chaînée est courte et plus la probabilité de collision de hachage est faible. Cependant, l'utilisation de l'espace est faible. Trop d’éléments mis entraîneront une expansion fréquente et affecteront les performances.

Le principe d'expansion de capacité de HashMap : La méthode de Hashmap consiste à remplacer le tableau d'origine par un nouveau tableau, à recalculer toutes les données du tableau d'origine, à insérer le nouveau tableau, puis à pointer vers le nouveau tableau si ; le tableau a atteint le maximum avant l'expansion, puis définissez directement le seuil sur l'entier maximum renvoyé.

Le processus d'expansion

Ce qui suit utilise le code source + les images + la description textuelle pour présenter le processus d'expansion de HashMap.

/** 
 * HashMap 添加节点 
 * 
 * @param hash        当前key生成的hashcode 
 * @param key         要添加到 HashMap 的key 
 * @param value       要添加到 HashMap 的value 
 * @param bucketIndex 桶，也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标 
 */  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    //数组扩容条件：1.已经存在的key-value mappings的个数大于等于阈值  
    //             2.底层数组的bucketIndex坐标处不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//扩容之后，数组长度变了  
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢？  
        bucketIndex = indexFor(hash, table.length);//扩容之后，数组长度变了，在数组的下标跟数组长度有关，得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  
  
/** 
 * 这地方就是链表出现的地方，有2种情况 
 * 1，原来的桶bucketIndex处是没值的，那么就不会有链表出来啦 
 * 2，原来这地方有值，那么根据Entry的构造函数，把新传进来的key-value mapping放在数组上，原来的就挂在这个新来的next属性上了 
 */  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K, V> e = table[bucketIndex];  
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);  
    size++;  
}

Dans la méthode addEntry ci-dessus, si la taille (nombre d'éléments dans le conteneur actuel) est supérieure ou égale au seuil (longueur du tableau multipliée par le facteur de charge) et que la coordonnée bucketIndex du tableau sous-jacent n'est pas égale à null, puis l'expansion (redimensionnement) sera effectuée). Sinon, l’expansion n’aura pas lieu.

Ce qui suit se concentrera sur le processus d'expansion :

        void resize(int newCapacity) {   //传入新的容量
            Entry[] oldTable = table;    //引用扩容前的Entry数组
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
                threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                return;
            }
     
            Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
            transfer(newTable);	此行有遗漏，勘误见下面引用	//！！将数据转移到新的Entry数组里
            table = newTable;                           //HashMap的table属性引用新的Entry数组
            threshold = (int) (newCapacity * loadFactor);此行有遗漏，勘误见下面引用//修改阈值
        }

Corrigé par le blogueur wenni328 : transfer(newTable); ==> transfer(newTable, initHashSeedAsNeeded(newCapacity));
threshold = (int) (newCapacity * loadFactor); ==> seuil = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

Avant l'expansion, obtenez d'abord l'adresse de référence du tableau avant l'expansion et stockez-le dans la variable oldTable, puis déterminez si la longueur du tableau avant l'expansion a atteint la valeur maximale stockée dans le type int. Si tel est le cas, abandonnez l'expansion car la capacité du tableau a atteint le maximum et ne peut pas être étendue.

L'image ci-dessous montre l'état après l'exécution du programme Entry[] newTable = new Entry[newCapacity]; code :

Voici comment utiliser un tableau avec une plus grande capacité pour remplacer le tableau existant avec une capacité plus petite. , la méthode transfer( ) copie les éléments du tableau Entry d'origine dans le nouveau tableau Entry.

        void transfer(Entry[] newTable) {
            Entry[] src = table;                   //src引用了旧的Entry数组
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
                Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
                if (e != null) {
                    src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                    do {
                        Entry<K, V> next = e.next;
                        int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                        e.next = newTable[i]; //标记[1]
                        newTable[i] = e;      //将元素放在数组上
                        e = next;             //访问下一个Entry链上的元素
                    } while (e != null);
                }
            }
        }

        static int indexFor(int h, int length) {
            return h & (length - 1);
        }

La référence de newTable[i] est attribuée à e.next, c'est-à-dire qu'elle utilise la méthode d'insertion de tête d'une liste à chaînage unique, et les nouveaux éléments à la même position seront toujours placés en tête de la liste liée list ; de cette manière, ils sont d'abord placés dans une liste. L'élément à l'index sera finalement placé à la fin de la chaîne Entry (si un conflit de hachage se produit). Les éléments de la même chaîne d'entrée dans l'ancien tableau peuvent être placés à différentes positions dans le nouveau tableau après avoir recalculé la position d'index.

Le processus de transfert sera démontré sous forme d'images ci-dessous (les polices rouges dans les images ci-dessous indiquent les différences par rapport aux images ci-dessus. Les images suivantes sont comme ceci, et les descriptions en polices rouges ne seront pas répétées)

L'image ci-dessous montre la fin de l'exécution du programme. src[j] = null; L'état après le code (c'est l'état lors de la première boucle) :

Tout d'abord, attribuez l'adresse de référence du tableau table[] au tableau src[].

Ensuite, Entry e = src[j]; consiste à transférer la liste chaînée à la position src[j] vers la variable e pour le stockage. Puisque la liste chaînée à src[j] a été donnée à e pour le stockage, vous pouvez hardiment définir src[j]=null puis attendre le garbage collection;

L'image ci-dessous montre l'état après que le programme exécute le code Entry next = e.next; (c'est l'état lors de la première boucle) :

Ici, changez d'abord la valeur de e. .next Sauvegarder jusqu'à la variable suivante. Le code suivant changera le pointeur de e.next, donc la valeur de e.next est sauvegardée ici.

L'image ci-dessous montre l'état après que le programme exécute le code e.next = newTable[i]; (c'est l'état lors de la première boucle) :

Puisque la valeur de newTable[3] est nulle , donc e.next est nul, comme le montre la figure ci-dessus.

L'image ci-dessous montre l'état après que le programme exécute le code newTable[i] = e; (c'est l'état lors de la première boucle) :

L'image ci-dessous montre l'état après que le programme exécute e = next; code Status (c'est l'état lors de la première boucle) :

Comme indiqué ci-dessus, le nœud Entry1 est inséré avec succès dans newTable, car e!=null est jugé, le. Le processus ci-dessus sera répété jusqu'à ce que tous les nœuds soient déplacés vers newTable.

Résumé

• L'expansion est une opération particulièrement gourmande en performances, donc lorsque les programmeurs utilisent HashMap, ils doivent estimer la taille de la carte et donner une valeur approximative lors de l'initialisation pour éviter une expansion fréquente de la carte.
• Le facteur de charge est modifiable et peut être supérieur à 1, mais il est recommandé de ne pas le modifier facilement sauf si la situation est très particulière.
• HashMap n'est pas sécurisé pour les threads. N'utilisez pas HashMap en même temps dans un environnement simultané. Il est recommandé d'utiliser ConcurrentHashMap.
• JDK1.8 introduit des arbres rouge-noir pour optimiser considérablement les performances de HashMap.

Pour plus de connaissances liées à la programmation, veuillez visiter : Enseignement de la programmation ! !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!