编程知识 cdmana.com

Absolument!C'est l'analyse la plus détaillée du code source de hashtap que j'ai jamais vu!

1 Généralités

HashMapEst basé sur une table de hachage,Chaque élément est unkey-valueC'est exact.,Son intérieur résout les conflits au moyen d'une liste à chaîne unique,Capacité insuffisante(Dépassement du seuil)Heure,De même, la croissance automatique.

HashMapN'est pas Thread - SAFE,Uniquement pour les environnements monothreadés,Un environnement Multi - threadé peut utiliser des paquets simultanésconcurrentHashMap

HashMap C'est fait.SerializableInterface,Il supporte donc la sérialisation,C'est fait.CloneableInterface,Peut être cloné

HashMapEst basé sur une table de hachageMapMise en œuvre asynchrone de l'interface.Cette implémentation fournit toutes les opérations de cartographie optionnelles,Et permet l'utilisationnullValeur etnullClé.Cette classe ne garantit pas l'ordre des cartes,En particulier, il ne garantit pas que l'ordre est constant.

Java8Cette mise en œuvre sous - jacente est optimisée,Comme l'introduction de la structure de l'arbre Rouge et noir pour résoudre les collisions de hachage

2 HashMapStructure des données pour

InJavaMoyenne,Les structures de base sont les suivantes:,L'un est un tableau,L'autre est un pointeur analogique(Références),Toutes les structures de données peuvent être construites avec ces deux structures de base,HashMapEt ça ne fait pas exception.
HashMapEn fait, c'est un"Hachage de la liste de liens"Structure des données pour,C'est - à - dire une combinaison de tableaux et de listes liées.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source
 

HashMapLa structure principale est similaire à un tableau,Ajouter une valeur parkeyDéterminer l'emplacement de stockage.

Chaque emplacement est unEntryStructure des données pour,Cette structure peut constituer une liste de liens.

En cas de conflit,Même chose.hashLes paires de valeurs clés forment une liste de liens.

Ce tableau + Les combinaisons de listes enchaînées donnent de bons résultats dans la plupart des cas ,Java6、7C'est comme ça que ça a été conçu.

Et pourtant,Dans des cas extrêmes,Groupe I(Par exemple, bien conçu)Les deux paires de valeurs clés sont en conflit,La structure de hachage devient alors une liste liée,FaireHashMapChute brutale des performances.

Donc, dansJava8Moyenne,HashMapL'implémentation de la structure devient un tableau+Liste des liens+Arbre Rouge et noir

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source_02
 

Comme vous pouvez le voir,,HashMapLe rez - de - chaussée est une structure de tableau
Chaque élément du tableau est une autre liste liée
Quand un nouveauHashMapHeure,Un tableau est initialisé.

3 Trois grands ensembles et itérateurs

HashMapUtilisez trois grands ensembles et trois itérateurs pour les sonderKey、ValueEtEntryObjet

public class HashMapExam {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>(16);
        for (int i = 0; i < 15; i++) {
            map.put(i, new String(new char[]{(char) ('A'+ i)}));
        }

        System.out.println("======keySet=======");
        Set<Integer> set = map.keySet();
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("======values=======");
        Collection<String> values = map.values();
        Iterator<String> stringIterator=values.iterator();
        while (stringIterator.hasNext()) {
            System.out.println(stringIterator.next());
        }

