编程知识 cdmana.com

Entretien d'entretien d'usine Java post sprint de 100 jours - accumulation de jours et de mois, trois questions par jour [jour 12, fonction de principe de Zookeeper

//LinkedHashMapClasse de noeuds pour

static class Entry<K,V> extends HashMap.Node<K,V> {

Entry<K,V> before, after;

Entry(int hash, K key, V value, Node<K,V> next) {

super(hash, key, value, next);

}

}

Exemple de code:

public static void main(String[] args) {

Map<String, String> linkedMap = new LinkedHashMap<String, String>();

linkedMap.put(“1”, “Profitez - en.”);

linkedMap.put(“2”, “Pas assez.”);

linkedMap.put(“3”, “Une perte.”);

linkedMap.put(“4”, “C'est dur.”);

for(linkedMap.Entry<String,String> item: linkedMap.entrySet()){

System.out.println(item.getKey() + “:” + item.getValue());

}

}

Résultats obtenus:

1:Profitez - en.

2:Pas assez.

3:Une perte.

4:C'est dur.

Demande.2:C'est...TreeMapComment réaliser l'ordre?

TreeMapOui.KeyOrdre naturelOuCompratorTrier dans l'ordre,L'intérieur est réalisé par l'arbre Rouge et noir.

  1. TreeMapC'est fait.SortedMapInterface,C'est unkeyOrdreMapCatégorie.

  2. OukeyMise en œuvre de la classe à laquelle appartientComparableInterface,Ou personnaliser une implémentationComparatorComparateur d'interface,Transmis àTreeMapPourkeyComparaison.

TreeMap<String, String> map = new TreeMap<String, String>(new Comparator() {

@Override

public int compare(String o1, String o2) {

return o2.compareTo(o1);

}

});


Demande.3:putComment le principe de la méthode a - t - il été réalisé?

Cette question est tirée de Le blog d'Angela(https://blog.csdn.net/zhengwangzw/article/details/104889549)

Insérer la description de l'image ici

  1. Déterminer si le tableau est vide,Initialisation vide;

  2. Pas vide,Calcul k De hash Valeur,Adoption(n - 1) & hashCalculer les indices qui doivent être stockés dans le tableau index;

  3. Voir table[index] Existe - t - il des données?,Construire sans donnéesNodeLes noeuds sont stockés dans table[index] Moyenne;

  4. Données existantes,Ça veut dire que c'est arrivé.hashConflit(Il y a deux noeudskeyDehashMême valeur), Continue de juger.keyégal ou non,Équivalence,Avec un nouveauvalueRemplacer les données originales(onlyIfAbsentPourfalse);

  5. Si ce n'est pas égal,Déterminer si le type de noeud actuel est un noeud arborescent,Si un noeud arborescent,Créer un noeud arborescent à insérer dans l'arbre Rouge et noir;(Si le noeud actuel est un noeud arborescent, il prouve qu'il est déjà un arbre Rouge et noir.)

  6. Si ce n'est pas un noeud arborescent,Créer unNodeAjouter à la liste des liens;Déterminer si la longueur de la liste est supérieure à 8Et la longueur du tableau est supérieure à64, Conversion de la liste liée en arbre Rouge et noir si elle est supérieure à;

  7. Déterminer si le nombre actuel de noeuds est supérieur au seuil après l'insertion,Si elle est supérieure au double de la capacité initiale du tableau.


Regardons le contenu du code source:

/**

  • Les paramètres seront spécifiéskeyEt spécifier les paramètresvalueInsérermapMoyenne,SikeyExiste déjà,Alors remplacez - le.keyCorrespondantvalue

  • @param key Désignationkey

  • @param value Désignationvalue

  • @return SivalueRemplacé,Renvoie l'ancienvalue,Sinon, retournez ànull.Bien sûr.,C'est possible.keyCorrespondantvalueC'estnull.

*/

public V put(K key, V value) {

//putValLa mise en œuvre de la méthode est la suivante:

return putVal(hash(key), key, value, false, true);

}

Comme vous pouvez le voir à partir du code source,put(K key, V value)Peut être divisé en trois étapes:

  1. Adoptionhash(Object key)Calcul méthodologiquekeyValeur de hachage pour.

  2. AdoptionputVal(hash(key), key, value, false, true)Fonction de réalisation de la méthode.

  3. RetourputValRésultats retournés par la méthode.

Alors regarde.putValComment le code source de la méthode est - il mis en œuvre??

/**

  • Map.putEt d'autres méthodes connexes

  • @param hash Spécifier les paramètreskeyValeur de hachage pour

  • @param key Spécifier les paramètreskey

  • @param value Spécifier les paramètresvalue

  • @param onlyIfAbsent Si ouitrue,Même si vous spécifiez un paramètrekeyInmapExiste déjà,Pas de remplacement non plus.value

  • @param evict Si ouifalse,TableautableEn mode création

  • @return SivalueRemplacé,Renvoie l'ancienvalue,Sinon, retournez ànull.Bien sûr.,C'est possible.keyCorrespondantvalueC'estnull.

*/

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

//Si la table de hachage est vide,Appelezresize()Créer une table de hachage,Et utiliser des variablesnEnregistrer la longueur de la table de hachage

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

//Si vous spécifiez un paramètrehashIl n'y a pas de seau correspondant dans le tableau,Il n'y a pas de collision.

if ((p = tab[i = (n - 1) & hash]) == null)

//Insérer des paires de valeurs clés directement dansmapJuste au milieu

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

//En cas de collision,Et le premier noeud dans le seau correspond

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

//Enregistrer le premier noeud dans le seau

e = p;

//Si le premier noeud du seau ne correspond pas,Et il y a une structure d'arbre Rouge et noir dans le seau,La méthode correspondante de l'arbre Rouge et noir est appelée pour insérer une paire de valeurs clés

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//Pas une structure d'arbre Rouge et noir,C'est une chaîne.

else {

//Traverser la structure de la chaîne

for (int binCount = 0

《Grandes usines de première ligneJavaAnalyse des questions d'entrevue+Notes d'apprentissage pour le développement de l'arrière - plan+La dernière vidéo d'architecture+Document d'information sur le code source du projet en direct》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 Partage open source du contenu complet

; ; ++binCount) {

//Si vous arrivez à la fin de la Liste

if ((e = p.next) == null) {

//Insérer une paire de valeurs clés à la fin de la Liste

p.next = newNode(hash, key, value, null);

//Si la longueur de la chaîne est supérieure àTREEIFY_THRESHOLDCe seuil,Pour transformer la chaîne en arbre Rouge et noir

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

treeifyBin(tab, hash);

//Sortir de la boucle

break;

}

//Si un duplicata est trouvékey,Identifier les noeuds dans la liste des lienskeyValeur par rapport à l'élément insérékeyLes valeurs sont - elles égales?,Si égal,Sortir de la boucle

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

//Pour traverser une liste liée dans un seau,Avec lee = p.nextCombinaison,Peut traverser la liste liée

p = e;

}

}

//SikeyLe noeud cartographié n'est pasnull

if (e != null) { // existing mapping for key

//Noeud d'enregistrementvlaue

V oldValue = e.value;

//SionlyIfAbsentPourfalse,OuoldValuePournull

if (!onlyIfAbsent || oldValue == null)

//Remplacervalue

e.value = value;

//Rappel après accès

afterNodeAccess(e);

// Renvoie l'ancienne valeur du noeud

return oldValue;

}

}

// Nombre de modifications structurelles +1

++modCount;

//Déterminer si l'expansion est nécessaire

if (++size > threshold)

resize();

//Insérer un rappel arrière

afterNodeInsertion(evict);

return null;

}

Demande.4:HashMapPrincipe du mécanisme d'expansion

  • capacity C'est - à - dire:Capacité,Par défaut16.
  • loadFactor Facteur de charge,Par défaut0.75
  • threshold Seuil.Seuil=Capacité*Facteur de charge.Par défaut12.L'expansion est déclenchée lorsque le nombre d'éléments dépasse le seuil.
  • En général,L'expansion est déclenchée lorsque le nombre d'éléments dépasse le seuil(Appelezresize()Méthodes).

  • La capacité de chaque expansion est la capacité précédente2X.

  • Après l'extensionNodeL'emplacement de l'objet est soit à l'emplacement d'origine,Ou se déplacer à deux fois le décalage initial.

Ici, nous prenonsJDK1.8 Par exemple, l'expansion de :

HashMap Les changements de capacité sont généralement les suivants :

  1. Constructeur d'arguments nuls:InstantanéHashMapLe tableau interne par défaut estnull,C'est - à - dire qu'il n'y a pas d'Instanciation.Premier appelputLa méthode,La première extension d'initialisation commence,La longueur est16.

  2. Constructeur paramétrique:Pour spécifier la capacité.Au moins la capacité spécifiée sera trouvée à partir de l'entier positif spécifié2Puissance de,Assigner ce nombre au seuil(threshold).Premier appelputLa méthode,Le seuil est attribué à la capacité,Et laissez Seuil = Capacité x Facteur de charge .(Ce n'est donc pas parce que nous avons spécifié manuellement la capacité que l'expansion ne sera pas déclenchée,La même capacité s'agrandit lorsque le seuil est dépassé!!)

  3. Si ce n'est pas la première expansion,La capacité devient la capacité originale2X,Le seuil devient aussi le même2X.(La capacité et le seuil deviennent les mêmes2Times,Facteur de charge0.75Sans changement)

