Analysieren Sie die internen Mechanismusprinzipien gängiger Sammlungen in JAVA

Jeder ist mit häufig verwendeten Sammlungen vertraut, hat jedoch möglicherweise nur ein geringes Verständnis für die internen Prinzipien. Das Folgende wird durch das Lesen des Quellcodes verstanden.

ArrayListe

In ArrayList befindet sich ein dynamischer Objekt-Array-Container mit einer Standardgröße von 10. Immer wenn neue Daten hinzugefügt werden und diese größer als die ursprüngliche Containergröße sind, wird die Containergröße durch Arrays erhöht .copyOf auf das 1,5-fache des Originals usw. Wenn die Datengröße vorhergesagt werden kann, kann die Größe der dynamischen Daten standardmäßig festgelegt werden, um den durch die Erweiterung verursachten Ressourcenverbrauch zu reduzieren:

get() – Den Index direkt lesen – O(1)

add(E) – Direkt am Ende hinzufügen – O(1)

add(idnex, E) – Nach dem Einfügen von Daten müssen Sie die folgenden Daten verschieben – O(n)

remove(index) – Nach dem Löschen müssen Sie verschieben – O(n)

LinkedList

LinkedList ist eine bidirektionale verknüpfte Liste. Beim Hinzufügen neuer Daten rufen Sie tatsächlich linklast auf, um Daten am Ende der verknüpften Liste einzufügen die entsprechenden Daten und ersetzen Sie die vorderen und hinteren Knoten der verknüpften Liste 🎜>Zeitliche Komplexität:

get() - muss durchlaufen werden - O(n)

add(E) - Aufruf linklast direkt am Ende hinzufügen - O(1)

add(index, E) - Sie müssen zuerst die Daten an der ursprünglichen Indexposition finden und dann die Daten vor und nach der Verknüpfung erneut angeben list – O(n)

remove() – RemoveLast direkt aufrufen, um die letzten Daten zu löschen – O(1 )

remove(index) – Sie müssen die Daten am ursprünglichen Index finden Position zuerst - O(n)

Hash

Map
HashMap ist eigentlich ein Array im Inneren, und Jedes Array ist eine einseitig verknüpfte Liste. Das Array in HashMap enthält die folgenden Attribute: (key, value, next). . Nach Erhalt des Arrays hat die HashMap auch einen Ladefaktor (Standard 0,75), wenn das Array zu 75 % gefüllt ist. Dann stellt sich die Frage, ob die Werte von hash(key)%len sind gleich beim Put, wird es da keinen Konflikt geben? Die Verarbeitungsmethode von HashMap ist: Es gibt ursprünglich einen Eintrag [0] = A, und dann kommt ein B mit einem Index von 0, dann ist Eintrag [0] = B, B.next = A, und wenn ein weiteres C kommt, dann Setzt Entry[0] = C, C.next = B usw. Auf diese Weise bildet Entry eine verknüpfte Liste. Beim Abrufen wird die verknüpfte Liste durchlaufen, um den Wert zu erhalten. Was hier erwähnt werden muss, ist, dass bei Verwendung von hashMap das eingeführte Schlüsselobjekt die beiden Funktionen

von hashCode() und equal() neu schreiben muss. Der Grund kann auf die Quelle verwiesen werden Code-Beurteilungsbedingung (if (e.hash == hash && ((k = e.key) == key || key.equals(k)))), wenn hashCode() nicht neu geschrieben wird, kann das entsprechende Array nicht gefunden werden Wenn equal( ) überhaupt nicht neu geschrieben wird, kann nicht festgestellt werden, ob die Inhalte der Schlüsselwerte gleich sind.

Ergänzung:

Hashmap wurde nach Java8 optimiert: Da die Abfrage

einer einseitig verknüpften Liste eine zeitliche Komplexität von O( n) In extremen Fällen kann es zu Leistungsproblemen kommen. Daher verwendet Java8 einen Rot-Schwarz-Baum mit einer Zeitkomplexität von O (log n) für die Speicherung, um die Effizienz von Speicherabfragen zu verbessern, wenn die Länge der verknüpften Liste größer ist als 8.

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;  
}

LinkedHashMap

Die Kombination aus der internen doppelt verknüpften Liste und der HashMap von LinkedHashMap unterstützt mehrere Iterationsreihenfolgen. Die Standardeinstellung ist die Einfügereihenfolge und kann auch die Zugriffsreihenfolge sein.

Zugriffsreihenfolge (accessOrder=true): Elemente, auf die durch den Aufruf von get zugegriffen wird, werden am Ende der Kette platziert und die Iteration beginnt am Anfang der Kette

Einfügungsreihenfolge (accessOrder= false): Iterieren Sie in der Einfügereihenfolge. Herauskommen

TreeMap

TreeMap wird intern basierend auf rot-schwarzen Bäumen implementiert und wird durch CompareTo auf natürliche Weise nach Schlüsseltyp sortiert Standard. Die untere Ebene von TreeSet ist TreeMap.

Das obige ist der detaillierte Inhalt vonAnalysieren Sie die internen Mechanismusprinzipien gängiger Sammlungen in JAVA. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!