        System.out.println("======entrySet=======");
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry);
        }
    }
}

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
4 Analyse des sources
    //Capacité initiale par défaut16,Et la capacité réelle est2Puissance entière de 
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    //Capacité maximale(La capacité d'entrée excessive sera remplacée par cette valeur)
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // Le facteur de charge par défaut est0.75(Quand le compteur atteint3/4Pleine heure,Pour hacher à nouveau),Ce facteur établit un équilibre entre le coût du temps et celui de l'espace.Des facteurs plus élevés peuvent réduire l'espace nécessaire au tableau,Mais cela augmente le coût de la recherche,Et la recherche est l'opération la plus fréquente
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //Seuil d'arborescence du baril:C'est - à - dire: Seuil de conversion de la liste liée en arbre Rouge et noir,Lors du stockage des données,Lorsque la longueur de la Liste >= 8Heure,Convertit la liste liée en arbre Rouge et noir
    static final int TREEIFY_THRESHOLD = 8;
   // Seuil de restauration de la liste des seaux:C'est - à - dire: Seuil de conversion des arbres rouges et noirs en listes liées,Quand on agrandit(resize())Heure(HashMapL'emplacement de stockage des données pour sera recalculé),Après avoir recalculé l'emplacement de stockage,Quand le nombre d'arbres rouges et noirs d'origine <= 6Heure,Alors Arbre rouge noir converti en liste liée
    static final int UNTREEIFY_THRESHOLD = 6;
   //Seuil minimal de capacité arborescente:C'est - à - dire: Quand la capacité dans la table de hachage > À cette valeur,Pour permettre l'arborescence de la liste (C'est - à - dire: Liste des liens Convertir en arbre Rouge et noir)

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.

Parce que la longueur moyenne de recherche d'un arbre Rouge et noir estlog(n),La longueur est8Quand,La longueur moyenne de la recherche est3,Si vous continuez à utiliser la liste liée,La longueur moyenne de la recherche est8/2=4,C'est ce qui rend nécessaire la conversion en arbre

Longueur de la liste si elle est inférieure ou égale à6,6/2=3,Même si c'est rapide,Mais le temps de conversion en structure d'arbre et de génération d'arbre ne sera pas trop court

Il y a d'autres options6Et8,Il y a une différence entre7Peut efficacement empêcher les listes liées et les arbres de changer fréquemment

Supposons que,Si le nombre de listes conçues dépasse8La liste liée est convertie en structure arborescente,Le nombre de listes liées est inférieur à8Ensuite, la structure de l'arbre est convertie en liste liée,Si unHashMapInsertion continue、Supprimer l'élément,Nombre de listes liées8Errer à gauche et à droite,La liste des liens d'arbre se produit fréquemment、Arbre de rotation de la liste liée,Ça va être inefficace..

    // Pour éviter l'expansion/Conflits de sélection arborescente,Cette valeur ne peut être inférieure à 4 * TREEIFY_THRESHOLD
    // En dessous de cette valeur, l'expansion est utilisée!!!
    static final int MIN_TREEIFY_CAPACITY = 64;

    // Stockage des donnéesNodeTableau,La longueur est2Puissance.    
    // HashMapRésoudre les conflits en utilisant la méthode de la liste de liens,ChaqueNodeEssentiellement une liste unidirectionnelle 
    //HashMapStructure des données pour le stockage sous - jacent,C'est unNodeTableau.Il paraît queNodeLa classe maintient une liste unidirectionnelle des éléments.Jusqu'ici.,HashMapLa structure des données stockées est également claire:Un tableau a été maintenu,Chaque tableau maintient une liste unidirectionnelle.C'est pour ça que,Vu qu'en cas de conflit de hachage,Même chose.indexDevalueLes valeurs sont maintenues à l'aide d'une liste unidirectionnelle
    //Avec JDK 1.7 Comparaison(EntryCatégorie),J'ai juste changé de nom
    transient Node<K,V>[] table;

    // HashMapNombre de fentes utilisées dans le tableau sous - jacent de 
    transient int size;
    // HashMapSeuil pour,Utilisé pour déterminer si un ajustement est nécessaireHashMapCapacité(threshold = Capacité*Facteur de charge) 
    int threshold;

    // Facteur de charge taille réelle
    final float loadFactor;

    // HashMapNombre de changements 
    transient int modCount;

    // Désignation“Taille de la capacité”Et“Facteur de charge”Le constructeur de,Est le constructeur le plus basique
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // HashMapLa capacité maximale ne peut être que deMAXIMUM_CAPACITY                                       
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //Le facteur de charge doit être supérieur à0
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // Paramètres"Facteur de charge"                                        
        this.loadFactor = loadFactor;
        // Paramètres"HashMapSeuil",QuandHashMapLa quantité de données stockées dansthresholdHeure,Il faut justeHashMapDouble la capacité de    
        this.threshold = tableSizeFor(initialCapacity);
    }

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • Au - dessustableSizeForÀ quoi bon??
    tableSizeForLa méthode garantit que la valeur de retour de la fonction est supérieure ou égale à un paramètre donnéinitialCapacityLe plus petit2La valeur numérique de la puissance de
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.

