Sammlungen
84. Erzählen Sie uns etwas über Iteratoren und wie sie verwendet werden
Sammlungen sind ein Lieblingsthema in jedem Java-Entwicklerinterview. Bei der Beantwortung von Fragen zur Sammlungshierarchie sagen Kandidaten oft, dass diese mit der Sammlungshierarchie beginnt . Aber das ist nicht so. Eine Ebene darüber gibt es eine weitere Schnittstelle: Iterable . Diese Schnittstelle besteht aus der Methode iterator() , mit der Sie auf das Iterator- Objekt für die aktuelle Sammlung zugreifen können. Und was genau ist dieses Iterator- Objekt? Das Iterator- Objekt bietet die Möglichkeit, sich durch eine Sammlung zu bewegen und über ihre Elemente zu iterieren, und der Benutzer muss die spezifischen Implementierungsdetails der Sammlung nicht kennen. Mit anderen Worten, es ist eine Art Zeiger auf die Elemente der Sammlung, als ob es einen Blick in eines von ihnen werfen würde. Der Iterator verfügt über Methoden wie:-
hasNext() – gibt true zurück , wenn die Iteration ein anderes Element enthält (diese Methode informiert Sie, wenn Sie das Ende der Sammlung erreicht haben);
-
next() – gibt das nächste Element in der Iteration zurück. Wenn keine vorhanden ist, wird eine NoSuchElementException ausgelöst. Das heißt, bevor Sie diese Methode verwenden, ist es am besten, die Methode hasNext() zu verwenden, um sicherzustellen, dass ein nächstes Element vorhanden ist.
-
remove() – entfernt das letzte mit der next()- Methode empfangene Element aus der Sammlung . Wenn next() noch nie aufgerufen wurde, führt der Aufruf von remove () dazu, dass eine IllegalStateException geworfen wird.
-
forEachRemaining(<Consumer>) – führt die übergebene Aktion für jedes Element der Sammlung aus (diese Methode erschien in Java 8).
List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
iterator.next();
iterator.remove();
}
System.out.println(list.size());
Die Konsole zeigt Folgendes an:
iterator.forEachRemaining(x -> System.out.print(x));
Sobald wir dies jedoch tun, ist der Iterator für die weitere Verwendung unbrauchbar: Er hat die gesamte Liste durchlaufen und ein gewöhnlicher Iterator verfügt über keine Methoden zum Rückwärtsiterieren. Und das ist ein schöner Einstieg in die Diskussion von LinkedList , insbesondere seiner listIterator() -Methode, die einen erweiterten Iteratortyp zurückgibt: ListIterator . Zusätzlich zu den Methoden eines regulären (Standard-)Iterators verfügt dieser Typ über Folgendes:
-
add(<Element>) – fügt der Liste ein neues Element hinzu;
-
hasPrevious() – gibt true zurück , wenn sich ein Element vor dem nächsten Element befindet (wenn es ein vorheriges Element gibt);
-
nextIndex() – gibt den Index des nächsten Elements zurück;
-
previous() – gibt das vorherige Element zurück (das vor dem nächsten Element);
-
previousIndex gibt den Index des vorherigen Elements zurück.
-
set(<Element>) – ersetzt das letzte von next() oder previous() zurückgegebene Element .
85. Welche Sammlungshierarchie gibt es im Java Collection Framework?
In Java gibt es zwei Sammlungshierarchien. Die erste Hierarchie ist die Collection-Hierarchie, die folgenden Aufbau hat: Sie ist in folgende Untersammlungen unterteilt:-
Set ist eine Schnittstelle, die eine Menge beschreibt, eine Datenstruktur, die ungeordnete, eindeutige (sich nicht wiederholende) Elemente enthält. Diese Schnittstelle verfügt über einige Standardimplementierungen: TreeSet , HashSet und LinkedHashSet .
-
Liste ist eine Schnittstelle, die eine Datenstruktur beschreibt, die eine geordnete Folge von Objekten speichert. Objekte in einer Liste können über ihren Index in der Liste eingefügt und entfernt werden (wie ein Array, aber mit dynamischer Größenänderung). Diese Schnittstelle verfügt auch über einige Standardimplementierungen: ArrayList , Vector ( veraltet und nicht tatsächlich verwendet ) und LinkedList .
-
Queue ist eine Schnittstelle, die eine Datenstruktur beschreibt, die Elemente in einer FIFO-Warteschlange (First In First Out) speichert . Diese Schnittstelle verfügt über die folgenden Standardimplementierungen: LinkedList (das stimmt, sie implementiert auch Queue ) und PriotityQueue .
86. Wie ist die interne Struktur einer ArrayList?
Eine ArrayList ähnelt einem Array, kann jedoch dynamisch erweitert werden. Was bedeutet das? Unter der Haube verwendet ArrayList ein gewöhnliches Array, dh es speichert seine Elemente in einem internen Array, dessen Standardgröße 10 Zellen beträgt. Sobald das interne Array voll ist, wird ein neues Array erstellt. Die Größe des neuen Arrays wird durch diese Formel bestimmt:<size of the current array> * 3 / 2 + 1
Wenn also die Größe unseres Arrays 10 beträgt, beträgt die Größe des neuen Arrays: 10 * 3 / 2 + 1 = 16. Dann werden alle Werte aus dem ursprünglichen (alten) Array mithilfe der integrierten Funktion hineinkopiert System.arraycopy()- Methode und das ursprüngliche Array wird gelöscht. Kurz gesagt: Auf diese Weise implementiert ArrayList die dynamische Größenänderung. Betrachten wir die beliebtesten ArrayList- Methoden: 1. add(<Element>) – fügt ein Element am Ende des Arrays (in der letzten leeren Zelle) hinzu, nachdem zunächst überprüft wurde, ob im Array eine verfügbare Zelle vorhanden ist. Wenn nicht, wird ein neues Array erstellt und die Elemente werden hineinkopiert. Die zeitliche Komplexität dieser Operation beträgt O(1). Es gibt eine ähnliche add(<Index>, <Elelement>) -Methode. Es fügt ein Element nicht am Ende der Liste (Array) hinzu, sondern an der spezifischen Zelle, die durch den als Argument eingegebenen Index angegeben wird. In diesem Fall variiert die zeitliche Komplexität je nachdem, wo Sie Folgendes hinzufügen:
- Wenn das Hinzufügen nahe am Anfang der Liste liegt, liegt die Zeitkomplexität nahe bei O(N), da alle Elemente, die sich rechts vom neuen befinden, um eine Zelle nach rechts verschoben werden müssen.
- Wenn das Element in der Mitte eingefügt wird, ist es O(N/2), da wir nur die Hälfte der Listenelemente um eine Zelle nach rechts verschieben müssen.
87. Wie ist die interne Struktur einer LinkedList?
Eine ArrayList enthält Elemente im internen Array, eine LinkedList speichert sie jedoch in einer doppelt verknüpften Liste. Das bedeutet, dass jedes Element einen Link zum vorherigen Element und zum nächsten Element enthält. Das erste Element stellt keinen Link zu einem vorherigen Element her (schließlich ist es das erste). Es wird auch als Kopf der Liste betrachtet und das LinkedList- Objekt weist einen direkten Verweis darauf auf. Ebenso verfügt das letzte Element nicht über das nächste Element, da es das Ende der Liste darstellt. Das LinkedList- Objekt verweist auch direkt darauf. Dies bedeutet, dass die zeitliche Komplexität des Zugriffs auf den Anfang oder das Ende einer Liste O(1) beträgt. Wenn in ArrayList die Liste wächst, wächst auch das interne Array. Hier ist alles einfacher: Das Hinzufügen einer Referenz ist so einfach wie das Ändern einiger Links. Schauen wir uns einige der am häufigsten verwendeten LinkedList- Methoden an: 1. add(<Element>) – fügt ein Element am Ende der Liste hinzu, dh nach dem letzten Element (5) wird als nächstes ein Link zum neuen Element hinzugefügt . Der vorherige Verweis im neuen Element verweist auf das Element (5), das jetzt in der Liste davor steht. Die Zeitkomplexität dieser Operation beträgt O(1), da wir nur eine Verknüpfung zum letzten Element benötigen. Wie Sie sich erinnern, hat das LinkedList-Objekt einen direkten Verweis auf das Ende und der Zugriff darauf erfordert eine minimale konstante Zeitkomplexität. 2. add(<Index>, <Element>) – fügt ein Element nach Index hinzu. Beim Hinzufügen eines Elements, sagen wir, in der Mitte einer Liste, iteriert diese Methode zunächst über die Elemente vom Kopf bis zum Ende (in beide Richtungen), bis die gewünschte Stelle gefunden wird. Wenn wir ein Element zwischen dem dritten und vierten Element hinzufügen (im Bild oben), dann zeigt der nächste Link des dritten Elements auf das neue Element. Und das Vorherige des neu hinzugefügten Elements zeigt auf das dritte. Der vorherige Link des alten vierten Elements wiederum zeigt nun auf das neue Element und der nächste Link des neuen Elements zeigt auf das neue vierte Element: Die zeitliche Komplexität dieser Methode hängt vom Index des neuen Elements ab:- Liegt es nahe am Kopf oder Ende, nähert sich die Operation O(1), da es eigentlich nicht notwendig ist, über die Elemente zu iterieren.
- Wenn es nahe an der Mitte liegt, haben wir O(N/2), da die Methode gleichzeitig vom Kopf und vom Ende aus sucht, bis das gewünschte Element gefunden ist.
88. Wie ist die interne Struktur einer HashMap?
Dies ist möglicherweise eine der beliebtesten Interviewfragen, die Java-Entwicklerkandidaten gestellt werden. Eine HashMap arbeitet mit Schlüssel-Wert-Paaren . Wie werden sie in der HashMap selbst gespeichert? Eine HashMap verfügt über ein internes Array von Knoten:Node<K,V>[] table
Standardmäßig beträgt die Größe des Arrays 16 und verdoppelt sich jedes Mal, wenn es mit Elementen gefüllt wird (d. h. wenn der LOAD_FACTOR erreicht wird; er gibt den Schwellenwert an, wie voll das Array werden kann – standardmäßig ist er 0,75 ). . Jeder der Knoten speichert einen Hash des Schlüssels, den Schlüssel, einen Wert und eine Referenz auf das nächste Element: In diesem Fall bedeutet die „Referenz auf das nächste Element“, dass es sich um eine einfach verknüpfte Liste handelt. wobei jedes Element einen Link zum nächsten enthält. Mit anderen Worten: Eine HashMap speichert ihre Daten in einem Array einfach verknüpfter Listen. Aber lassen Sie mich gleich sagen: Wenn eine Zelle des Tabellenarrays eine einfach verknüpfte Liste hat, die aus mehr als einem Element besteht, ist das nicht gut. Dieses Phänomen wird Kollision genannt . Aber das Wichtigste zuerst. Sehen wir uns an, wie ein neues Paar mit der Put- Methode gespeichert wird. Zuerst ruft die Methode den hashCode() des Schlüssels ab . Dies bedeutet, dass die von Ihnen verwendeten Schlüssel Klassen sein müssen, die diese Methode überschreiben, damit eine HashMap ordnungsgemäß funktioniert. Dieser Hash-Code wird dann in der internen Methode hash() verwendet , um einen Index einer Zelle innerhalb des Tabellenarrays zu bestimmen. Der resultierende Index ermöglicht uns den Zugriff auf eine bestimmte Zelle des Tabellenarrays. Wir haben hier zwei Fälle:
- Die Zelle ist leer – in diesem Fall wird der neue Knotenwert darin gespeichert.
- Die Zelle ist nicht leer – in diesem Fall werden die Werte der Schlüssel verglichen. Wenn sie gleich sind, überschreibt der neue Knotenwert den alten; Wenn nicht gleich, wird auf den nächsten zugegriffen und sein Schlüssel verglichen ... Und so weiter, bis der neue Wert entweder einen alten Wert überschreibt oder wir das Ende der einfach verknüpften Liste erreichen und den neuen Wert dort als speichern letztes Element.
GO TO FULL VERSION