Tipps zur Verwendung von Sammlungen

1. Liste der Sammlungen

Wie Sie sich vielleicht erinnern, verfügt Java über Sammlungen – ein praktisches Werkzeug zum Speichern von Objekten desselben Typs.

Versuchen wir, uns an die wichtigsten sammlungsbezogenen Schnittstellen zu erinnern:

Liste , Satz , Karte und Warteschlange .

Wie üblich sind Werkzeuge nicht unbedingt gut oder schlecht – entscheidend ist, ob Sie sie für den vorgesehenen Zweck verwenden. Und dazu müssen wir ihre spezifischen Merkmale genau verstehen, um zu wissen, welche Sammlung wir wann verwenden sollten.

1. Liste

Beginnen wir mit der am häufigsten verwendeten Sammlung.

Liste so nah wie möglich an einem einfachen alten Array.

Mit dieser Sammlung können wir bequem eine Liste von Objekten desselben Typs speichern, ohne uns Gedanken über die Größe der Sammlung selbst machen zu müssen, wie dies bei Verwendung eines Arrays der Fall wäre. Der Zugriff auf Elemente der Sammlung erfolgt über den Index. Wenn wir genau wissen, wo sich ein Objekt befindet, und häufig darauf zugreifen müssen, ohne häufig Elemente hinzufügen oder entfernen zu müssen, ist eine Liste ideal.

2. Einstellen

Set hat einen völlig anderen Aufbau.

Das Set eignet sich am besten, wenn wir einzigartige Objekte aufbewahren müssen. Beispielsweise eine Gruppe von Autoren in einer Bibliothek, in der jeder Autor einzigartig ist. Aber wir können nicht einfach einen bestimmten Autor herausgreifen. Mit Set können wir schnell überprüfen, ob ein bestimmter Autor in unserer Bibliothek vorhanden ist, dh wir können überprüfen, ob ein eindeutiges Objekt in einem Set vorhanden ist . Wir können auch über die gesamte Sammlung iterieren und auf jedes Element zugreifen, aber das ist nicht optimal.

Mit anderen Worten: Für unsere Bibliothek kann ein Set die Sammlung aller einzelnen Autoren darstellen, um schnell zu überprüfen, ob ein bestimmter Autor vorhanden ist.

3. Karte

Map ähnelt eher einem Aktenschrank, in dem jede Datei signiert ist und einzelne Objekte oder ganze Strukturen gespeichert werden können. Map sollte in Fällen verwendet werden, in denen wir eine Zuordnung von einem Wert zu einem anderen aufrechterhalten müssen.

Für Map werden diese Beziehungen als Schlüssel-Wert-Paare bezeichnet.

Wir könnten diese Struktur in unserer Bibliothek verwenden, indem wir Autorenobjekte als Schlüssel und Listen ( Listenobjekte ) von Büchern als Werte verwenden. Nachdem wir also ein Set überprüft haben, um zu sehen, ob ein Autorenobjekt in der Bibliothek vorhanden ist, können wir dasselbe Autorenobjekt verwenden, um eine Liste seiner Bücher aus einer Map abzurufen .

4. Warteschlange

Queue ist eine Sammlung, die – Überraschung! — implementiert das Verhalten einer Warteschlange. Und die Warteschlange kann entweder LIFO (Last In, First Out) oder FIFO (First In, First Out)seinDarüber hinaus kann die Warteschlange bidirektional oder „doppelt“ sein.

Diese Struktur ist hilfreich, wenn die der Klasse hinzugefügten Objekte in der Reihenfolge verwendet werden müssen, in der sie empfangen werden. Nehmen Sie zum Beispiel unsere Bibliothek.

Wir können neu angekommene Besucher zu einer Warteschlange hinzufügen und sie abwechselnd bedienen, indem wir ihnen die Bücher aushändigen, für die sie gekommen sind.

Wie wir sehen, ist jede dieser Strukturen gut, wenn sie für den vorgesehenen Zweck verwendet wird. Und wir haben in einem einzigen Bibliotheksbeispiel gute Verwendungsmöglichkeiten für alle vier Arten von Sammlungen gefunden.

2. Komplexität

Wie bereits erwähnt, handelt es sich bei den oben betrachteten Sammlungen um Schnittstellen, was bedeutet, dass sie über Implementierungen verfügen müssen, damit wir sie verwenden können.

So wie das Einschlagen von Nägeln mit dem Mikroskop nicht die beste Idee ist, ist nicht jede Umsetzung einer Kollektion für jede Situation geeignet.

Bei der Auswahl des richtigen Werkzeugs für eine Aufgabe achten wir typischerweise auf zwei Merkmale:

• Wie gut passt das Werkzeug zur Aufgabe?
• Wie schnell wird die Arbeit erledigt?

Wir haben einige Zeit damit verbracht, herauszufinden, wie man ein geeignetes Werkzeug für eine Aufgabe auswählt, aber seine Geschwindigkeit ist etwas Neues.

In der Informatik wird die Geschwindigkeit eines Werkzeugs oft als Zeitkomplexität ausgedrückt und mit dem Großbuchstaben O bezeichnet.

Was in aller Welt ist Zeitkomplexität?

Vereinfacht ausgedrückt gibt die Zeitkomplexität die Zeit an, die ein Algorithmus in der Sammlung benötigt, um eine bestimmte Aktion auszuführen (Hinzufügen/Entfernen eines Elements, Suchen nach einem Element).

ArrayList vs. LinkedList

