Analyser les principes du mécanisme interne des collections communes en JAVA

Tout le monde connaît les collections couramment utilisées, mais il se peut qu'ils n'aient qu'une petite compréhension des principes internes. Ce qui suit est compris en lisant le code source.

TableauListe

À l'intérieur d'ArrayList se trouve un conteneur de tableau d'objets dynamiques avec une taille par défaut de 10. Chaque fois qu'une nouvelle donnée est ajoutée, si elle est plus grande que la taille du conteneur d'origine, la taille du conteneur sera augmentée via les tableaux. .copyOf à 1,5 fois l'original, et ainsi de suite. Lorsque la taille des données peut être prédite, la taille des données dynamiques peut être définie par défaut pour réduire la consommation de ressources causée par l'expansion

Complexité temporelle :

get() - Lire l'indice directement - O(1)

add(E) - Ajouter directement à la fin - O(1)

add(idnex, E) - Après avoir inséré les données, vous devez déplacer les données suivantes - O(n)

remove(index) - Après la suppression, vous devez déplacer - O(n)

LinkedList

LinkedList est une liste chaînée bidirectionnelle Lorsque vous ajoutez de nouvelles données, vous appelez en fait linklast pour insérer des données à la fin de la liste chaînée. Lors de la suppression, vous pouvez rechercher directement. les données correspondantes et remplacez les nœuds avant et arrière de la liste chaînée 🎜>Complexité temporelle :

get() - besoin de parcourir - O(n)

add(E) - appel. linklast à ajouter directement à la fin - O(1)

add(index, E) - Vous devez d'abord trouver les données à la position d'index d'origine, puis re-spécifier les données avant et après le lien list - O(n)

remove() - Appelez directement RemoveLast pour supprimer les dernières données - O(1 )

remove(index) - Vous devez trouver les données à l'index d'origine positionner en premier - O(n)

HashMapHashMap est en fait un tableau à l'intérieur, et chaque tableau est une liste chaînée unidirectionnelle. Le tableau dans HashMap est une classe nommée Entry, qui contient (key, value, next Les règles de stockage sont les suivantes : l'indice du tableau est obtenu par hash(key)%len). . Après avoir obtenu le tableau, le HashMap a également un facteur de charge (par défaut 0,75). Lorsque le tableau est rempli à 75%

Alors la question se pose, si les valeurs de hash(key)%len sont. égal lors du put, n'y aura-t-il pas un conflit ? La méthode de traitement de HashMap est la suivante : il y a à l'origine un Entry[0] = A, puis un B avec un index de 0 arrive, puis Entry[0] = B, B.next = A, et quand un autre C arrive, alors Will Entry[0] = C, C.next = B, et ainsi de suite. De cette façon, Entry formera une liste chaînée, et lors de la récupération, la liste chaînée sera parcourue pour obtenir la valeur.

Ce qu'il faut mentionner ici, c'est que lors de l'utilisation de hashMap, l'objet clé introduit doit réécrire les deux

fonctions

de hashCode() et equal(). condition de jugement de code (if (e.hash == hash && ((k = e.key) == key || key.equals(k)))), si hashCode() n'est pas réécrit, le tableau correspondant est introuvable Si égal( ) n'est pas réécrit, il est impossible de déterminer si le contenu des valeurs clés est égal.

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null总是放在数组的第一个链表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍历链表  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
            Object k;  
            //如果key在链表中已存在，则替换为新value  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
}

Supplément :

Hashmap a été optimisé après java8 : Puisque la

requête

d'une liste chaînée unidirectionnelle a une complexité temporelle de O( n), dans des cas extrêmes, il peut y avoir des problèmes de performances, donc si la longueur de la liste chaînée est supérieure à 8, Java8 utilisera un arbre rouge-noir avec une complexité temporelle de O(log n) pour le stockage afin d'améliorer l'efficacité de requêtes de stockage. LinkedHashMap

La combinaison de la liste interne doublement liée et du HashMap de LinkedHashMap prend en charge plusieurs ordres d'itération. La valeur par défaut est l'ordre d'insertion, et il peut également être dans l'ordre d'accès.

Ordre d'accès (accessOrder=true) : les éléments accessibles en appelant get seront placés à la fin de la chaîne, et l'itération commencera au début de la chaîne

Ordre d'insertion (accessOrder= false) : Itérer dans l'ordre d'insertion Sortir

TreeMap

TreeMap est implémenté en interne sur la base d'arbres rouge-noir et sera naturellement trié par type de clé via compareTo par défaut. Le niveau inférieur de TreeSet est TreeMap.

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!