Spickzettel für Java-Sammlungen. Ein Muss für Java-Anfänger

Überprüfen Sie in möglichst kurzer Zeit die Merkmale, Implementierungsmethoden und Leistung aller Sammlungen und gleichzeitigen Sammlungen. Es eignet sich zur Lektüre für alle, die sich nicht so sicher sind, „Java zu beherrschen“.

List

ArrayList

Als Array implementiert. Sparen Sie Platz, aber Arrays haben Kapazitätsgrenzen. Wenn das Limit überschritten wird, wird die Kapazität um 50 % erhöht und mit System.arraycopy() in ein neues Array kopiert. Daher ist es am besten, eine Schätzung der Array-Größe anzugeben. Standardmäßig wird beim ersten Einfügen eines Elements ein Array der Größe 10 erstellt.

Der Zugriff auf Elemente über den Array-Index --get(i)/set(i,e) bietet eine hohe Leistung, was den grundlegenden Vorteil von Arrays darstellt.

Die Leistung beim Hinzufügen von Elementen direkt am Ende des Arrays --add(e) ist ebenfalls hoch, aber wenn Sie Elemente durch Drücken des Indexes --add(i,e) einfügen und löschen, entfernen Sie i), entfernen(e), Sie müssen System.arraycopy() verwenden, um einige der betroffenen Elemente zu verschieben, und die Leistung wird schlechter. Dies ist ein grundlegender Nachteil.

LinkedList

wird als bidirektional verknüpfte Liste implementiert. Es gibt keine Kapazitätsbeschränkung für verknüpfte Listen, aber die doppelt verknüpfte Liste selbst benötigt mehr Platz und erfordert zusätzliche Zeigeroperationen für verknüpfte Listen.

Der Zugriff auf Elemente per Index – get(i)/set(i,e) durchläuft tragischerweise die verknüpfte Liste, um den Zeiger an die richtige Position zu bewegen (wenn i> halb so groß wie das Array ist, wird er verschoben vom Ende).

Beim Einfügen oder Löschen von Elementen können Sie nur die Zeiger des vorherigen und nächsten Knotens ändern, müssen jedoch immer noch einen Teil des Zeigers der verknüpften Liste durchlaufen, um zu der Position zu gelangen, auf die der Index zeigt. Nur Operationen Beide Enden der verknüpften Liste können hinzugefügt werden: add(), addFirst(), removeLast() oder verwenden Sie remove() auf iterator(), um die Zeigerbewegung zu speichern.

CopyOnWriteArrayList

Parallelitätsoptimierte ArrayList. Verwenden Sie die CopyOnWrite-Strategie, um zunächst einen Snapshot zu kopieren, um ihn zu ändern, und lassen Sie dann den internen Zeiger nach der Änderung auf das neue Array zeigen.

Da Änderungen am Snapshot für Lesevorgänge unsichtbar sind, gibt es nur Schreibsperren, aber keine Lesesperren. Zusätzlich zu den hohen Replikationskosten eignet es sich normalerweise für Szenarien, in denen mehr gelesen und weniger geschrieben wird . Wenn die Aktualisierungshäufigkeit hoch oder das Array groß ist, ist es besser, Collections.synchronizedList(list) zu verwenden und für alle Vorgänge dieselbe Sperre zu verwenden, um die Thread-Sicherheit zu gewährleisten.

Die Methode addIfAbsent(e) wurde hinzugefügt, die das Array durchläuft, um zu prüfen, ob das Element bereits vorhanden ist. Wie Sie sich vorstellen können, ist die Leistung nicht sehr gut.

Ergänzung

Unabhängig davon, welche Implementierung verwendet wird, erfordert die Rückgabe des Index nach Wert --contains(e), indexOf(e), remove(e) das Durchlaufen aller Elemente zum Vergleich und die Die Leistung kann man sich vorstellen. Es wird nicht so gut sein.

Es gibt keine SortedList, die nach Elementwert sortiert ist, und es gibt keine sperrenfreie ConcurrentLinkedList in der Thread-sicheren Klasse. Wenn Sie sich mit den entsprechenden Klassen in Set und Queue begnügen, fehlen Ihnen einige Listenspezifische Methoden.

Map

HashMap

Hash-Bucket-Array implementiert als Entry[]-Array. Verwenden Sie den Hash-Wert von Key, um die Größe des Bucket-Arrays zu modulieren, um den Array-Index zu erhalten.