On peut voir que la méthode est une série d'opérations binaires

a |= b équivalent à a = a|b

Analyse ligne par ligne

  • int n = cap - 1

Donnécap Moins 1,Pour éviter les paramètrescapC'est ça.2Puissance de,C'est comme ça.,Après un suivi,capVa devenir2 * cap,Ce n'est pas ce que nous attendions

  • n |= n >>> 1

n >>> 1 : nDéplacement à droite non signé1Bits,C'est - à - dire:nBinaire supérieur1À droite

n | (n >>> 1) Cause nBinaire élevé2La valeur du BIT est1

Pour l'instantnHaut1~2Tous les bits sont1

  • n |= n >>> 2

nContinuer sans symbole à droite2Bits

n | (n >>> 2) CausenHaute représentation binaire3~4Les valeurs de bitpass sont toutes1

Pour l'instantnHaut1~4Tous les bits sont1

  • n |= n >>> 4

nContinuer sans symbole à droite4Bits

n | (n >>> 4) CausenHaute représentation binaire5~8Les valeurs de bitpass sont toutes1

Pour l'instantnHaut1~8Tous les bits sont1

  • n |= n >>> 8

nContinuer sans symbole à droite8Bits

n | (n >>> 8) CausenHaute représentation binaire9~16Les valeurs de bitpass sont toutes1

Pour l'instantnHaut1~16Tous les bits sont1

Comme vous pouvez le voir,,Peu importecap(cap < MAXIMUM_CAPACITY )Quelle est la valeur de,Après les calculs ci - dessus,Tous les bits binaires de sa valeur seront1.Ajouter1,Cette valeur doit être2Puissance de.
Bien sûr, si la valeur calculée est supérieure àMAXIMUM_CAPACITY,Sélection directeMAXIMUM_CAPACITY.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_03
 

Jusqu'ici.tableSizeForComment garantircapPour2La puissance de,Alors la question se pose

4.1PourquoicapPour rester2Puissance de?

Principalement avecHashMapLe stockage de données dans.

InJava8Moyenne,HashMapMoyennekeyDeHashValeur parHash(key)La méthode calcule

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Programmeur_04
 

HashMapDonnées stockées danstableDeindexC'est parkeyDeHashValeur déterminée.

InHashMapLors du stockage des données,Nous nous attendons à ce que les données soient réparties uniformément,Pour éviter les conflits de hachage.

Naturellement, nous pensons à l'utiliser%Pour réaliser notre vision

Prends le reste(%)Fonctionnement : Si le diviseur est2La puissance de est égale à la somme de son diviseur moins un(&)Fonctionnement.

C'est pourquoi il fautcapPour2Puissance de.Revenez voirtableDeindexRègles de calcul pour:

C'est pourquoi il fautcapPour2Puissance de.Revenez voirtableDeindexRègles de calcul pour:

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Programmeur_05

Équivalent à:

 index = e.hash % newCap

     
  • 1.

Fonctionnement binaire&,Par rapport à%,Capable d'améliorer l'efficacité du calcul,C'est ça.capLa valeur de est requise pour2La cause de la puissance

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source_06
 
Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source_07
 
4.2NodeCatégorie
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }


     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.

Node<K,V> La classe estHashMapClasse interne statique en,RéalisationMap.Entry<K,V>Interface.DéfinikeyClé、valueValeur、nextNoeud,C'est - à - dire qu'une liste unidirectionnelle est formée entre les éléments.

4.3 TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {}

        // Renvoie le noeud racine du noeud courant  
        final TreeNode<K,V> root() {  
          for (TreeNode<K,V> r = this, p;;) {  
            if ((p = r.parent) == null)  
                return r;  
            r = p;  
        }  
    } 
 }

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.

La structure de l'arbre Rouge et noir contient、Après、Gauche.、Noeud droit,Et si le drapeau est rouge et noir
Cette structure estJava8Nouveau

4.4 hashMéthodes

Java 8Fonction d'optimisation de la valeur de hachage dans

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_HashMap_08
 

Juste une fois16Déplacement à droite Xor

