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

Hallo! Wie viele Stunden dauert es, um ein Meister in etwas zu werden? Ich habe oft so etwas gehört wie: „Um in irgendetwas ein Meister zu werden, muss man 10.000 Stunden damit verbringen.“ Das ist eine einschüchternde Zahl, nicht wahr? Dennoch frage ich mich, ob es wahr ist. Und ich versuche ständig herauszufinden, wie viele Stunden ich bereits in die Beherrschung der Programmierkunst investiert habe. Und wenn ich diese spezielle Grenze von 10.000 Stunden überschreite und Meister werde, werde ich dann den Unterschied spüren? Oder habe ich diese Grenze schon vor langer Zeit überschritten, ohne es zu merken? So oder so muss man nicht so viel Zeit investieren, um Programmierer zu werden. Wichtig ist, dass Sie Ihre Zeit sinnvoll nutzen. Ihr primäres Ziel ist es, ein Vorstellungsgespräch zu bekommen. Und in Vorstellungsgesprächen werden angehende Softwareentwickler zunächst nach der Theorie gefragt, das muss also eine Stärke sein. Tatsächlich besteht Ihre Aufgabe bei der Vorbereitung auf ein Vorstellungsgespräch darin, alle Wissenslücken in der grundlegenden Java-Theorie zu entdecken und diese dann zu schließen. Heute bin ich hier, um Ihnen dabei zu helfen, denn heute werden wir unsere Überprüfung der beliebtesten Interviewfragen fortsetzen. Na, lasst uns weitermachen!

89. Wie unterscheidet sich eine ArrayList von einer LinkedList?

Dies ist neben der Frage nach der internen Struktur einer HashMap eine der beliebtesten Fragen . Ohne sie ist kein Vorstellungsgespräch vollständig, daher sollte Ihnen die Antwort leicht von der Zunge rollen. Neben dem Offensichtlichen (sie haben unterschiedliche Namen) unterscheiden sie sich auch in ihrer inneren Struktur. Zuvor haben wir die interne Struktur von ArrayList und LinkedList besprochen , daher werde ich nicht näher auf die Implementierungsdetails eingehen. Ich möchte Sie nur daran erinnern, dass ArrayList mithilfe eines internen Arrays implementiert wird, dessen Größe gemäß dieser Formel dynamisch zunimmt:

<size of the current array> * 3 / 2 + 1

Darüber hinaus verwendet die Implementierung einer LinkedList eine interne doppelt verknüpfte Liste, d. h. jedes Element hat einen Verweis auf das vorherige und das nächste Element, mit Ausnahme der Elemente am Anfang und Ende der Liste. Interviewer stellen diese Frage gerne so: „Was ist besser, ArrayList oder LinkedList ?“ Ich hoffe, dich zu erwischen. Denn wenn Sie sagen, das eine oder das andere sei besser, dann haben Sie die falsche Antwort gegeben. Stattdessen sollten Sie die spezifische Situation klären, von der Sie sprechen: den Zugriff auf Elemente über den Index oder das Einfügen in die Mitte der Liste. Abhängig von der Antwort können Sie dann erklären, welches besser ist. Ich habe zuvor beschrieben, wie ArrayList und LinkedList in den jeweiligen Situationen funktionieren. Fassen wir dies zusammen, indem wir sie zum Vergleich in eine Reihe stellen: Hinzufügen eines Elements (add)

1. Wenn kein Index angegeben ist, wird für beide Arten von Listen automatisch ein neues Element am Ende hinzugefügt. In einer LinkedList wird das neue Element zum neuen Ende (nur ein Referenzpaar wird neu geschrieben, sodass die algorithmische Komplexität O(1) ist ).

   Die Add-Methode fügt der letzten leeren Zelle im Array ( O(1) ) ein Element hinzu.

2. Das Hinzufügen eines Elements nach Index bedeutet normalerweise, dass es irgendwo in der Mitte der Liste eingefügt wird. In einer LinkedList sucht die Methode zunächst nach der gewünschten Position, indem sie über die Elemente am Ende und am Kopf iteriert ( O(n/2) ) und fügt dann den Wert ein, indem sie die Referenzen der Elemente auf beiden Seiten der Position überschreibt neues Element wird eingefügt ( O(1) ). Die gesamte algorithmische Komplexität dieser Operation beträgt O(n/2) .

   In der gleichen Situation (Hinzufügen nach Index) findet eine ArrayList die gewünschte Position ( O(1) ) und verschiebt dann alle rechts befindlichen Elemente (einschließlich des bereits am angegebenen Index gespeicherten Elements) um eins nach rechts (was erfordert möglicherweise die Erstellung eines neuen internen Arrays und das Kopieren von Elementen dorthin) ( O(n/2) ). Die Gesamtkomplexität beträgt O(n/2) .

