Analyse von Fragen und Antworten aus Interviews für Java-Entwickler. Teil 9

Feuerwerk! Programmierer zu sein ist nicht einfach. Man muss ständig lernen, immer etwas Neues lernen. Aber wie in jedem anderen Geschäft ist es am schwierigsten, anzufangen und den ersten Schritt in Richtung Ihres Ziels zu machen. Und da Sie auf dieser Seite sitzen und diesen Artikel lesen, haben Sie den ersten Schritt getan. Das bedeutet, dass Sie sich jetzt gezielt Ihrem Ziel nähern müssen, ohne unterwegs langsamer zu werden oder abzuschalten. Wenn ich das richtig verstehe, besteht Ihr Ziel darin, Java-Entwickler zu werden oder Ihr Wissen zu erweitern, wenn Sie einer sind. Wenn ja, dann sind Sie hier genau richtig, denn wir werden weiterhin eine umfangreiche Liste von über 250 Interviewfragen für Java-Entwickler analysieren. Lass uns weitermachen!

Sammlungen

84. Erzählen Sie uns etwas über Iteratoren und ihre Verwendung

Sammlungen sind eines der Lieblingsthemen in jedem Java-Entwicklerinterview, und wenn es um die Sammlungshierarchie geht, sagen Kandidaten oft, dass sie mit der Sammlungshierarchie beginnt . Dies ist jedoch nicht wahr, da sich über dieser Schnittstelle eine weitere befindet – Iterable . Diese Schnittstelle stellt die Methode iterator() dar, mit der Sie ein Iterator- Objekt für die aktuelle Sammlung aufrufen können . Und was genau ist dieses Iterator- Objekt ? Ein Iterator ist ein Objekt, das die Möglichkeit bietet, sich durch eine Sammlung zu bewegen und über Elemente zu iterieren, ohne dass der Benutzer die Implementierung einer bestimmten Sammlung kennen muss. Das heißt, dies ist eine Art Hinweis auf die Elemente der Sammlung, der sozusagen auf eine bestimmte Stelle darin blickt. Der Iterator verfügt über die folgenden Methoden:

• hasNext() – gibt true zurück , wenn sich ein Element nach dem Zeiger befindet (mit dieser Methode können Sie herausfinden, ob das Ende der Sammlung erreicht wurde);
• next() – gibt das nächste Element nach dem Zeiger zurück. Wenn keine vorhanden ist, wird eine NoSuchElementException ausgelöst . Das heißt, bevor Sie diese Methode verwenden, ist es besser, sicherzustellen, dass das Element vorhanden ist – mit hasNext() ;
• remove() – entfernt das letzte Element, das mit der next()- Methode aus der Sammlung empfangen wurde . Wenn next() vor dem Aufruf von remove() noch nie aufgerufen wurde , wird eine Ausnahme ausgelöst – IllegalStateException ;
• forEachRemaining(<Consumer>) – führt die übergebene Aktion mit jedem Element der Sammlung aus (die Methode erschien in Java 8).

Hier ist ein kleines Beispiel für das Durchlaufen einer Liste und das Entfernen aller ihrer Elemente mithilfe der besprochenen Iteratormethoden:

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 das Entfernen von Elementen erfolgreich war. Sobald wir einen Iterator hatten, konnten wir eine Methode verwenden, um alle Elemente auf dem Bildschirm auszugeben:

iterator.forEachRemaining(x -> System.out.print(x));

Danach wäre der Iterator jedoch für die weitere Verwendung unbrauchbar, da er die gesamte Liste durchlaufen würde und ein regulärer Iterator keine Methoden zum Zurückverfolgen hat. Hier nähern wir uns schrittweise LinkedList , nämlich seiner listIterator()- Methode , die einen modernisierten Iteratortyp zurückgibt – ListIterator . Neben den regulären (Standard-)Iteratormethoden gibt es hier noch weitere:

• add(<Element>) – fügt ein neues Element in die Liste ein;
• hasPrevious() – gibt true zurück , wenn sich ein Element vor dem Zeiger befindet (unabhängig davon, ob es ein vorheriges Element gibt);
• nextIndex() – gibt den Index in der Liste des nächsten Elements nach dem Zeiger zurück;
• previous() – gibt das vorherige Element zurück (bis zum Zeiger);
• previousIndex() – gibt den Index des vorherigen Elements zurück;
• set(<Element>) – Ersetzt das letzte Element, das von den Methoden next() oder previous() zurückgegeben wird .