key.hashCode()La fonction appellekeyFonction de hachage fournie avec le type de valeur clé,RetourintValeur de hachage de type

En théorie, la valeur de hachage estintType,Si vous accédez directement à la valeur de hachage comme indiceHashMapSi le tableau principal,Considérant que2Décimal32Bits signésintPortée approximative40Un espace de cartographie de milliards.Tant que les fonctions de hachage sont cartographiées uniformément et vaguement,Il est difficile d'entrer en collision avec une application générale.

Mais le problème, c'est que40Un tableau de milliards de longueurs,Il n'y a pas de mémoire..HashMapLa taille initiale du tableau avant l'expansion16,Donc cette valeur de hachage ne peut pas être utilisée directement.

Il faut d'abord modéliser la longueur du tableau avant de l'utiliser,Le reste obtenu peut être utilisé pour accéder à l'indice Array

L'opération modulaire dans le code source est de faire une valeur de hachage et la longueur du tableau"Avec"Fonctionnement

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source_09
 

Ça explique aussi pourquoiHashMapLa longueur du tableau pour2Toute la puissance de

Parce que...(Longueur du tableau-1)Exactement l'équivalent d'un“Masque bas”

“Avec”Le résultat de l'opération est que tous les bits supérieurs de la valeur de hachage sont réinitialisés à zéro,Seules les valeurs inférieures sont réservées,Utilisé pour accéder à un index de tableau

En longueur initiale16Par exemple,16-1=15

2La représentation décimale est00000000 00000000 00001111

Et une certaine valeur de hachage“Avec”Les opérations sont les suivantes,Le résultat est que les quatre chiffres les plus bas ont été tronqués

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_10
 

Mais c'est là que la question se pose,De cette façon, même si ma distribution des valeurs de hachage est encore lâche,Si seulement les derniers chiffres,Les collisions peuvent aussi être graves

À ce moment - là.“Fonction de perturbation”La valeur de

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Java_11

Déplacement à droite16Bits,Exactement.32La moitié,La moitié haute et la moitié basse de soi font Xor,C'est pour mélanger l'originalhashCodeHaut et bas de,Pour augmenter le caractère aléatoire de la position inférieure
Et la partie inférieure du mélange dope une partie de la caractéristique supérieure,Cette information de haut niveau est conservée sous une forme déguisée.

indexLa règle de calcul pour

e.hash & (newCap - 1)

     
  • 1.

newCap- Oui.2Puissance,Alors...newCap - 1Tous les sommets de0

Sie.hashLa valeur n'utilise que sa proprehashcode,indexSeulement avece.hashLe bas de&Fonctionnement.C'est comme ça.,indexLa valeur de n'a qu'une faible implication dans l'opération,Le Haut n'a aucun sens de l'existence,Il y a donc un risque de conflit de hachage

Donc je calculekeyDehashCodeHeure,Avec son proprehashCodeAu lieu d'être bas16BIT pour Xor

C'est ce qui amène les cadres supérieurs àindexDans les calculs de,C'est - à - dire réduire le risque de conflit de hachage sans trop de problèmes de performance

4.5 PutMéthodes
Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Java_12
 
Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Programmeur_13
 

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Java_14

①.Déterminer la valeur de la clé par rapport au tableautable[i]Est vide ou estnull,Sinon, exécutezresize()Pour agrandir

②.Selon la valeur de la clékeyCalculhashValeur de l'index du tableau inséréi,Sitable[i]==null,Ajouter un nouveau noeud directement,Direction⑥,Sitable[i]Pas vide,Direction③

③.Jugementtable[i]Le premier élément dekeyC'est pareil,Si la même couverture directevalue,Sinon, tournez④,La même chose ici, c'est quehashCodeEtequals

④.Jugementtable[i] Oui NontreeNode,C'est - à - dire:table[i] Si c'est un arbre Rouge et noir,Si c'est un arbre Rouge et noir,Insérez la paire de clés directement dans l'arbre,Sinon, tournez⑤

⑤.Traverséetable[i],Déterminer si la longueur de la liste est supérieure à8,Plus grand que8Convertit la liste en arbre Rouge et noir,Insérer dans l'arbre Rouge et noir,Sinon, insérez la liste liée;Si vous trouvezkeyUne dérogation directe existe déjàvalueC'est tout.