En outre, il y a quelques points à noter :

  • Pour la première foisputHeure,L'expansion sera déclenchée en premier(C'est une initialisation.),Et ensuite stocker les données,Et déterminer si une expansion est nécessaire;Visible La première expansion peut être appelée deux fois resize()Méthodes.

  • Ce n'est pas la première fois.put,Ne plus initialiser,Stockage direct des données,Et déterminer si une expansion est nécessaire;

Lors de l'expansion de la capacité, Pour agrandir l'espace ,Pour fairehash Le hachage est réparti uniformément , L'emplacement des éléments partiels d'origine peut être déplacé .

JDK7 Migration des éléments de

JDK7Moyenne,HashMap Les données internes sont stockées dans des listes liées . La logique est donc relativement simple : Après avoir préparé un nouveau tableau ,map Parcourra chaque “Seau”, Puis traversez chaque Entity, Recalculez - le hashValeur( Il est possible aussi de ne pas calculer ), Trouver la position correspondante dans le nouveau tableau , Insérer une nouvelle liste de liens par tête .

  • Voici quelques points d'attention:

Voulez - vous recalculer hash Les conditions de valeur ne sont pas discutées en détail ici , Le lecteur peut consulter le code source lui - même .

Parce que c'est un coup de tête, Ainsi, l'emplacement des éléments de l'ancienne et de la nouvelle liste de liens peut être déplacé .