Wie Sie sehen, ist die Funktionalität dieses Iterators viel interessanter: Er ermöglicht die Bewegung in beide Richtungen und macht Ihre Hände beim Arbeiten mit Elementen frei. Wenn man von Iteratoren spricht, meint man manchmal auch das Muster selbst. Um Ärger zu vermeiden und überzeugend darüber zu sprechen, lesen Sie diesen Artikel über das Iterator-Muster .

85. Wie ist die Sammlungshierarchie im Java Collection Framework?

In Java gibt es zwei Sammlungshierarchien. Die erste Hierarchie ist die Collection- Hierarchie selbst mit folgender Struktur: Sie ist wiederum in folgende Untersammlungen unterteilt:

• Set ist eine Schnittstelle, die eine solche Datenstruktur als eine Menge beschreibt , die ungeordnete, eindeutige (sich nicht wiederholende) Elemente enthält. Die Schnittstelle verfügt über Standardimplementierungen – TreeSet , HashSet und LinkedHashSet .
• List ist eine Schnittstelle, die eine Datenstruktur beschreibt, die eine geordnete Folge von Objekten speichert. In einer Liste enthaltene Instanzen können über ihren Index in diese Sammlung eingefügt und gelöscht werden (analog zu einem Array, jedoch mit dynamischer Größenänderung). Die Schnittstelle verfügt über Standardimplementierungen: ArrayList , Vector ( gilt als veraltet und wird nicht tatsächlich verwendet ) und LinkedList .
• Queue ist eine Schnittstelle, die eine Datenstruktur beschreibt, die Elemente in Form einer Warteschlange speichert, die der FIFO-Regel „First In First Out“ folgt . Die Schnittstelle verfügt über die folgenden Standardimplementierungen: LinkedList (ja, sie implementiert auch Queue ) und PriotityQueue .

Die zweite Sammlungshierarchie ist Map , die folgende Struktur hat: In dieser Sammlung gibt es keine Unterteilungen in Untersammlungen (da die Map- Hierarchie selbst so etwas wie eine Untersammlung ist, aber separat liegt). Standard- Map- Implementierungen sind Hashtable (gilt als veraltet), LinkedHashMap und TreeMap . Eigentlich sind bei der Frage nach Collection meist beide Hierarchien gemeint.

86. Wie ist die interne Struktur einer ArrayList?

ArrayList ähnelt einem Array, kann jedoch dynamisch erweitert werden. Was bedeutet das? Tatsache ist, dass ArrayList auf der Grundlage eines regulären Arrays funktioniert, d. h. es speichert Elemente in einem internen Array (seine Standardgröße beträgt 10 Zellen). Wenn das interne Array voll ist, wird ein neues Array erstellt, dessen Größe durch die Formel bestimmt wird:

<размерТекущегоМассива> * 3 / 2  + 1

Das heißt, wenn die Größe unseres Arrays 10 beträgt, beträgt die Größe des neuen Arrays: 10 * 3 / 2 + 1 = 16. Als nächstes werden alle Werte aus dem ersten (alten) Array mit dem in dieses kopiert native System.arraycopy ()- Methode und das erste Array wird gelöscht. Tatsächlich wird auf diese Weise die dynamische Erweiterbarkeit von ArrayList implementiert . Schauen wir uns die am häufigsten verwendeten ArrayList- Methoden an : 1. add(<Elelement>) – fügt ein Element am Ende des Arrays (zur letzten leeren Zelle) hinzu und prüft zunächst, ob in diesem Array Platz ist. Ist es nicht vorhanden, wird ein neues Array erstellt, in das die Elemente kopiert werden. Die logarithmische Komplexität dieser Operation beträgt O(1). Es gibt eine ähnliche Methode – add(<Index>,<Elelement>) . Es fügt ein Element nicht am Ende der Liste (Array) hinzu, sondern an einer bestimmten Zelle mit dem Index, der als Argument angegeben wurde. In diesem Fall unterscheidet sich die logarithmische Komplexität je nachdem, wo sie hinzugefügt wird:

• Wenn dies ungefähr der Anfang der Liste war, liegt die logarithmische Komplexitä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 - O(N/2), weil Wir müssen nur die Hälfte der Listenelemente um eine Zelle nach rechts verschieben.