⑥.Après insertion réussie,Déterminer le nombre réel de paires de valeurs cléssizeSi la capacité maximale est dépasséethreshold,Si plus de,Mise en œuvreresize()Expansion de la capacité

 public V put(K key, V value) {
        // C'est exact.keyDehashCode()Fais - le.hash
        return putVal(hash(key), key, value, false, true);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // Étapes① tabSi vide, appelezresize()Initialisation de la création
        if ((tab = table) == null || (n = tab.length) == 0)         
            n = (tab = resize()).length;
        // Étapes② Calculindex,Et oui.nullOn s'en occupe.  
        //tab[i = (n - 1) & hashPremier noeud correspondant à l'indice   
        if ((p = tab[i = (n - 1) & hash]) == null)
            // Sans conflit de hachage,Oui.valueDirectement encapsulé commeNodeEt assigner une valeur
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // Étapes③ NodekeyMême chose.,écraser directement le noeud
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // Étapes④ Jugez que la chaîne est rouge et noir    
            else if (p instanceof TreeNode)
                 // pC'est un arbre Rouge et noir,AppeléputTreeValMéthode d'affectation
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // Étapes⑤ pType d'arbre non Rouge et noir,La chaîne est une liste de liens    
            else {
                // index Dans le même cas
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        // SipDenextVide,Va faire un nouveauvalueLa valeur est ajoutée après la liste des liens
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            // Si la longueur de la liste est supérieure à8,La liste des liens est convertie en arbre Rouge et noir,Effectuer l'insertion
                            treeifyBin(tab, hash);
                        break;
                    }
                    // keyLa même chose sort de la boucle
                    if (e.hash == hash &&  ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //Est de déplacer le pointeur pour continuer à récupérer p.next

                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //Choisir d'écraser ou non selon les règlesvalue
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // Étapes⑥:Capacité maximale dépassée,Juste agrandir
        if (++size > threshold)
            // sizePlus grand que le facteur de charge,Expansion de la capacité
            resize();
        afterNodeInsertion(evict);
        return null;
    }

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.

.Dans le constructeur, tout au plus, c'est juste régléinitialCapacity、loadFactorValeur de,Pas d'initialisationtable,tableLe travail d'initialisation pourputDans la méthode.

4.6 resize
Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Java_15
 

Expansion de la capacité(resize)Est de recalculer la capacité,VersHashMapAjout continu d'éléments à l'objet,Lorsque le tableau interne ne peut pas charger plus d'éléments,Il faut agrandir le tableau.
Bien sûr.JavaLe tableau ne s'agrandit pas automatiquement,La méthode consiste à utiliser un nouveau tableau au lieu d'un tableau existant de petite capacité

   /**
     * Cette fonction a2Utilisation des semences:1.Initialisation de la table de hachage 2.La capacité actuelle du tableau est trop petite,Besoin d'expansion
     */
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;

        // Pour la situation2:Si la capacité du tableau avant l'expansion dépasse le maximum,Ne pas étendre
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // Pour la situation2:Si la valeur maximale n'est pas dépassée,Il s'est étendu à l'original2X
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //newCapSet tooldCapDe2Et inférieur àMAXIMUM_CAPACITY,Et supérieur à la valeur par défaut, NouveauthresholdAjouté à l'original2X
                newThr = oldThr << 1; // double threshold
        }

        // Pour la situation1:Initialisation de la table de hachage(Adopter la désignation or Par défaut)
        else if (oldThr > 0) // initial capacity was placed in threshold
            // threshold>0, Oui.thresholdSet tonewCap,C'est pour ça quetableSizeForGarantie de méthodethreshold- Oui.2Puissance de
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // Initialisation par défaut
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }

        // Calculer le nouveauresizeLimite supérieure
        if (newThr == 0) {
            // newThrPour0,newThr = newCap * 0.75
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            // Créer un nouveautableTableau
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // oldTab Copier vers newTab
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                       // La liste n'a qu'un seul noeud,Affectation directe
                       //Pourquoi est - ce queHashEt alors??Parce qu'après l'élargissement,HashLes règles de.
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // ePour le cas des arbres rouges et noirs
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve orderPoids optimisé de la listehashBloc de code pour
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // L'original
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // L'original + oldCap
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // Le câble d'origine estbucket- Oui.
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // L'original+oldCapMets - le.bucket- Oui.
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }


     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.
  • 94.
  • 95.
  • 96.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source_16