Il est possible de déclencher une boucle morte dans un scénario multithreadé pendant la migration des éléments ( Inversion infinie de la liste de liens ).

JDK1.8 Migration des éléments de

JDK1.8 Grâce à un design ingénieux , Les performances ont été grandement améliorées : Parce que la capacité du tableau est 2 Expansion de la puissance ,Et celui - là?EntityLors de l'expansion de la capacité, Nouvelle position ou ancienne position , Soit sur la longueur d'origine + Emplacement d'origine . La raison en est la suivante :

Insérer la description de l'image ici

La longueur du tableau devient originale 2X, En binaire, il y a un chiffre supérieur pour participer à la détermination de l'indice du tableau .En ce moment,Un élément passe parhash Après le calcul de la méthode de conversion des coordonnées , Il se trouve qu'il y a un phénomène :La position la plus élevée est0 Alors les coordonnées ne changent pas ,La position la plus élevée est1 Les coordonnées deviennent “10000+ Coordonnées originales ”,C'est - à - dire:“Longueur initiale+ Coordonnées originales ”.Comme le montre la figure ci - dessous::

Insérer la description de l'image ici

Donc,,Lors de l'expansion de la capacité, Il n'est pas nécessaire de recalculer l'élément hashC'est, Il suffit de juger que la position la plus élevée est 1Toujours0C'est bon..

JDK8DeHashMap Les détails suivants sont également à noter :

  • JDK8 Est dans l'ordre positif lors de la migration des éléments , Il n'y aura pas de transposition de la liste liée .

  • Si l'élément d'un seau dépasse 8- Oui., Convertit la liste en arbre Rouge et noir , Accélérer l'efficacité de la recherche de données .

Demande.5:HashMapInJDK1.8Quelles optimisations ont été faites?

| C'est différent. | JDK 1.7 | JDK 1.8 |

| — | — | — |

| Structure de stockage | Tableau + Liste des liens | Tableau + Liste des liens + Arbre Rouge et noir |

| Méthode d'initialisation | Fonction individuelle:inflateTable() | Directement intégré dans la fonction d'expansionresize()Moyenne |

| hashMéthode de calcul de la valeur | Traitement des perturbations = 9Perturbation secondaire = 4Opérations secondaires + 5Opération d'exclusion secondaire | Traitement des perturbations = 2Perturbation secondaire = 1Opérations secondaires + 1Opération d'exclusion secondaire |

