Der Anfang des Weges
Heute möchte ich über ein so interessantes Thema wie das „
Java Collections Framework “ oder, vereinfacht gesagt, über Sammlungen sprechen. Die meiste Arbeit des Codes besteht darin, Daten in der einen oder anderen Form zu verarbeiten. Rufen Sie eine Liste der Benutzer ab, rufen Sie eine Liste der Adressen usw. ab. Irgendwie sortieren, eine Suche durchführen, vergleichen. Daher gilt die Kenntnis von Sammlungen als eine Kernkompetenz. Deshalb möchte ich darüber sprechen. Darüber hinaus sind Sammlungen eine der häufigsten Fragen in Java-Entwicklerinterviews. Beispiel: „Zeichnen Sie eine Hierarchie von Sammlungen.“ Der Online-Compiler hilft uns dabei. Sie können beispielsweise „ Tutorialspoint
Online Java Compiler “ oder
Repl.it verwenden. Der Weg zum Kennenlernen jeglicher Datenstrukturen beginnt mit gewöhnlichen Variablen (Variablen). Auf der Oracle-Website werden verschiedene Themen als „Pfade“ oder Trails dargestellt. Der Weg zum Kennenlernen von Java heißt also „
Trail: Learning the Java Language: Table of Contents “. Und die Grundlagen der Sprache (d. h. Sprachgrundlagen) beginnen mit Variablen. Schreiben wir daher einen einfachen Code:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Es ist in allem gut, außer dass wir verstehen, dass dieser Code nur für eine Variable gut und schön ist. Was tun, wenn es mehrere davon gibt? Arrays wurden erfunden, um Daten eines Typs zu speichern. Im gleichen Trail von Oracle gibt es einen separaten Abschnitt, der Arrays gewidmet ist. Dieser Abschnitt heißt: „
Arrays “. Auch die Arbeit mit Arrays ist ganz einfach:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Arrays lösen das Problem der Speicherung mehrerer Werte an einem Ort. Es gibt jedoch eine Einschränkung: Die Array-Größe ist konstant. Wenn wir wie im Beispiel sagen, dass Größe = 2 ist, dann ist es gleich zwei. Und alle. Wenn wir ein größeres Array wünschen, müssen wir eine neue Instanz erstellen. Außerdem ist das Auffinden eines Elements für ein Array ebenfalls eine schwierige Sache. Es gibt eine Methode
Arrays.binarySearch, aber diese Suche funktioniert nur bei einem sortierten Array (bei einem unsortierten Array ist das Ergebnis undefiniert oder einfach unvorhersehbar). Das heißt, die Suche zwingt uns, jedes Mal zu sortieren. Durch das Löschen wird auch nur der Wert gelöscht. Daher wissen wir immer noch nicht, wie viele Daten sich tatsächlich im Array befinden, wir wissen nur, wie viele Zellen sich im Array befinden. Um Ihr Wissen über Arrays aufzufrischen:
Und als Folge der Entwicklung der Java-Sprache erschien das Java Collections Framework in JDK 1.2, über das wir heute sprechen werden.
Sammlung
Beginnen Sie mit der Kalkulation von Anfang an. Warum Sammlungen? Der Begriff selbst stammt aus Dingen wie „Typtheorie“ und „Abstrakte Datentypen“. Aber wenn man sich keine hohen Dinge ansieht, dann können wir, wenn wir mehrere Dinge haben, sie eine „Ansammlung von Dingen“ nennen. Diejenigen, die Gegenstände sammeln. Im Allgemeinen stammt das Wort „sammeln“ aus dem Lateinischen. Collectio „Sammeln, Sammeln“. Das heißt, eine Sammlung ist eine Sammlung von etwas, ein Container für einige Elemente. Wir haben also eine Sammlung von Elementen. Was wir damit machen wollen:
Wie Sie sehen, wünschen wir uns möglicherweise recht logische Dinge. Wir verstehen auch, dass wir möglicherweise etwas mit mehreren Sammlungen machen möchten:
Dementsprechend haben die Java-Entwickler die Schnittstelle java.util.Collection geschrieben , um dieses allgemeine Verhalten für alle Sammlungen zu beschreiben . Die Collection-Schnittstelle ist der Ursprung aller Sammlungen. Sammlung ist eine Idee, es ist eine Vorstellung davon, wie sich alle Sammlungen verhalten sollten. Daher wird der Begriff „Sammlung“ als Schnittstelle ausgedrückt. Natürlich braucht eine Schnittstelle Implementierungen. Die Schnittstelle
java.util.Collectionverfügt über eine abstrakte Klasse
AbstractCollection, also eine „abstrakte Sammlung“, die das Grundgerüst für andere Implementierungen darstellt (wie im JavaDoc über der Klasse geschrieben
java.util.AbstractCollection). Apropos Sammlungen: Gehen wir zurück und bedenken Sie, dass wir sie durchlaufen möchten. Das bedeutet, dass wir die Elemente einzeln durchlaufen möchten. Das ist ein sehr wichtiges Konzept. Daher
Collectionwird die Schnittstelle von geerbt
Iterable. Das ist sehr wichtig, weil... Erstens muss alles Iterable in der Lage sein, basierend auf seinem Inhalt einen Iterator zurückzugeben. Und zweitens kann alles, was Iterable ist, in Schleifen verwendet werden
for-each-loop. Und mit Hilfe eines Iterators werden
AbstractCollectionMethoden wie
contains,, implementiert . Und der Weg zum Verständnis von Sammlungen beginnt mit einer der häufigsten Datenstrukturen – einer Liste, d. h. .
toArrayremoveList
Listen
Daher nehmen Listen einen wichtigen Platz in der Sammlungshierarchie ein:
Wie wir sehen können, implementieren Listen die Schnittstelle
java.util.List . Listen drücken aus, dass wir eine Sammlung von Elementen haben, die in einer bestimmten Reihenfolge nacheinander angeordnet sind. Jedes Element hat einen Index (wie in einem Array). In der Regel können Sie in einer Liste Elemente mit demselben Wert haben. Wie oben erwähnt,
Listkennt es den Index des Elements.
getAuf diese Weise können Sie ein Element anhand des Index abrufen ( ) oder einen Wert für einen bestimmten Index festlegen (
set). Mit den Sammlungsmethoden
add, können Sie den Index angeben, von dem aus sie ausgeführt werden sollen. Darüber hinaus verfügt y über eine eigene Version eines Iterators namens . Dieser Iterator kennt den Index des Elements und kann daher nicht nur vorwärts, sondern auch rückwärts iterieren. Es kann sogar von einer bestimmten Stelle in der Sammlung aus erstellt werden. Unter allen Implementierungen werden zwei am häufigsten verwendet: und . Erstens handelt es sich um eine Liste ( ), die auf einem Array ( ) basiert.
Dadurch können Sie einen „wahlfreien Zugriff“ auf Elemente erreichen . Beim wahlfreien Zugriff handelt es sich um die Möglichkeit, ein Element sofort anhand des Index abzurufen, anstatt alle Elemente zu durchlaufen, bis wir das Element mit dem gewünschten Index gefunden haben. Es ist das Array als Basis, das dies ermöglicht. Im Gegenteil, es handelt sich um eine verknüpfte Liste. Jeder Eintrag in einer verknüpften Liste wird im Formular dargestellt , das die Daten selbst sowie einen Link zum nächsten (nächsten) und vorherigen (vorherigen) speichert . Dadurch wird „Sequentieller Zugriff
“ implementiert . Es ist klar, dass wir, um das 5. Element zu finden, vom ersten zum letzten Element gehen müssen, denn Wir haben keinen direkten Zugriff auf das fünfte Element. Wir können darauf erst ab dem 4. Element zugreifen. Der Unterschied in ihrem Konzept ist unten aufgeführt:
addAllremoveListListIteratorArrayListLinkedListArrayListListArrayLinkedListEntryEntryLinkedList
Wie Sie verstehen, gibt es auch bei der Arbeit einen Unterschied. Zum Beispiel das Hinzufügen von Elementen. Die
LinkedListElemente sind einfach wie Glieder einer Kette miteinander verbunden. Aber
ArrayListes speichert Elemente in einem Array. Und wie wir wissen, kann ein Array seine Größe nicht ändern. Wie funktioniert es dann
ArrayList? Und es funktioniert ganz einfach. Wenn der Speicherplatz im Array erschöpft ist, erhöht er sich um das 1,5-fache. Hier ist der Zoom-Code:
int newCapacity = oldCapacity + (oldCapacity >> 1); Ein weiterer Unterschied in der Bedienung ist der beliebige Versatz von Elementen. Zum Beispiel beim Hinzufügen oder Entfernen von Elementen in der Mitte. Zum Entfernen aus
LinkedListeinem Element entfernen Sie einfach Verweise auf dieses Element. Im Fall von
ArrayListsind wir gezwungen, die Elemente jedes Mal mit dem zu verschieben
System.arraycopy. Je mehr Elemente also vorhanden sind, desto mehr Aktionen müssen ausgeführt werden. Eine ausführlichere Beschreibung finden Sie in diesen Artikeln:
Nachdem man ArrayList untersucht hat, kommt man nicht umhin, sich an seinen „Vorgänger“ zu erinnern, die Klasse
java.util.Vector . Der Unterschied besteht
Vectordarin
ArrayList, dass die Methoden zum Arbeiten mit der Sammlung (Hinzufügen, Löschen usw.) synchronisiert sind. Das heißt, wenn ein Thread (
Thread) Elemente hinzufügt, warten die anderen Threads, bis der erste Thread seine Arbeit beendet hat. Da Thread-Sicherheit häufig nicht erforderlich ist, wird empfohlen, in solchen Fällen die Klasse zu verwenden
ArrayList, wie im JavaDoc für die Klasse explizit angegeben
Vector. Außerdem
Vectorvergrößert es seine Größe nicht um das 1,5-fache,
ArrayListsondern um das 2-fache. Ansonsten ist das Verhalten dasselbe –
Vectordie Speicherung von Elementen in Form eines Arrays wird ausgeblendet und das Hinzufügen/Entfernen von Elementen hat die gleichen Konsequenzen wie in
ArrayList. Tatsächlich
Vectorhaben wir uns aus einem bestimmten Grund daran erinnert. Wenn wir im Javadoc nachsehen, werden wir in „Direct Known Subclasses“ eine Struktur wie
java.util.Stack sehen . Der Stapel ist eine interessante Struktur, die eine LIFO-
last-in-first-outStruktur (Last In, First Out) ist. Aus dem Englischen übersetzt ist „Stack“ ein Stapel (wie zum Beispiel ein Stapel Bücher). Der Stack implementiert zusätzliche Methoden:
peek(look, look),
pop(push),
push(push). Die Methode
peekwird mit „schauen“ übersetzt (zum Beispiel wird „
peek inside the bag “ mit „ schau in die Tasche “ übersetzt und „
peek through the keyhole“ wird mit „ peek through the keyhole “ übersetzt ). Mit dieser Methode können Sie die „Oberseite“ des Stapels betrachten, d. h. Holen Sie sich das letzte Element, ohne es vom Stapel zu entfernen (d. h. ohne es zu entfernen). Die Methode
pushschiebt (fügt) ein neues Element auf den Stapel und gibt es zurück, und die Elementmethode
popschiebt (entfernt) das entfernte Element und gibt es zurück. In allen drei Fällen (also Peek, Pop und Push) arbeiten wir nur mit dem letzten Element (also der „Oberseite des Stapels“). Dies ist das Hauptmerkmal der Stapelstruktur. Übrigens gibt es eine interessante Aufgabe zum Verständnis von Stapeln, die im Buch „A Programmer's Career“ (Cracking Coding Interview) beschrieben wird. Es gibt eine interessante Aufgabe, bei der Sie mithilfe der „Stack“-Struktur (LIFO) die „Warteschlange“ implementieren müssen ” Struktur (FIFO). Es sollte so aussehen:
Eine Analyse dieser Aufgabe finden Sie hier: „
Implementieren Sie eine Warteschlange mithilfe von Stacks – The Queue ADT („Implement Queue Using Stacks“ auf LeetCode) “. Wir gehen also reibungslos zu einer neuen Datenstruktur über – einer Warteschlange.
Warteschlange
Eine Warteschlange ist eine Struktur, die uns aus dem Leben bekannt ist. Schlangen vor Geschäften, vor Ärzten. Wer zuerst da war (First In), verlässt als Erster die Warteschlange (First Out). In Java wird eine Warteschlange durch die Schnittstelle
java.util.Queue dargestellt . Laut Javadoc der Warteschlange fügt die Warteschlange die folgenden Methoden hinzu:
Wie Sie sehen, gibt es Auftragsmethoden (deren Nichtausführung mit einer Ausnahme behaftet ist) und Anforderungsmethoden (deren Nichtausführung nicht zu Fehlern führt). Es ist auch möglich, das Element zu erhalten, ohne es zu entfernen (Peek oder Element). Auch die Queue-Schnittstelle hat einen nützlichen Nachfolger –
Deque . Dabei handelt es sich um die sogenannte „Zwei-Wege-Warteschlange“. Das heißt, eine solche Warteschlange ermöglicht die Verwendung dieser Struktur sowohl vom Anfang als auch vom Ende. In der Dokumentation heißt es: „Deques können auch als LIFO-Stacks (Last-In-First-Out) verwendet werden. Diese Schnittstelle sollte der älteren Stack-Klasse vorgezogen werden.“ Das heißt, es wird empfohlen, stattdessen Deque-Implementierungen zu verwenden Stapel. Das Javadoc zeigt, welche Methoden die Deque-Schnittstelle beschreibt:
Mal sehen, welche Implementierungen es gibt. Und wir werden eine interessante Tatsache sehen: LinkedList ist in das Warteschlangenlager geraten. Das heißt, LinkedList implementiert sowohl
List, als auch
Deque. Es gibt aber beispielsweise auch „nur Warteschlangen“
PriorityQueue. Man erinnert sich nicht oft an sie, aber vergebens. Erstens können Sie in dieser Warteschlange keine „nicht vergleichbaren Objekte“ verwenden, d. h. Entweder muss Comparator angegeben werden oder alle Objekte müssen vergleichbar sein. Zweitens: „Diese Implementierung stellt O(log(n)) Zeit für die Ein- und Ausreihungsmethoden bereit.“ Logarithmische Komplexität gibt es aus einem bestimmten Grund. PriorityQueue basierend auf dem Heap implementiert. Im Javadoc heißt es: „Prioritätswarteschlange als ausgeglichener binärer Heap dargestellt“. Der Speicher selbst hierfür ist ein reguläres Array. Was bei Bedarf wächst. Wenn der Heap klein ist, erhöht er sich um das Zweifache. Und dann um 50 %. Kommentar aus dem Code: „Doppelte Größe, wenn klein; sonst um 50 % wachsen“. Prioritätswarteschlange und binärer Heap sind ein separates Thema. Also für weitere Informationen:
Als Implementierung
java.util.Dequekönnen Sie die Klasse
java.util.ArrayDeque verwenden . Das heißt, Listen können mithilfe einer verknüpften Liste und eines Arrays implementiert werden, und Warteschlangen können auch mithilfe eines Arrays oder einer verknüpften Liste implementiert werden.
QueueDie und- Schnittstellen
Dequehaben Nachkommen, die die „Blockierungswarteschlange“ darstellen:
BlockingQueueund
BlockingDeque. Hier ist die Schnittstellenänderung im Vergleich zu regulären Warteschlangen:
Schauen wir uns einige Beispiele für blockierende Warteschlangen an. Aber sie sind interessant. BlockingQueue wird beispielsweise implementiert durch:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Aber
BlockingDequesie implementieren alles aus den Standard-Collection-Frameworks
LinkedBlockingDeque. Jede Warteschlange ist Gegenstand einer separaten Überprüfung. Und im Rahmen dieser Rezension werden wir die Klassenhierarchie nicht nur mit
List, sondern auch mit darstellen
Queue:
Wie wir dem Diagramm entnehmen können, sind die Schnittstellen und Klassen des Java Collections Framework stark miteinander verflochten. Fügen wir einen weiteren Zweig der Hierarchie hinzu –
Set.
Satz
Set– übersetzt als „gesetzt“. Sie unterscheidet sich von einer Warteschlange und einer Liste
Setdurch ihre stärkere Abstraktion über die Speicherung von Elementen.
Set- wie eine Tüte mit Gegenständen, bei der unbekannt ist, wie sich die Gegenstände befinden und in welcher Reihenfolge sie liegen. In Java wird ein solcher Satz durch die Schnittstelle
java.util.Set dargestellt . Wie es in der Dokumentation heißt,
Sethandelt es sich hierbei um eine „Sammlung, die keine doppelten Elemente enthält“. Interessanterweise fügt die Schnittstelle selbst
Setkeine neuen Methoden hinzu
Collection, sondern klärt lediglich die Anforderungen (darüber, was keine Duplikate enthalten sollte). Darüber hinaus folgt aus der vorherigen Beschreibung, dass man
Setdaraus nicht einfach ein Element erhalten kann. Iterator wird verwendet, um Elemente abzurufen.
SetEs sind mehrere weitere Schnittstellen damit verbunden. Der erste ist
SortedSet. Wie der Name schon sagt,
SortedSetbedeutet dies, dass eine solche Menge sortiert ist und daher die Elemente die Schnittstelle implementieren
Comparableoder spezifiziert sind
Comparator. Darüber hinaus
SortedSetbietet es mehrere interessante Methoden:
Darüber hinaus gibt es Methoden
first(kleinstes Element nach Wert) und
last(größtes Element nach Wert). Es
SortedSetgibt einen Erben -
NavigableSet. Der Zweck dieser Schnittstelle besteht darin, die Navigationsmethoden zu beschreiben, die zur genaueren Identifizierung geeigneter Elemente erforderlich sind. Eine interessante Sache ist,
NavigableSetdass es dem üblichen Iterator (der vom kleinsten zum größten geht) einen Iterator für die umgekehrte Reihenfolge hinzufügt –
descendingIterator. Darüber hinaus
NavigableSetermöglicht es Ihnen, mit der Methode
descendingSeteine Sicht auf sich selbst (View) zu erhalten, in der die Elemente in umgekehrter Reihenfolge vorliegen. Dies wird so genannt
View, weil Sie durch das resultierende Element die Elemente des ursprünglichen Elements ändern können
Set. Das heißt, es handelt sich im Wesentlichen um eine Darstellung der Originaldaten auf andere Weise und nicht um eine Kopie davon. Interessanterweise kann ,
NavigableSetwie , (minimale) und (maximale) Elemente
Queueverarbeiten . Das heißt, es ruft dieses Element ab und entfernt es aus der Menge. Welche Implementierungen gibt es? Erstens basiert die bekannteste Implementierung auf einem Hash-Code –
HashSet . Eine weitere ebenso bekannte Implementierung basiert auf einem rot-schwarzen Baum –
TreeSet . Vervollständigen wir unser Diagramm:
pollFirstpollLast
Innerhalb der Sammlungen bleibt die Hierarchie zu klären – die Einsiedler. Was auf den ersten Blick daneben steht -
java.util.Map.
Karten
Karten sind eine Datenstruktur, in der Daten nach Schlüsseln gespeichert werden. Der Schlüssel könnte beispielsweise eine ID oder ein Stadtcode sein. Und mit diesem Schlüssel werden die Daten durchsucht. Interessant ist, dass die Karten separat angezeigt werden. Laut den Entwicklern (siehe „
Java Collections API Design FAQ “) handelt es sich bei der Schlüsselwertzuordnung nicht um eine Sammlung. Und Karten können schneller als eine Sammlung von Schlüsseln, eine Sammlung von Werten, eine Sammlung von Schlüssel-Wert-Paaren betrachtet werden. Das ist so ein interessantes Tier. Welche Methoden bieten Karten? Schauen wir uns die Java-API-Schnittstelle
java.util.Map an . Weil Da Karten keine Sammlungen sind (sie erben nicht von Sammlungen), enthalten sie keine
contains. Und das ist logisch. Eine Karte besteht aus Schlüsseln und Werten. Welche davon sollte die Methode überprüfen
containsund wie kann man keine Verwirrung stiften? Daher
Mapgibt es von der Schnittstelle zwei verschiedene Versionen:
containsKey(enthält einen Schlüssel) und
containsValue(enthält einen Wert). Wenn Sie es verwenden,
keySeterhalten Sie einen Satz Schlüssel (den gleichen
Set). Und mit dieser Methode
valueskönnen wir eine Sammlung von Werten in der Karte erhalten. Die Schlüssel in der Karte sind eindeutig, was durch die Datenstruktur hervorgehoben wird
Set. Werte können wiederholt werden, was durch die Datenstruktur der Sammlung hervorgehoben wird. Darüber hinaus
entrySetkönnen wir mit dieser Methode eine Reihe von Schlüssel-Wert-Paaren erhalten. Welche Kartenimplementierungen es gibt, können Sie in den detailliertesten Analysen nachlesen:
Ich würde auch gerne sehen, was , und , sehr
HashMapähnlich ist . Sie haben sogar ähnliche Schnittstellen: und , und . Unsere endgültige Karte wird also so aussehen:
HashSetTreeMapTreeSetNavigableSetNavigableMapSortedSetSortedMap
Wir können mit der interessanten Tatsache abschließen, dass die Sammlung
Setintern verwendet
Map, wobei die hinzugefügten Werte Schlüssel sind und der Wert überall gleich ist. Das ist interessant, weil es
Mapsich nicht um eine Sammlung handelt und zurückgibt
Set, was zwar eine Sammlung ist, aber tatsächlich als implementiert ist
Map. Ein bisschen surreal, aber so ist es geworden)
Abschluss
Die gute Nachricht ist, dass diese Rezension hier endet. Die schlechte Nachricht ist, dass dies ein sehr rezensierter Artikel ist. Jede Implementierung jeder Sammlung verdient einen eigenen Artikel, und auch für jeden Algorithmus, der vor unseren Augen verborgen ist. Der Zweck dieser Überprüfung besteht jedoch darin, sich daran zu erinnern, was sie sind und welche Verbindungen zwischen den Schnittstellen bestehen. Ich hoffe, dass Sie nach sorgfältiger Lektüre in der Lage sind, aus dem Gedächtnis ein Diagramm der Sammlungen zu zeichnen.
Nun, wie immer, einige Links:
#Wjatscheslaw
GO TO FULL VERSION