4.7 removeMéthodes

remove(key) Méthodes Et remove(key, value) Les méthodes sont toutes appeléesremoveNodePour supprimer un élément

 final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // index L'élément n'a qu'un seul élément
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    // indexIl y a un arbre Rouge et noir
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // indexIl y a une liste de liens,Traverser la liste des liens renvoienode
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // Supprimer les noeuds dans différents scénarios
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }


     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
4.8 get
/**
   * Prototype de fonction
   * Action:Selon la clékey,VersHashMapObtenir la valeur correspondante
   */ 
   map.get(key);

 /**
   * Analyse des sources
   */ 
   public V get(Object key) {
    Node<K,V> e;
    // 1\. Calculer les données à obtenirhashValeur
    // 2\. AdoptiongetNode()Obtenir les données demandées ->>Analyse1
    // 3\. Après avoir obtenu,Déterminer si les données sont vides
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
   * Analyse1:getNode(hash(key), key))
   */ 
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // 1\. Les calculs sont stockés dans un tableautablePosition in
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 4\. Avec cette fonction,Dans le tableau、Arbre Rouge et noir、Trouver dans la liste des liens(Adoptionequals()Jugement)
        // a. Cherchez d'abord dans le tableau,S'il existe,Retour direct
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        // b. Si ce n'est pas dans le tableau,Cherchez dans les arbres rouges et noirs
        if ((e = first.next) != null) {
            // Dans l'arbreget
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // c. S'il n'y en a pas dans les arbres rouges et noirs,En traversant,Cherchez dans la liste des liens
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.

InJDK1.7Et dans les versions précédentes,HashMapIl n'y a pas d'implémentation d'arbre Rouge et noir,InJDK1.8Un arbre Rouge et noir a été ajouté pour empêcher les attaques de collision de table de hachage,Lorsque la longueur de la chaîne est8Heure,À temps pour se transformer en arbre Rouge et noir,AméliorationmapEfficacité

Si l'enregistrement dans un seau est trop grand(Actuellement, c'estTREEIFY_THRESHOLD = 8),HashMapVa utiliser dynamiquement untreemapImplémenter pour le remplacer.Ce serait mieux de le faire,- Oui.O(logn),Et pas malO(n).Comment ça marche?

Ceux qui sont en conflitKEYLes enregistrements correspondants sont simplement ajoutés à une liste liée,Ces enregistrements ne peuvent être trouvés que par traversée.Mais après avoir dépassé ce seuilHashMapCommencez à mettre à jour la liste en un arbre binaire,Utilisez la valeur de hachage comme variable de branche pour l'arbre,Si les deux valeurs de hachage ne sont pas égales,Mais si vous pointez vers le même seau,Le plus grand sera inséré dans le Sous - arbre droit.Si les valeurs de hachage sont égales,HashMapL'espoirkeyLes valeurs sont mieux réaliséesComparableInterface,Pour qu'il puisse être inséré dans l'ordre.Voilà.HashMapDekeyCe n'est pas nécessaire.,Mais si c'est fait, c'est mieux.Si cette interface n'est pas implémentée,En cas de grave collision de hachage,Vous ne pouvez pas vous attendre à une amélioration des performances.

À quoi sert cette amélioration des performances?Comme un programme malveillant,S'il sait qu'on utilise un algorithme de hachage,Il peut envoyer un grand nombre de demandes,Cause de graves collisions de hachage.Et j'ai continué à y accéderkeyPeut affecter considérablement les performances du serveur,Cela crée une attaque de déni de service(DoS).JDK 8DeO(n)ÀO(logn)Un bond en avant,Peut efficacement prévenir des attaques similaires,Et en même tempsHashMapLa prévisibilité des performances s'est légèrement améliorée