Das heißt, die logarithmische Komplexität dieser Methode reicht von O(N) bis O(1), je nachdem, wo das Element eingefügt wird. 2. set(<Index>,<Elelement>) – schreibt ein Element an die angegebene Position in der Liste. Wenn an dieser Position bereits ein Element vorhanden ist, wird es überschrieben. Die logarithmische Komplexität dieser Operation beträgt O(1), da es keine Verschiebungen gibt: nur die Suche nach dem Index im Array, das, wie wir uns erinnern, eine Komplexität von O(1) hat, und das Schreiben des Elements. 3. remove(<index>) – Entfernen eines Elements anhand seines Index im internen Array. Wenn Sie ein Element löschen, das nicht am Ende der Liste steht, müssen Sie alle Elemente rechts davon um eine Zelle nach links verschieben, um die Lücke zu schließen, die nach dem Löschen des Elements entsteht. Daher ist die logarithmische Komplexität dieselbe wie bei add(<Index>,<Elelement>) , wenn sich das Element in der Mitte befand – O(N/2) –, da Sie die Hälfte der Elemente um eins nach links verschieben müssen. Dementsprechend, wenn es am Anfang war - O(N). Nun, wenn es am Ende O(1) ist, besteht keine Notwendigkeit, etwas zu verschieben. Für diejenigen, die tiefer in dieses Thema eintauchen möchten, hinterlasse ich diesen Link zu einem Artikel mit einer Analyse der ArrayList- Klasse .

87. Wie ist die interne Struktur von LinkedList?

Wenn ArrayList Elemente in einem internen Array enthält, liegt LinkedList in Form einer doppelt verknüpften Liste vor. Dies bedeutet, dass jedes Element einen Link zum vorherigen Element ( previous ) und zum nächsten ( next ) enthält. Das erste Element hat keinen Link zum vorherigen (es ist das erste), wird aber als Kopf der Liste betrachtet und die LinkedList hat einen direkten Link dazu. Das letzte Element hat tatsächlich kein nächstes Element, es ist das Ende der Liste und daher gibt es in der LinkedList selbst einen direkten Link dazu . Daher beträgt die logarithmische Komplexität des Zugriffs auf den Anfang oder das Ende einer Liste O(1). Wenn in ArrayList die Liste wuchs, vergrößerte sich auch das interne Array, aber hier geschieht alles einfacher – beim Hinzufügen eines Elements ändern sich einfach ein paar Links. Schauen wir uns einige der am häufigsten verwendeten LinkedlList- Methoden an : 1. add(<Elelement>) – Hinzufügen am Ende der Liste, d. h. Nach dem letzten Element (5) wird als nächstes ein Link zum neuen Element eingefügt . Das neue Element verfügt wie das vorherige Element über einen Link zum letzten (5) . Die logarithmische Komplexität einer solchen Operation beträgt O(1), da nur ein Link zum letzten Element erforderlich ist. Wie Sie sich erinnern, hat das Ende einen direkten Link von LinkedList und die logarithmische Komplexität des Zugriffs darauf ist minimal. 2. add(<Index>,<Elelement>) – Hinzufügen eines Elements nach Index. Wenn Sie beispielsweise ein Element in die Mitte einer Liste einfügen, werden zunächst die Elemente aus Kopf und Ende (auf beiden Seiten) iteriert, bis die gewünschte Stelle gefunden ist. Wenn wir ein Element zwischen dem dritten und vierten einfügen möchten (in der Abbildung oben), dann zeigt bei der Suche nach der richtigen Stelle bereits der nächste Link des dritten Elements auf das neue. Beim neuen Link verweist der vorherige Link auf den dritten. Dementsprechend zeigt der Link des vierten Elements ( vorheriges ) bereits auf das neue Element und der nächste Link des neuen Elements zeigt auf das vierte Element: Die logarithmische Komplexität dieser Methode hängt vom Index ab, der dem neuen Element gegeben wird:

• wenn es nahe am Kopf oder Ende liegt, nähert es sich O(1), da es eigentlich nicht notwendig ist, über die Elemente zu iterieren;
• wenn es nahe an der Mitte liegt, dann O(N/2) – die Elemente von Kopf und Ende werden gleichzeitig sortiert, bis das erforderliche Element gefunden wird.