Sehen wir uns dies anhand zweier Implementierungen der List- Schnittstelle an – ArrayList und LinkedList .

Äußerlich gesehen ist die Arbeit mit diesen Kollektionen ähnlich:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Wie Sie sehen, sieht das Hinzufügen, Abrufen und Entfernen von Elementen für beide Sammlungstypen gleich aus. Dies liegt daran, dass es sich um Implementierungen auf derselben Schnittstelle handelt. Aber hier enden die Gemeinsamkeiten.

Aufgrund ihrer unterschiedlichen Implementierungen der List- Schnittstelle führen diese beiden Strukturen unterschiedliche Aktionen effizienter aus als andere.

Erwägen Sie das Entfernen und Hinzufügen eines Elements.

Wenn wir ein Element aus der Mitte einer ArrayList entfernen müssen , müssen wir den Teil der Liste überschreiben, der auf das entfernte Element folgt.

Angenommen, wir haben eine Liste mit 5 Elementen und möchten das dritte entfernen.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

In diesem Fall wird durch das Entfernen eine Zelle freigegeben, daher müssen wir das 4. Element dort schreiben, wo das 3. war, und das 5. dort, wo das 4. war.

Das ist höchst ineffizient.

Das Gleiche passiert, wenn Sie ein Element in die Mitte der Liste hinzufügen.

LinkedList ist anders aufgebaut. Das Hinzufügen oder Entfernen von Elementen geht schnell, da wir nur die Referenzen in den vorherigen und nächsten Elementen ändern müssen und dadurch das Objekt, das wir entfernen, aus der Elementkette ausschließen.

Zurück zum Beispiel derselben Liste mit 5 Elementen: Nachdem wir das dritte Element entfernt haben, müssen wir lediglich den Verweis des zweiten Elements auf das nächste Element und den Verweis des vierten Elements auf das vorherige ändern.

Wenn der Liste ein Element hinzugefügt wird, erfolgt der gleiche Vorgang, jedoch in umgekehrter Reihenfolge.

Beachten Sie, wie viel weniger Arbeit wir in einer LinkedList im Vergleich zu einer ArrayList leisten müssen . Und das sind nur 5 Elemente. Wenn unsere Liste 100 oder mehr Elemente hätte, würde die Überlegenheit von LinkedList noch deutlicher hervortreten.

Aber wie ändert sich die Situation, wenn wir über den Index auf ein Element zugreifen?

Hier ist alles genau umgekehrt.

Da ArrayList als gewöhnliches Array strukturiert ist, ist es für uns sehr einfach, jedes Element anhand seines Index zu ermitteln. Wir bewegen einfach den Zeiger an eine bestimmte Stelle und holen uns das Element aus der entsprechenden Zelle.

Aber eine LinkedList funktioniert so einfach nicht. Wir müssen alle Elemente der Liste durchgehen, um das Element mit einem bestimmten Index zu finden.

Sollen wir versuchen, das alles in Form eines großen O auszudrücken?

Beginnen wir mit dem Zugriff auf ein Element über den Index.

In einer ArrayList geschieht dies in einem Schritt, unabhängig davon, wo sich das Element in der Liste befindet. Ob am Ende oder am Anfang.

In diesem Fall beträgt die Zeitkomplexität O(1) .

In einer LinkedList müssen wir über eine Anzahl von Elementen iterieren, die dem Wert des benötigten Index entspricht.

Die Zeitkomplexität für eine solche Aktion beträgt O(n) , wobei n der Index des benötigten Elements ist.

Hier sehen Sie, dass die Zahl, die wir in die großen O-Klammern setzen, der Anzahl der durchgeführten Aktionen entspricht.

Shell, kehren wir zum Entfernen und Hinzufügen zurück?

Beginnen wir mit LinkedList.

Da wir nicht viele Aktionen ausführen müssen, um ein Element hinzuzufügen oder zu entfernen, und die Geschwindigkeit dieser Operation in keiner Weise davon abhängt, wo sich das Element befindet, wird seine Komplexität als O(1) ausgedrückt und gesagt konstant sein.

Die zeitliche Komplexität dieser Operation für ArrayList beträgt ebenfalls O(n) , was wir lineare Komplexität nennen.

Bei Algorithmen mit linearer Komplexität hängt die Laufzeit direkt von der Anzahl der zu verarbeitenden Elemente ab. Es kann auch von der Position des Elements abhängen, ob es sich am Anfang der Liste oder am Ende befindet.

Zeitkomplexität kann auch logarithmisch sein. Dies wird als O(log n) ausgedrückt .

Betrachten Sie als Beispiel ein sortiertes TreeSet bestehend aus 10 Zahlen. Wir wollen die Nummer 2 finden.

Da die Liste sortiert ist und keine Duplikate enthält, können wir sie in zwei Hälften teilen und prüfen, welche Hälfte die gewünschte Zahl enthalten würde, den irrelevanten Teil verwerfen und diesen Vorgang dann wiederholen, bis wir das gewünschte Element erreichen. Letztendlich werden wir die Anzahl der Elemente nach der Verarbeitung von log(n) finden (oder nicht finden).

Hier ist eine Tabelle, die die zeitliche Komplexität der übrigen Sammlungen zusammenfasst.

Nachdem wir nun eine Tabelle haben, die die zeitliche Komplexität beliebter Sammlungen zeigt, können wir die Frage beantworten, warum wir von so vielen Sammlungen am häufigsten ArrayList , HashSet und HashMap verwenden .

Es ist einfach so, dass sie für die meisten Aufgaben am effizientesten sind :)