/**
   * Analyse des sources:resize(2 * table.length)
   * Action:Lorsque la capacité est insuffisante(Capacité > Seuil),Pour augmenter la capacité(Étendre à2X)
   */ 
   void resize(int newCapacity) {  

    // 1\. Enregistrer l'ancien tableau(old table) 
    Entry[] oldTable = table;  

    // 2\. Enregistrer l'ancienne capacité(old capacity ),C'est - à - dire la longueur du tableau
    int oldCapacity = oldTable.length; 

    // 3\. Si l'ancienne capacité est déjà la capacité maximale par défaut du système,Alors définissez le seuil au maximum de l'entier,Sortie    
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;  
        return;  
    }  

    // 4\. Selon la nouvelle capacité(2Double capacité)Nouveau1Tableaux,Nouveautable  
    Entry[] newTable = new Entry[newCapacity];  

    // 5\. (Analyse des priorités)Mettre les données sur l'ancien tableau(Paire de clés)Transfert au nouveautableMoyenne,Pour compléter l'expansion ->>Analyse1.1 
    transfer(newTable); 

    // 6\. Nouveau tableautableRéférence àHashMapDetablePropriétés
    table = newTable;  

    // 7\. Réinitialiser le seuil  
    threshold = (int)(newCapacity * loadFactor); 
} 

 /**
   * Analyse1.1:transfer(newTable); 
   * Action:Mettre les données sur l'ancien tableau(Paire de clés)Transfert au nouveautableMoyenne,Pour compléter l'expansion
   * Processus:Traverser la liste de liens dans l'ordre positif de l'ancienne liste de liens、Insérer à tour de rôle dans la tête de la nouvelle liste
   */ 
void transfer(Entry[] newTable) {
      // 1\. srcRéférence à l'ancien tableau
      Entry[] src = table; 

      // 2\. Obtenir la taille du nouveau tableau = Obtenir une nouvelle taille de capacité                 
      int newCapacity = newTable.length;

      // 3\. En traversant Ancien tableau,Mettre les données sur l'ancien tableau(Paire de clés)Passer au nouveau tableau
      for (int j = 0; j < src.length; j++) { 
          // 3.1 Obtenir chaque élément de l'ancien tableau  
          Entry<K,V> e = src[j];           
          if (e != null) {
              // 3.2 Libérer les références d'objets de l'ancien tableau(forAprès le cycle,L'ancien tableau ne fait plus référence à un objet)
              src[j] = null; 

              do { 
                  // 3.3 Traversée Avec cet élément de tableau en tête Liste des liens
                  // Note::Lors du transfert de la liste de liens,Parce que c'est une liste à chaîne unique,C'est pourquoi1Noeuds,Sinon, la liste sera déconnectée après le transfert
                  Entry<K,V> next = e.next; 
                 // 3.3 Recalculer l'emplacement de stockage de chaque élément
                 int i = indexFor(e.hash, newCapacity); 
                 // 3.4 Placer l'élément sur le tableau:En utilisant la méthode d'insertion de la tête de table à chaîne unique = Stocker les données sur l'en - tête de la liste = Placez les données originales de l'emplacement du tableau derrière1Pointeurs、Placer les données à placer dans l'emplacement du tableau
                 // C'est - à - dire: Après expansion,L'ordre inverse peut se produire:Traverser la liste de liens dans l'ordre positif de l'ancienne liste de liens、Insérer à tour de rôle dans la tête de la nouvelle liste
                 e.next = newTable[i]; 
                 newTable[i] = e;  
                 // Visite1- Oui.EntryLes éléments de la chaîne,Comme ça.,Jusqu'à ce que tous les noeuds de la liste aient été traversés
                 e = next;             
             } while (e != null);
             // Comme ça.,Jusqu'à ce que vous ayez traversé tous les éléments de données du tableau
         }
     }
 }

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.

D'après ce qui précède:En expansionresize()En cours,Données sur l'ancien tableau Transfert à Sur un nouveau tableau,Opération de transfert de données = Traverser la liste de liens dans l'ordre positif de l'ancienne liste de liens、Insérer à tour de rôle dans la tête de la nouvelle liste,C'est - à - dire le transfert de données、Après expansion,Il est facile d'avoir une liste en ordre inverse