3. set(<Index>,<Elelement>) – schreibt ein Element an die angegebene Position in der Liste. Die logarithmische Komplexität dieser Operation reicht von O(1) bis O(N/2), wiederum abhängig davon, wie nah sich das Element am Kopf, Schwanz oder in der Mitte befindet. 4. remove(<index>) – entfernt ein Element aus der Liste, wodurch im Wesentlichen das Element, das vor dem entfernten Element kommt ( vorheriger ), auf das Element verweist, das nach dem entfernten Element kommt ( nächstes ). Und umgekehrt: So dass das Element, das nach dem zu löschenden Element kommt, auf das Element verweist, das vor dem zu löschenden Element kommt: Das Ergebnis ist ein zum Hinzufügen durch Index umgekehrter Prozess ( add(<Index>,<Elelement>) ). Für diejenigen, die mehr über die interne Struktur von LinkedList erfahren möchten , empfehle ich die Lektüre dieses Artikels .

88. Wie ist die interne Struktur einer HashMap?

Vielleicht eine der beliebtesten Fragen bei Vorstellungsgesprächen mit einem Java-Entwickler. HashMap v funktioniert mit Schlüssel-Wert- Paaren . Wie werden sie im HashMapv selbst gespeichert ? Innerhalb der HashMap gibt es ein 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 (wenn LOAD_FACTOR erreicht ist – ein bestimmter Prozentsatz der Fülle, standardmäßig ist es 0,75 ). Jeder Knoten speichert einen Hash des Schlüssels, einen Schlüssel, einen Wert und einen Link zum nächsten Element: Tatsächlich bedeutet „Link zum nächsten Element“, dass wir es mit einer einfach verknüpften Liste zu tun haben, in der jedes Element einen Link zu enthält der Nächste. Das heißt, HashMap speichert Daten in einem Array einfach verknüpfter Listen. Aber ich möchte gleich anmerken: Wenn eine Zelle des Tabellenarrays einen Link zu einer ähnlichen einfach verknüpften 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 . Zunächst wird der hachCode() des Schlüssels übernommen. Damit Hashmap ordnungsgemäß funktioniert , müssen Sie Klassen, in denen diese Methode überschrieben ist, als Schlüssel verwenden. Dieser Hash-Code wird dann in der internen Methode hash() verwendet, um die Zahl innerhalb der Größe des Tabellenarrays zu ermitteln . Anschließend wird mit der empfangenen Nummer auf eine bestimmte Zelle des Tabellenarrays zugegriffen . Hier haben wir zwei Fälle:

1. Die Zelle ist leer – der neue Knotenwert wird darin gespeichert .
2. Die Zelle ist nicht leer – der Wert der Schlüssel wird verglichen. Wenn sie gleich sind, überschreibt der neue Node- Wert den alten, wenn sie nicht gleich sind, wird auf das nächste Element zugegriffen und mit seinem Schlüssel verglichen ... Und so weiter, bis der neue Wert einen alten überschreibt oder das Ende erreicht einfach verknüpfte Liste und wird dort als letztes Element gespeichert.

Bei der Suche nach einem Element anhand des Schlüssels ( Methode get(<key>) ) wird der HashCode des Schlüssels berechnet, dann wird sein Wert innerhalb des Arrays mit hash() berechnet und mit der resultierenden Zahl wird die Zelle des Tabellenarrays gefunden , bei dem die Suche bereits durch das Aufzählen von Knoten und den Vergleich des Schlüssels des gewünschten Knotens mit dem Schlüssel des aktuellen Knotens durchgeführt wird. Operationen in Map haben im Idealfall eine algorithmische Komplexität von O(1), da sie auf ein Array zugreifen, und wie Sie sich erinnern, haben Operationen auf einem Array unabhängig von der Anzahl der Elemente eine Komplexität von O(1). . Aber das ist ideal. Wenn die verwendete Array-Zelle nicht leer ist (2) und dort bereits einige Knoten vorhanden sind, wird die algorithmische Komplexität zu linearem O(N), da nun eine Iteration über die Elemente erforderlich ist, bevor die richtige Stelle gefunden wird. Ich kann nicht anders, als Folgendes zu erwähnen: Wenn ein einfach verknüpfter Listenknoten ab Java 8 mehr als 8 Elemente (Kollisionen) aufweist, wird er zu einem Binärbaum. In diesem Fall ist die algorithmische Komplexität nicht mehr O(N), sondern O(log(N)) – das ist eine andere Sache, nicht wahr? HashMap ist ein großes Thema und in Interviews werden gerne Fragen dazu gestellt. Daher rate ich Ihnen, es im Detail zu verstehen (damit es von Ihren Zähnen abprallt). Ich persönlich hatte noch kein Vorstellungsgespräch ohne HashMap- Fragen . In diesem Artikel finden Sie einen detaillierten Einblick in HashMap . Das ist alles für heute, Fortsetzung folgt...