Wenn beim Einfügen eines Elements zwei Schlüssel in denselben Bucket fallen (z. B. gehören die Hashwerte 1 und 17 beide zum ersten Hash-Bucket nach Modulo 16), verwendet Entry ein next-Attribut, um mehrere zu implementieren In einer unidirektional verknüpften Liste gespeicherte Einträge zeigen den später im Bucket eingegebenen Eintrag neben dem aktuellen Eintrag im Bucket.

Wenn Sie nach einem Schlüssel mit einem Hash-Wert von 17 suchen, suchen Sie zuerst den ersten Hash-Bucket, durchlaufen Sie dann alle Elemente im Bucket mithilfe einer verknüpften Liste und vergleichen Sie ihre Schlüsselwerte einzeln.

Wenn die Anzahl der Einträge 75 % der Anzahl der Buckets erreicht (viele Artikel sagen, dass die Anzahl der verwendeten Buckets 75 % erreicht, aber das stimmt basierend auf dem Code nicht), wird das Bucket-Array erweitert exponentiell und alle ursprünglichen Einträge werden neu zugewiesen. Daher ist es am besten, hier eine Schätzung vorzunehmen.

Es ist schneller, die bitweise Operation (Hash & (arrayLength-1)) zu verwenden, um den Modul zu ermitteln, sodass die Größe des Arrays immer 2 hoch N-te Potenz beträgt 17 wird es in 32 umgewandelt. Der Standardanfangswert beim ersten Platzieren eines Elements ist 16.

Iterator() durchläuft das Hash-Bucket-Array, das außer Betrieb zu sein scheint.

In JDK8 wird ein neuer Schwellenwert mit einem Standardwert von 8 hinzugefügt. Wenn der Eintrag in einem Bucket den Schwellenwert überschreitet, wird er nicht in einer einseitig verknüpften Liste, sondern in einem rot-schwarzen Baum gespeichert um die Schlüsselsuche zu beschleunigen.

LinkedHashMap

Erweitert HashMap um die Implementierung einer doppelt verknüpften Liste, die als die speicherintensivste Datenstruktur bekannt ist. Wenn iterator() unterstützt wird, werden die Einträge entsprechend der Einfügereihenfolge sortiert (Aktualisierungen werden jedoch nicht gezählt. Wenn das Attribut accessOrder auf true gesetzt ist, werden alle Lese- und Schreibzugriffe gezählt).

Die Implementierung besteht darin, dem Eintrag Attribut-Vorher/Nachher-Zeiger hinzuzufügen und sich beim Einfügen selbst vor dem Header-Eintrag hinzuzufügen. Wenn alle Lese- und Schreibzugriffe sortiert werden müssen, müssen die Vorher/Nachher-Einträge der vorderen und hinteren Einträge zusammengefügt werden, um sich selbst in der verknüpften Liste zu löschen.

TreeMap

Aus Platzgründen wird die Implementierung mit rot-schwarzen Bäumen durchgeführt. Weitere Informationen finden Sie im Einführungs-Tutorial. Wenn iterator() unterstützt wird, erfolgt die Sortierung nach Schlüsselwert, der in aufsteigender Reihenfolge der Schlüssel sortiert werden kann, die die Comparable-Schnittstelle implementieren, oder durch den eingehenden Comparator gesteuert werden kann. Es ist denkbar, dass die Kosten für das Einfügen/Löschen von Elementen in den Baum höher sein müssen als die von HashMap.

Unterstützt die SortedMap-Schnittstelle, z. B. firstKey(), lastKey(), um den größten und kleinsten Schlüssel zu erhalten, oder sub(fromKey, toKey), tailMap(fromKey), um ein bestimmtes Segment der Karte auszuschneiden.

ConcurrentHashMap

Die gleichzeitig optimierte HashMap verfügt standardmäßig über 16 Schreibsperren (mehr können festgelegt werden), wodurch die Wahrscheinlichkeit einer Blockierung effektiv verteilt wird und keine Lesesperren vorhanden sind.

Die Datenstruktur ist Segment[]. Innerhalb des Segments befindet sich das Hash-Bucket-Array, und jedes Segment hat eine Sperre. Der Schlüssel berechnet zunächst, in welchem ​​Segment er sich befindet, und berechnet dann, in welchem ​​Hash-Bucket er sich befindet.

Unterstützt die ConcurrentMap-Schnittstelle wie putIfAbsent(key, value) und das Gegenteil replace(key, value) und replacement(key, oldValue, newValue), das CAS implementiert.

