Ü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 „Java beherrschen“, aber noch nicht sicher sind.
List
ArrayList
ist 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.
Zugriff auf Elemente über den Array-Index – get(i)/set(i,e) bietet eine hohe Leistung, was der grundlegende Vorteil von Arrays ist.
Die Leistung beim direkten Hinzufügen von Elementen am Ende des Arrays –add(e) ist ebenfalls hoch, aber wenn Sie Elemente durch Drücken des Indexes –add(i,e) einfügen oder löschen, entfernen Sie(i) Wenn Sie System.arraycopy () verwenden, um einige der betroffenen Elemente zu verschieben, wird die Leistung schlechter, was einen grundlegenden Nachteil darstellt.
LinkedList
ist als doppelt 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.
Zugriff auf Elemente per Index – get(i)/set(i,e) Durchläuft die verknüpfte Liste, um den Zeiger an die Position zu bewegen (wenn i > die halbe Größe des Arrays ist, wird er vom Ende verschoben ).
Beim Einfügen oder Löschen von Elementen können Sie einfach die Zeiger des vorherigen und nächsten Knotens ändern. Sie müssen jedoch immer noch einen Teil der verknüpften Liste durchlaufen, um zu der Position zu gelangen, auf die der Index zeigt beide Enden der verknüpften Liste – add(), addFirst(), removeLast() oder verwenden Sie remove() auf iterator(), um Zeigerbewegungen zu sparen.
CopyOnWriteArrayList
Parallelitätsoptimierte ArrayList. Kopieren Sie mit der CopyOnWrite-Strategie zunächst einen Snapshot, 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 nicht sichtbar sind, gibt es nur Schreibsperren und keine Lesesperren. Zusätzlich zu den hohen Replikationskosten eignet es sich normalerweise für Szenarien mit mehr Lesevorgängen und weniger Schreibvorgängen. 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 von Indizes nach Wert – enthält(e), indexOf(e), entfernen(e) das Durchlaufen aller Elemente zum Vergleich, und die Leistung ist vorstellbar 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
Ein als Entry[]-Array implementiertes Hash-Bucket-Array. Der Array-Index kann durch Modulo der Größe des Bucket-Arrays mithilfe des Hash-Werts ermittelt werden des Schlüssels.
Wenn beim Einfügen eines Elements zwei Schlüssel in denselben Bucket fallen (z. B. gehören die Hashwerte 1 und 17 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. Der später im Bucket eingegebene Eintrag zeigt 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)) für Modulo zu verwenden, sodass die Größe des Arrays immer 2 hoch N-te Potenz beträgt. Wenn Sie nach Belieben einen Anfangswert angeben, z Als 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 bidirektional 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
wird als rot-schwarzer Baum implementiert. Wenn iterator() unterstützt wird, kann es in aufsteigender Reihenfolge des Schlüssels sortiert werden, der die Comparable-Schnittstelle implementiert oder vom eingehenden Komparator gesteuert. 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
Parallelitätsoptimierte 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/Eintragszeiger) und die Leseoperation den Zwischenstatus einer Aktualisierungsaktion nicht sieht .
ConcurrentSkipListMap
JDK6s neue parallelitätsoptimierte SortedMap ist in 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.
ist etwas ganz Besonderes. Seine Größe () kann nicht zufällig angepasst werden, sondern wird für Statistiken durchlaufen.
Ergänzend
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 gleichzeitig optimierten 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.
–Gewöhnliche Warteschlange–
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 Platzieren eines Elements befindet sich der Kopf unter dem Kopf. Der Index wird erhöht. Wenn ein Element das Ende des Array-Bereichs erreicht, wird das Element zirkulär dem Array 0 zugewiesen, und der Endindex zeigt auf 0. Wann Das nächste Element wird eingefügt, es wird 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
Die mithilfe eines Binärheaps implementierte Prioritätswarteschlange ist kein FIFO mehr, sondern wird basierend auf der vom Element implementierten Comparable-Schnittstelle oder dem an den Komparator übergebenen Vergleichsergebnis aus der Warteschlange entfernt Wert: Je höher die Priorität, desto früher wird sie aus der Warteschlange entfernt. Beachten Sie jedoch, dass die Rückgabe von iterator() nicht sortiert wird.
–Thread-sichere Warteschlange–
ConcurrentLinkedQueue/ConcurrentLinkedDeque
Unbegrenzte Parallelität optimierte Warteschlange, basierend auf verknüpfter Liste, implementiert einen sperrenfreien Algorithmus, der auf CAS basiert.
Die Struktur von ConcurrentLinkedQueue besteht aus einer einseitig verknüpften Liste und zwei Zeigern, Kopf/Schwanz, da Sie beim Beitritt zur Warteschlange den nächsten Zeiger des Schwanzelements der Warteschlange und den Schwanz ändern müssen Um auf das neu verbundene Element zu verweisen, können die beiden CAS-Aktionen nicht atomar sein. Informationen zu den erforderlichen speziellen Algorithmen finden Sie aus Platzgründen im 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 sich die Geschwindigkeit von Produzenten und Konsumenten nicht zu stark unterscheidet und eine Speichererschöpfung vermieden wird. 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:
ArrayBlockingQueue
Parallelität mit fester Länge, optimierte BlockingQueue, implementiert basierend auf einem Schleifenarray. 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
Eine parallelitätsoptimierte BlockingQueue mit einer ausgewählten Länge wird basierend auf einer verknüpften Liste implementiert, sodass die Länge auf Integer.MAX_VALUE gesetzt werden kann. 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 eingegebenen Elemente vom Verbraucher weggenommen und dann zurückgegeben werden. Sie sollten es lernen, wenn Sie Zeit haben.
