Erkundung der Fragen und Antworten aus einem Vorstellungsgespräch für eine Stelle als Java-Entwickler. Teil 9

Programmierer zu sein ist nicht einfach. Es gibt immer etwas Neues zu lernen. Und wie bei jedem anderen Unterfangen ist es am schwierigsten, anzufangen und den ersten Schritt in Richtung Ihres Ziels zu tun. Aber da Sie bereits hier sind und diesen Artikel lesen, haben Sie den ersten Schritt getan. Das bedeutet, dass Sie sich jetzt bewusst auf Ihr Ziel zubewegen müssen, ohne langsamer zu werden oder zur Seite auszuweichen. Ich gehe davon aus, dass Ihr Ziel darin besteht, Java-Entwickler zu werden oder Ihr Wissen zu erweitern, wenn Sie bereits Entwickler sind. Wenn ja, beschäftigen wir uns weiterhin mit einer umfangreichen Liste von Interviewfragen für Java-Entwickler. Lass uns weitermachen!

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).

Hier ist ein kleines Beispiel für das Durchlaufen einer Liste und das Entfernen aller ihrer Elemente mithilfe der verschiedenen Iteratormethoden, die wir uns angesehen haben:

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: Dies bedeutet, dass die Elemente erfolgreich entfernt wurden. Sobald Sie einen Iterator erhalten, können Sie eine Methode verwenden, um alle Elemente auf dem Bildschirm anzuzeigen:

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 .

Wie Sie sehen, verfügt dieser Iterator über eine viel interessantere Funktionalität: Er ermöglicht das Gehen in beide Richtungen und bietet erhebliche Freiheit beim Arbeiten mit Elementen. Sie sollten auch wissen, dass, wenn von Iteratoren gesprochen wird, manchmal das Entwurfsmuster selbst gemeint ist.

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 .

Die zweite Sammlungshierarchie ist die Kartenhierarchie , die die folgende Struktur hat: Diese Sammlungshierarchie weist keine Unterteilungen in Untersammlungen auf (da die Kartenhierarchie selbst so etwas wie eine eigenständige Untersammlung ist). Die Standard- Map- Implementierungen sind Hashtable (veraltet), LinkedHashMap und TreeMap . Wenn man in der Praxis nach Collections fragt , meint man meist beide Hierarchien.

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.

Das heißt, die Zeitkomplexität dieser Methode reicht von O(1) bis O(N), je nachdem, wo das Element eingefügt wird. 2. set(<Index>, <Element>) – schreibt ein Element an die angegebene Position in der Liste. Wenn an dieser Position bereits ein Element vorhanden ist, wird es von der Methode überschrieben. Die zeitliche Komplexität dieser Operation beträgt O(1), da sie keine Schiebeoperationen beinhaltet: Wir verwenden lediglich den Index, um die Adresse der Zelle im Array zu berechnen, die eine Komplexität von O(1) hat, und schreiben dann das neue Element . 3. remove(<index>) – entfernt ein Element anhand seines Index im internen Array. Beim Entfernen eines Eintrags, der nicht am Ende der Liste steht, müssen alle Einträge rechts vom gelöschten Eintrag um eine Zelle nach links verschoben werden, um die durch das Löschen entstandene Lücke zu schließen. Dementsprechend ist die zeitliche Komplexität dieselbe wie für add(<Index>, <Element>) , wenn ein Element in der Mitte hinzugefügt wird: O(N/2). Schließlich müssen Sie die Hälfte der Elemente um eine Zelle nach links verschieben. Und wenn wir über den Anfang sprechen, dann O(N). Oder wenn am Ende, dann O(1), da Sie nichts 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.

3. set(<Index>, <Element>) – schreibt ein Element an die angegebene Position in der Liste. Die zeitliche Komplexität dieser Operation liegt zwischen O(1) und O(N/2), wiederum abhängig davon, wie nah sich das neue Element am Kopf, am Ende oder in der Mitte befindet. 4. remove(<index>) – entfernt ein Element aus der Liste, indem es so gestaltet wird, dass das Element vor dem gelöschten Element ( vorheriges ) nun auf das Element nach dem gelöschten Element verweist ( nächstes ). Und umgekehrt, d. h. das Element nach dem gelöschten verweist nun auf das vor dem gelöschten: Dieser Vorgang ist das Gegenteil des Hinzufügens per Index ( add(<Index>, <Element>) ).

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:

1. Die Zelle ist leer – in diesem Fall wird der neue Knotenwert darin gespeichert.
2. 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.

Bei der Suche nach einem Element nach Schlüssel (mit der Methode get(<key>) ) wird der hashCode() des Schlüssels berechnet und dann wird sein Index innerhalb des Arrays mit hash() berechnet . Die resultierende Zahl ist der Index einer Zelle im Tabellenarray , den wir dann durchsuchen, indem wir über Knoten iterieren und den Schlüssel des gewünschten Knotens mit dem Schlüssel des aktuellen Knotens vergleichen. Im Idealfall haben Kartenoperationen eine algorithmische Komplexität von O(1), da wir auf ein Array zugreifen, und wie Sie sich erinnern werden, ist es O(1), unabhängig von der Anzahl der darin enthaltenen Elemente. Aber wir haben es nicht mit dem Idealfall zu tun. Wenn die Zelle nicht leer ist (2) und bereits einige Knoten speichert, wird die algorithmische Komplexität zu O(N) (linear), da nun eine Iteration über die Elemente erforderlich ist, bevor wir die richtige Stelle finden. Ich kann nicht anders, als zu erwähnen, dass ab Java 8 ein Knoten in Form einer einfach verknüpften Liste mit mehr als 8 Elementen (Kollisionen) in einen Binärbaum umgewandelt wird. In diesem Fall ist die algorithmische Komplexität nicht mehr O(N), sondern O(log(N)) – und das ist eine ganz andere Sache, nicht wahr? HashMap ist ein großes Thema und die Leute stellen in Vorstellungsgesprächen gerne Fragen dazu. Daher schlage ich vor, dass Sie es wie Ihre Westentasche kennen. Persönlich hatte ich noch nie ein Interview, in dem keine Fragen zu HashMap enthalten waren . Das ist alles für heute. Fortgesetzt werden...