Es gibt keine Lesesperre, da die Put-/Remove-Aktion eine atomare Aktion ist (Put ist beispielsweise eine Zuweisungsoperation für ein Array-Element/Eingabezeiger) und die Leseoperation den Zwischenstatus von nicht sieht eine Update-Aktion.

ConcurrentSkipListMap

JDK6s neue parallelitätsoptimierte SortedMap wird mit SkipList implementiert. SkipList ist eine vereinfachte Alternative zu Rot-Schwarz-Bäumen und ein beliebter Algorithmus für geordnete Mengen. Bitte lesen Sie aus Platzgründen das Einführungs-Tutorial. Das Concurrent-Paket verwendet es, weil es CAS-basierte sperrenfreie Algorithmen unterstützt, während Rot-Schwarz-Bäume keine guten sperrenfreien Algorithmen haben.

Ganz besonders, seine Größe () kann nicht zufällig angepasst werden, sondern wird für Statistiken durchlaufen.

Ergänzung

In Bezug auf null sind HashMap und LinkedHashMap willkürlich. Der Schlüssel kann nicht null sein, wenn TreeMap keinen Comparator festlegt. (Warum ist das so?) , JDK8 Weder Schlüssel noch Wert in ConcurrentSkipListMap können null sein; in ConcurrentSkipListMap können nicht alle Schlüssel und Werte in JDK null sein.

Set

Set wird fast immer intern mithilfe einer Map implementiert, da das KeySet in der Map ein Set ist und der Wert ein falscher Wert ist, wobei alle dasselbe Objekt verwenden. Die Eigenschaften von Set erben auch die der internen Map-Implementierung.

HashSet: Intern ist eine HashMap.

LinkedHashSet: Intern ist es LinkedHashMap.

TreeSet: Intern ist das SortedSet von TreeMap.

ConcurrentSkipListSet: Intern handelt es sich um ein nebenläufigkeitsoptimiertes SortedSet von ConcurrentSkipListMap.

CopyOnWriteArraySet: Intern handelt es sich um einen parallelitätsoptimierten Satz von CopyOnWriteArrayList. Die Methode addIfAbsent() wird verwendet, um die Elementdeduplizierung zu erreichen.

Ergänzung: Es scheint, dass ein ConcurrentHashSet fehlt. Es sollte intern eine einfache Implementierung von ConcurrentHashMap geben, aber JDK stellt diese nicht bereit. Jetty hat eines selbst versiegelt, und Guava verwendet direkt java.util.Collections.newSetFromMap(new ConcurrentHashMap()), um es zu implementieren.

Warteschlange

Warteschlange ist eine Liste, die an beiden Enden ein- und ausgeht, sodass sie auch mit einem Array oder einer verknüpften Liste implementiert werden kann.

　--Ordinary Queue--

　LinkedList

　Ja, LinkedList, implementiert als doppelt verknüpfte Liste, ist sowohl eine Liste als auch eine Warteschlange. Es ist die einzige Warteschlange, die das Platzieren von Nullen zulässt.

　ArrayDeque

　 Eine bidirektionale Warteschlange, die als kreisförmiges Array implementiert ist. Die Größe ist ein Vielfaches von 2, der Standardwert ist 16.