3. Das Hinzufügen eines Elements am Anfang einer LinkedList ähnelt dem Hinzufügen eines Elements am Ende: Das neue Element wird zum neuen Kopf ( O(1) ). Für eine ArrayList erfordert dieser Vorgang jedoch das Verschieben aller Elemente nach rechts ( O(n) ).

Die Quintessenz ist, dass die algorithmische Komplexität für eine LinkedList zwischen O(1) und O(n/2) liegt . Eine weitere Beobachtung ist, dass die Einfügung umso schneller erfolgt, je näher sie am Ende oder Anfang der Liste liegt. Für ArrayList reicht die algorithmische Komplexität von O(1) bis O(n) und je näher die Einfügung am Ende der Liste erfolgt, desto schneller ist sie. Festlegen eines Elements (Set) Diese Operation schreibt ein Element an die angegebene Position in der Liste und überschreibt dabei alle vorhandenen Elemente. In einer LinkedList ähnelt dieser Vorgang dem Hinzufügen, da die größte Herausforderung hier darin besteht, die Position des Elements zu finden. Das vorhandene Element wird durch die Aktualisierung eines Referenzpaars überschrieben, sodass wir wiederum eine algorithmische Komplexität haben, die von O(1) bis O(n/2) variiert , abhängig vom Abstand der gewünschten Position vom Ende oder Anfang der Liste. Aber für eine ArrayList findet diese Operation die gewünschte Zelle anhand des Index und schreibt das neue Element dort. Wie die Mengenoperation weist auch die Indexsuche eine algorithmische Komplexität von O(1) auf . Abrufen eines Elements über den Index (get) Das Abrufen eines Elements aus einer LinkedList erfolgt nach demselben Suchprinzip, das auch bei anderen Vorgängen verwendet wird. Die Komplexität hängt vom Abstand vom Ende bzw. Anfang ab, variiert also von O(1) bis O(n/2) . Wie bereits erwähnt, hat das Suchen eines Elements anhand des Index im internen Array für eine ArrayList eine Komplexität von O(1) . Entfernen eines Elements per Index (remove) Für LinkedList gilt das gleiche Prinzip noch einmal. Zuerst wird das Element lokalisiert und dann werden die Referenzen neu geschrieben. Die Nachbarn des gelöschten Elements verweisen nun aufeinander, wodurch die Referenzen auf das gelöschte Element entfernt werden, das anschließend vom Garbage Collector bereinigt wird. Mit anderen Worten, die algorithmische Komplexität ist immer noch dieselbe – sie variiert von O(1) bis O(n/2) . Für ArrayList ähnelt dieser Vorgang eher dem Hinzufügen eines neuen Elements (add). Zuerst findet die Methode das gewünschte Element ( O(1) ), entfernt es und anschließend werden alle rechts liegenden Elemente um einen Schritt nach links verschoben, um die durch die Entfernung entstandene Lücke zu schließen. Das Entfernen eines Elements hat die gleiche algorithmische Komplexität wie die Additionsoperation – von O(1) bis O(n). Je näher das entfernte Element am Ende der Liste liegt, desto geringer ist die algorithmische Komplexität dieser Operation. Und jetzt haben wir alle wichtigen Operationen abgedeckt. Ich möchte Sie daran erinnern, dass Sie beim Vergleich dieser beiden Arten von Listen die konkrete Situation klären müssen, in der sie verwendet werden. Nur dann können Sie die Frage des Interviewers eindeutig beantworten.

90. Wie unterscheidet sich eine ArrayList von einem HashSet?

Wenn wir ArrayList und LinkedList Operation für Operation vergleichen könnten, um festzustellen, welche besser ist, wäre ein solcher Vergleich zwischen ArrayList und HashSet für uns nicht so einfach , da es sich um völlig unterschiedliche Sammlungen handelt. Man kann ein Dessert mit einem anderen vergleichen, aber ein Dessert und ein herzhaftes Gericht zu vergleichen ist eine Herausforderung – sie unterscheiden sich schmerzlich. Dennoch werde ich versuchen, einige der Unterschiede zwischen ihnen aufzuzeigen:

• ArrayList implementiert die List- Schnittstelle, während HashSet die Set- Schnittstelle implementiert .

• Mit ArrayList können Sie über den Index auf ein Element zugreifen: Die Get- Operation hat eine algorithmische Komplexität von O(1) , mit HashSet können Sie jedoch nur über Iteration auf ein gewünschtes Element zugreifen, was zu einer algorithmischen Komplexität im Bereich von O(1) bis O(n) führt .

• ArrayList erlaubt doppelte Elemente. In einem HashSet sind alle Elemente eindeutig: Jeder Versuch, ein Element hinzuzufügen, das bereits in einem HashSet vorhanden ist , schlägt fehl (Duplikate werden durch Hashcode überprüft, daher der Name dieser Sammlung).

• ArrayList wird mithilfe eines internen Arrays implementiert, HashSet wird jedoch mithilfe einer internen HashMap implementiert .

• ArrayList behält die Einfügereihenfolge der Elemente bei, HashSet ist jedoch eine ungeordnete Menge und behält die Reihenfolge der Elemente nicht bei.

• ArrayList erlaubt eine beliebige Anzahl von Nullwerten, aber Sie können einem HashSet nur einen Nullwert hinzufügen (schließlich müssen die Elemente eindeutig sein).

91. Warum gibt es in Java so viele verschiedene Implementierungen dynamischer Arrays?

Das ist eher eine philosophische Frage. Wir könnten uns auch fragen, warum sie so viele neue und vielfältige Technologien entwickeln? Zur Bequemlichkeit. Das Gleiche gilt auch für eine große Anzahl dynamischer Array-Implementierungen. Keine davon kann als die beste oder ideale Umsetzung bezeichnet werden. Jedes hat in bestimmten Situationen seine Vorteile. Unsere Aufgabe ist es, ihre Unterschiede und ihre Stärken/Schwächen zu kennen, um für die jeweilige Situation die am besten geeignete Sammlung nutzen zu können.

92. Warum gibt es in Java so viele verschiedene Schlüsselwertspeicherimplementierungen?

Hier ist die Situation dieselbe wie bei den dynamischen Array-Implementierungen. Es gibt definitiv keine, die allgemein besser ist als die anderen: Jeder hat Stärken und Schwächen. Und natürlich müssen wir ihre Stärken optimal nutzen. Beispiel: Das Concurrent-Paket, das viele Multithread-Klassen enthält, verfügt über eigene Concurrent- Sammlungen. Die ConcurrentHashMap- Klasse hat gegenüber der Standard- HashMap einen Vorteil hinsichtlich der Sicherheit beim Arbeiten mit Daten in einer Multithread-Umgebung, allerdings geht dies auf Kosten einer langsameren Leistung. Und Implementierungen, die nicht in jeder Situation die beste Wahl sind, werden nach und nach nicht mehr verwendet. Beispiel: Hashtable , das ursprünglich als Thread-sichere HashMap gedacht war , wurde vergessen und nicht mehr verwendet, da ConcurrentHashMap beim Arbeiten in einer Multithread-Umgebung sogar besser als Hashtable ist.

93. Wie sortiere ich eine Sammlung von Elementen?

Als Erstes muss gesagt werden, dass die Klasse, die Sammlungselemente darstellt, die Schnittstelle Comparable implementieren muss, die aus der Methode CompareTo besteht . Oder Sie benötigen eine Klasse, die die Comparator- Schnittstelle einschließlich ihrer Vergleichsmethode implementiert . Beide Methoden geben an, wie Objekte eines bestimmten Typs verglichen werden. Dies ist beim Sortieren von entscheidender Bedeutung, da der Sortieralgorithmus verstehen muss, nach welchem ​​Prinzip Elemente verglichen werden sollen. Dies geschieht hauptsächlich durch die direkte Implementierung von Comparable in der Klasse, die Sie sortieren möchten. Die Verwendung von Comparator ist weniger verbreitet. Angenommen, Sie verwenden eine Klasse aus einer Bibliothek und diese implementiert Comparable nicht , Sie müssen jedoch eine Sammlung ihrer Objekte sortieren. Da Sie den Code dieser Klasse nicht ändern können (außer durch Erweitern), können Sie eine Implementierung von Comparator schreiben , die angibt, wie Objekte der Klasse verglichen werden. Und noch ein Beispiel. Wenn Sie Objekte desselben Typs auf unterschiedliche Weise sortieren müssen, können Sie mehrere Comparator- Implementierungen schreiben, um sie in verschiedenen Situationen zu verwenden. In der Regel implementieren viele Out-of-the-Box-Klassen, z. B. String , bereits das Comparable- Interface. Das bedeutet, dass Sie sich keine Gedanken über den Vergleich dieser Klassen machen müssen. Sie können sie einfach nutzen. Der erste und offensichtlichste Weg ist die Verwendung der TreeSet- oder TreeMap- Klasse. Diese Klassen speichern Elemente in sortierter Reihenfolge basierend auf dem von den Klassenelementen implementierten Komparator. Vergessen Sie nicht, dass TreeMap Schlüssel und keine Werte sortiert. Wenn Sie Comparator anstelle von Comparable verwenden , müssen Sie beim Erstellen ein Comparator- Objekt an den Konstruktor der Sammlung übergeben:

TreeSet treeSet = new TreeSet(customComparator);

Aber was ist, wenn Sie eine andere Art von Sammlung haben? Wie sortiert man es? In diesem Fall ist die zweite Möglichkeit der Collections- Dienstprogrammklasse – die Methode sort() – geeignet. Die Methode ist statisch, Sie müssen also lediglich den Namen der Klasse voranstellen und dann die zu sortierende Liste übergeben. Zum Beispiel:

Collections.sort(someList);

Wenn Sie eine Implementierung von Comparator anstelle von Comparable verwenden , müssen Sie diese als zweites Argument übergeben:

Collections.sort(someList, customComparator);

Diese Operation ändert die interne Reihenfolge der Elemente in der übergebenen Liste: Die Liste wird mithilfe des Komparators sortiert. Beachten Sie, dass die übergebene Liste veränderbar sein muss, andernfalls schlägt die Methode fehl und wirft eine UnsupportedOperationException aus . Eine dritte Möglichkeit besteht darin, die sortierte Methode der Stream- Klasse zu verwenden , die die Elemente der Sammlung sortiert. Wenn wir Comparable verwenden :

someList = someList.stream().sorted().collect(Collectors.toList());

Wenn wir Comparator verwenden :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Die vierte Möglichkeit besteht darin, manuell einen Sortieralgorithmus zu implementieren, z. B. Blasensortierung oder Zusammenführungssortierung .

Objektklasse. equal() und hashCode()

94. Geben Sie eine kurze Beschreibung der Object-Klasse in Java.

Im zweiten Teil der Rezension haben wir bereits die Methoden der Object- Klasse besprochen. Hier möchte ich Sie daran erinnern, dass die Object- Klasse ein Vorfahre jeder Klasse in Java ist. Es verfügt über 11 Methoden, die wiederum von allen Klassen geerbt werden.

95. Wofür werden equal() und hashCode() in Java verwendet?

hashCode() ist eine Methode der Object- Klasse, die von allen Klassen geerbt wird. Seine Aufgabe besteht darin, eine Zahl zu generieren, die ein bestimmtes Objekt darstellt. Ein Beispiel für diese Methode in Aktion finden Sie in HashMap , wo sie für Schlüsselobjekte aufgerufen wird, um den lokalen Hashcode abzurufen, der bestimmt, in welchem ​​Bucket (Zelle des internen Arrays) das Schlüssel-Wert-Paar gespeichert wird. Außerdem Diese Methode wird im Allgemeinen in der Methode equal() als eine ihrer Hauptmethoden zur Identifizierung von Objekten verwendet . equal() ist eine Methode der Object- Klasse, deren Aufgabe es ist, Objekte zu vergleichen und festzustellen, ob sie gleich sind. Diese Methode wird überall dort verwendet, wo wir Objekte vergleichen müssen, da der Standard - Vergleichsoperator == nicht für Objekte geeignet ist, da er nur Objektreferenzen vergleicht.

96. Erzählen Sie uns etwas über den Vertrag zwischen equal() und hashCode() in Java?

Lassen Sie mich zunächst sagen, dass die Methoden equal() und hashCode() korrekt überschrieben werden müssen, damit sie ordnungsgemäß funktionieren. Ihre neuen Implementierungen müssen diesen Regeln folgen:

• Identische Objekte, für die „equals“ den Wert „true“ zurückgibt, müssen die gleichen Hashcodes haben.
• Objekte mit denselben Hash-Codes sind nicht unbedingt gleich.

Jetzt scheint ein guter Ort zu sein, um bis zum nächsten Teil der Rezension innezuhalten!