| Règles de stockage des données | Sans conflit,Tableau de stockage;En cas de conflit,Liste des chaînes de stockage | Sans conflit,Tableau de stockage;Conflit & Longueur de la liste < 8:Liste des chaînes de stockage;Conflit & Longueur de la liste > 8:Arbres et stockage des arbres rouges et noirs |

| Insérer les données par | Tête insérée(Les données de l'emplacement d'origine sont transférées à1Bits,Insérer les données à cet endroit) | Insertion de la queue(Insérer directement à la fin de la Liste/Arbre Rouge et noir) |

| Méthode de calcul de la position de stockage après expansion de la capacité | Tous calculés selon la méthode originale(C'est - à - dire:hashCode ->> Fonction de perturbation ->> (h&length-1)) | Calculé selon la loi après expansion de la capacité(C'est - à - dire la position agrandie=Emplacement d'origine or Emplacement d'origine + Ancienne capacité) |

  1. Tableau+Liste des liensC'est changé.Tableau+Liste liée ou arbre Rouge et noir;

PréventionhashConflit, La longueur de la liste est trop longue ,Oui.Complexité temporelle parO(n)Réduit àO(logn);

  1. La méthode d'insertion de la liste de liens a été changée de la méthode d'insertion de début à la méthode d'insertion de fin , C'est juste qu'au moment de l'insertion , S'il y a déjà un élément à l'emplacement du tableau ,1.7 Placer le nouvel élément dans le tableau , Insérer un nouveau noeud dans l'en - tête de la liste , Le noeud original recule ;EtJDK1.8Traverse la Liste, Placer l'élément à la fin de la liste ;

Parce que1.7 Lors de l'expansion de la tête , L'insertion de la tête peut entraîner l'inversion de la liste liée , Les anneaux sont générés dans un environnement multithreadé (Cycle mort);

Insérer la description de l'image ici

Ce processus est ,D'abord.ACopier dans le nouveauhashDans le tableau, Et ensuite copier B Au bout de la chaîne (AAvant:B.next=A),À l'origine.B.next=null, C'est la fin ( Un processus comme le thread 21 ),Mais, En raison de l'expansion du thread II ,Oui.B.next=A,Alors..., Continuez à copier ici A,JeanA.next=B,Par conséquent,, La liste des anneaux apparaît :B.next=A; A.next=B

L'utilisation de la prise de tête modifie l'ordre sur la liste liée , Mais si vous utilisez la queue , L'ordre original des éléments de la liste liée est maintenu lors de l'expansion ,Il n'y aurait pas de problème avec la liste liée en boucle.

Ça veut dire que c'était A->B, Après l'expansion de la capacité, la liste est toujours A->B.

  1. Lors de l'expansion1.7 Les éléments du tableau original doivent être refaits hash Localiser le nouveau tableau ,1.8 Adopter une logique de jugement plus simple , Sans changement de position ou d'index + Taille de l'ancienne capacité ;

  2. Lors de l'insertion,1.7Déterminer d'abord si l'expansion est nécessaire,Insérer à nouveau,1.8 Insérer d'abord , Insérer terminé pour déterminer si l'expansion est nécessaire ;

Demande.6:Liste de liens comment les arbres rouges et noirs se convertissent entre eux?Quel est le seuil??

  • ** Le seuil de conversion de la liste liée en arbre Rouge et noir est :8 **

  • ** Le seuil de la liste rouge - Noire est :6 **

Calculé,Inhash Si la fonction est bien conçue ,C'est arrivé.hashCollisions8 La deuxième chance est une partie par million 6, En termes de probabilité ,Le seuil est8Assez.; Quant à la raison pour laquelle les arbres rouges et noirs retournent à la liste liée, le seuil de condition est 6Au lieu de7Ou9?Parce que sihash Le nombre de collisions est 8Errant dans les environs, Les opérations de conversion entre les listes liées et les arbres rouges et noirs peuvent se produire fréquemment , Pour éviter cela .


Insérer la description de l'image ici

Pause,Encore une fois, montre - moi le chantier de briques de nos camarades de classe,Coordonnées:Beijing.

Auteur:Qnlko

C'est le même flotteur ,Bonne chance.~


Questions d'entrevue2:HashMapEst - ce que le fil est sécurisé?

===================================================================================

Réponse sérieuse:


Pas sans fil,Dans un environnement multithreadé,

  • JDK1.7: Il y aura un cycle de vie et de mort 、Perte de données、 Problèmes de couverture des données ;

  • JDK1.8: Il y aura des problèmes de couverture des données .

版权声明
本文为[Alibaba Open Source]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/11/20211125174908923h.html

Scroll to Top