Gewöhnliche Arrays können am Ende nur schnell Elemente hinzufügen. Um FIFO zu unterstützen und Elemente schnell aus dem Kopf des Arrays zu entfernen, müssen Sie ein Schleifenarray verwenden: Es gibt zwei Indizes für den Kopf und das Ende : Beim Einfügen eines Elements wird der Index erhöht. Wenn ein Element hinzugefügt wird und das Ende des Array-Bereichs erreicht ist, wird das Element in einer Schleife dem Array [0] zugewiesen (wenn der Index des Der Index an der Spitze des Teams ist zu diesem Zeitpunkt größer als 0, was bedeutet, dass das Element an der Spitze des Teams herausgesprungen ist und eine freie Stelle vorhanden ist. Der Index zeigt auf 0 am Ende des Teams. und wenn das nächste Element eingefügt wird, wird es dem Array [1] zugewiesen und der Endindex zeigt auf 1. Wenn der Index am Ende der Warteschlange den Kopf der Warteschlange einholt, bedeutet dies, dass der gesamte Speicherplatz im Array aufgebraucht ist und das Array verdoppelt wird.

PriorityQueue

Eine Prioritätswarteschlange, die mithilfe eines binären Heaps implementiert wird. Weitere Informationen finden Sie im Einführungs-Tutorial. Es handelt sich nicht mehr um einen FIFO, sondern wird basierend auf der vom Element implementierten Comparable-Schnittstelle oder dem Vergleichsergebnis aus der Warteschlange entfernt an den Komparator übergeben: Je kleiner der Wert, desto höher die Priorität und desto höher der Wert, der aus der Warteschlange entfernt wird. Beachten Sie jedoch, dass die Rückgabe von iterator() nicht sortiert wird.

　--Thread-sichere Warteschlange--

　ConcurrentLinkedQueue/ConcurrentLinkedDeque

　Eine für unbegrenzte Parallelität optimierte Warteschlange, die auf einer verknüpften Liste basiert, implementiert einen sperrfreien Algorithmus, der auf CAS basiert.

Die Struktur von ConcurrentLinkedQueue besteht aus einer einseitig verknüpften Liste und zwei Zeigern, Kopf/Ende. Denn beim Beitritt zur Warteschlange müssen Sie den nächsten Zeiger des Schwanzelements der Warteschlange ändern und den Schwanz ändern, auf den er zeigen soll Die beiden CAS-Aktionen können nicht atomar sein, daher sind besondere Anforderungen erforderlich. Bitte lesen Sie aus Platzgründen das Einführungs-Tutorial.

　PriorityBlockingQueue

　 Unbegrenzte Parallelität optimiert PriorityQueue basiert ebenfalls auf einem binären Heap. Verwenden Sie eine öffentliche Lese-/Schreibsperre. Obwohl die BlockingQueue-Schnittstelle implementiert ist, weist sie keine blockierenden Warteschlangeneigenschaften auf. Sie wird automatisch erweitert, wenn der Speicherplatz nicht ausreicht.

DelayQueue

Enthält intern eine PriorityQueue, die ebenfalls unbegrenzt ist. Das Element muss die Delayed-Schnittstelle implementieren und bei jedem Aufruf zurückgeben, wie lange es bis zur Triggerzeit dauert. Wenn es kleiner als 0 ist, bedeutet dies, dass es Zeit zum Triggern ist.
Beim pull() wird peek() verwendet, um das Element am Kopf der Warteschlange zu überprüfen, um zu überprüfen, ob die Triggerzeit erreicht wurde. ScheduledThreadPoolExecutor verwendet eine ähnliche Struktur.

　--Thread-sichere Blockierungswarteschlange--

　 Die Warteschlangenlänge von BlockingQueue ist begrenzt, um sicherzustellen, dass die Geschwindigkeit von Produzenten und Konsumenten nicht zu weit auseinander liegt, um eine Speichererschöpfung zu vermeiden. Die Warteschlangenlänge kann nach dem Festlegen nicht mehr geändert werden. Wenn die Warteschlange beim Betreten der Warteschlange voll ist oder beim Verlassen der Warteschlange leer ist, werden die Auswirkungen verschiedener Funktionen in der folgenden Tabelle angezeigt:

Kann eine Ausnahme melden. Gibt einen booleschen Wert zurück. Kann das Warten blockieren Wartezeit kann eingestellt werden

In die Warteschlange stellen add(e) offer(e) put(e) offer(e, timeout, unit)

Entfernen entfernen() poll() take() poll( Timeout, Einheit)

View element() peek() None None

ArrayBlockingQueue

Gleichzeitig optimierte BlockingQueue mit fester Länge, basierend auf einem Schleifenarray implementiert. Es gibt eine allgemeine Lese-/Schreibsperre und zwei Bedingungen, notFull und notEmpty, um den Blockierungsstatus zu verwalten, wenn die Warteschlange voll oder leer ist.

LinkedBlockingQueue/LinkedBlockingDeque

Sie können eine lange, parallelitätsoptimierte BlockingQueue auswählen, die auf einer verknüpften Liste basiert, sodass Sie die Länge auf Integer.MAX_VALUE festlegen können. Unter Ausnutzung der Eigenschaften der verknüpften Liste werden die beiden Sperren takeLock und putLock getrennt, und notEmpty und notFull werden verwendet, um den Blockierungsstatus weiterhin zu verwalten, wenn die Warteschlange voll oder leer ist.

Ergänzung

JDK7 verfügt über eine LinkedTransferQueue. Die transfer(e)-Methode stellt sicher, dass die vom Produzenten eingefügten Elemente weggenommen und vom Verbraucher zurückgegeben werden Lerne es, wenn du Zeit hast.