Régler pour ne pas changer après le recalcul de l'emplacement de stockage,C'est - à - dire avant l'expansion = 1->2->3,Après expansion = 3->2->1

À ce stade, si l'exécution simultanée put Fonctionnement,En cas d'expansion,Et Facile à voir Liste des anneaux,Pour obtenir des données、En traversant la liste Formation d'un cycle mort(Infinite Loop),C'est une impasse

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Programmeur_17

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_18
Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_19
Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_20
 
4.9 getOrDefault

getOrDefault() Méthode pour obtenir la désignation key La réponse value,Si vous ne trouvez pas key ,Renvoie la valeur par défaut définie.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Java_21
 
5 Un seul filrehash

Dans le cas d'un seul thread,rehashAucun problème.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Programmeur_22
 
6 Multithreading simultanérehash

Supposons ici que deux Threads exécutent simultanémentputL'opération a déclenchérehash,Mise en œuvretransferMéthodes,Et supposons qu'une fois le thread entrétransferMéthode et exécution terminéenext = e.nextAprès,Parce que le thread Schedule n'a plus de temps alloué“Pause”,Le thread 2 est terminétransferExécution de la méthode.L'état actuel est le suivant.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Code source_23
 

Puis le fil1Réveillée,Poursuivre le reste du premier cycle

e.next = newTable[1] = null
newTable[1] = e = key(5)
e = next = key(9)

     
  • 1.
  • 2.
  • 3.

Les résultats sont présentés ci - dessous.

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_HashMap_24
 

Puis le prochain cycle,Le diagramme d'état des résultats est le suivant

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_25

Continuez le prochain cycle,Le diagramme d'état des résultats est le suivant

Absolument.!C'est le plus détaillé que j'ai jamais vu.HashMapAnalyse du code source!_Architecture_26
 

La liste des boucles se forme,Etkey(11)Impossible de rejoindre le thread1Un nouveau tableau de.Une boucle morte se produit la prochaine fois que vous accédez à la liste liée.

7 Fast-fail Cause de l'accident

Lors de l'utilisation d'un Itérateur, siHashMapModifié,AlorsConcurrentModificationExceptionSera jeté,C'est - à - direFast-failStratégie.

QuandHashMapDeiterator()Quand la méthode est appelée,Va construire et retourner un nouveauEntryIteratorObjet,Et vaEntryIteratorDeexpectedModCountSet toHashMapDemodCount(Cette variable enregistreHashMapNombre de modifications).

HashIterator() {
  expectedModCount = modCount;
  if (size > 0) { // advance to first entry
  Entry[] t = table;
  while (index < t.length && (next = t[index++]) == null)
    ;
  }
}

     
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.

En passant parIteratorDenextMéthode d'accès suivantEntryHeure,Il va d'abord vérifier sonexpectedModCountAvecHashMapDemodCountégal ou non,Si ce n'est pas égal,DescriptionHashMapModifié,Lancer directementConcurrentModificationException.LeIteratorDeremoveLa méthode fera un examen similaire.L'exception est lancée pour avertir l'utilisateur d'un problème de sécurité de fil tôt.

Solutions de sécurité pour les fils

Avec un seul thread,Pour éviterConcurrentModificationException,Il faut s'assurer que seuls lesHashMapEn soi ou seulement parIteratorPour modifier les données,Ça ne peut pas êtreIteratorUtiliser avant la fin de l'utilisationHashMapModifier les données par sa propre méthode.Parce que passerIteratorLors de la suppression des données,HashMapDemodCountEtIteratorDeexpectedModCountÇa va augmenter.,Sans préjudice de l'égalité des deux.S'il s'agit d'ajouter des données,Uniquement parHashMapLa méthode elle - même est terminée,Si vous voulez continuer à traverser les données à ce stade,Besoin de rappeleriterator()Pour reconstruire un nouveauIterator,Pour créer un nouveauIteratorDeexpectedModCountAvec mise à jourHashMapDemodCountÉquivalence.

Dans des conditions multithreadées,Disponible enCollections.synchronizedMapLa méthode construit une synchronisationMap,Ou directement en utilisant thread SafeConcurrentHashMap.

版权声明
本文为[JavaCheng...PréfaceMembres]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/09/20210914165729767p.html

Scroll to Top