Analyse von Fragen und Antworten aus Interviews für 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 aufwenden.“ Eine beängstigende Zahl, nicht wahr? Allerdings frage ich mich, ob das wahr ist? Und ich versuche ständig herauszufinden, wie viele Stunden ich bereits in die Beherrschung der Programmierkunst investiert habe. Und wenn ich diese geschätzten 10.000 Stunden erreiche und Meister werde, werde ich dann diesen Unterschied spüren? Oder bin ich schon vor langer Zeit darüber gestiegen, ohne es zu merken? Um Programmierer zu werden, muss man auf die eine oder andere Weise nicht so viel Zeit investieren. Die Hauptsache ist, es mit Bedacht einzusetzen. Ihr oberstes Ziel ist es, das Vorstellungsgespräch zu bestehen. Und bei Vorstellungsgesprächen für Neueinsteiger wird als Erstes nach der Theorie gefragt, also muss man darin stark sein. Eigentlich besteht Ihre Aufgabe bei der Vorbereitung auf das Vorstellungsgespräch darin, alle Ihre Lücken in der grundlegenden Theorie eines Java-Entwicklers zu entdecken und diese mit Wissen zu schließen. Und heute werde ich Ihnen in dieser Angelegenheit helfen, denn ich bin hier, um die am häufigsten gestellten Fragen weiter zu analysieren. Also lasst uns weitermachen!

89. Wie unterscheidet sich ArrayList von LinkedList?

Dies ist neben der Frage nach der internen Struktur von HashMap eine der beliebtesten Fragen . Kein einziges Interview ist ohne sie vollständig, und deshalb sollte die Antwort darauf „von Ihren Zähnen abprallen“. Neben den offensichtlichen – unterschiedlichen Namen – unterscheiden sie sich auch in der inneren Struktur. Zuvor haben wir die interne Struktur von ArrayList und LinkedList untersucht , daher werde ich nicht auf die Details ihrer Implementierung eingehen. Ich möchte Sie nur daran erinnern, dass ArrayList auf der Grundlage eines internen Arrays implementiert wird, das nach Bedarf gemäß der Formel erhöht wird:

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

Gleichzeitig wird LinkedList basierend auf einer internen doppelt verknüpften Liste implementiert, d. h. jedes Element hat einen Link zum vorherigen und nächsten, mit Ausnahme von Werten, die den Anfang/das Ende der Liste darstellen. Die Leute stellen diese Frage gerne im Format: „Was ist besser – ArrayList oder LinkedList ?“ und hoffen, Sie zu erwischen. Wenn Sie auf eine davon als Antwort verweisen, ist es schließlich die falsche Antwort. Stattdessen sollten Sie klären, um welche konkrete Situation es sich handelt – Indexzugriff oder Einfügen in die Mitte einer Liste. Abhängig von der Antwort können Sie Ihre Wahl begründen. Ich habe zuvor beschrieben, wie ArrayList und LinkedList in der einen oder anderen Situation funktionieren. Fassen wir dies zusammen, indem wir sie zum Vergleich auf derselben Seite zusammenfassen: Hinzufügen eines Elements (Hinzufügen)

1. Добавление нового Element без указания индекса Wie местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление Element по индексу Wie правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление Element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Fazit: In LinkedList wird die algorithmische Komplexität zwischen O(1) und O(n/2) liegen . Das heißt, je näher die Einfügung am Ende oder Anfang der Liste erfolgt, desto schneller erfolgt sie. Gleichzeitig reicht es für ArrayList von O(1) bis O(n) : Je näher die Einfügung am Ende der Liste erfolgt, desto schneller ist sie. Setzen eines Elements (Set) Diese Operation schreibt ein Element an die angegebene Position in der Liste und überschreibt das vorherige, falls vorhanden. In LinkedList ähnelt dieser Vorgang dem Hinzufügen, weil Die größte Schwierigkeit besteht hier darin, das Element zu finden. Das Umschreiben eines Elements erfolgt durch Umschreiben eines Verknüpfungspaars, sodass die algorithmische Komplexität auch hier je nach Abstand der Position vom Ende oder Anfang der Liste zwischen O(1) und O(n/2) liegt. Zu diesem Zeitpunkt wird die für diesen Indexvorgang erforderliche Zelle in der ArrayList gefunden und ein neues Element wird in sie geschrieben. Die Indexsuche weist wie diese Operation eine algorithmische Komplexität von O(1) auf . Nehmen Sie ein Element nach Index (get) . In LinkedList erfolgt die Aufnahme eines Elements nach dem gleichen Prinzip wie die Suche nach anderen Operationen – abhängig von der Entfernung vom Ende oder Anfang, d. h. von O(1) nach O(n/2) . In ArrayList hat das Finden eines Elements in einem Array anhand des Index, wie ich bereits sagte, eine Komplexität von O(1) . Ein Element nach Index entfernen (remove) Bei LinkedList funktioniert das Funktionsprinzip auch hier: Zuerst wird das Element gefunden, und dann werden die Links überschrieben – die Nachbarn des Elements beginnen, aufeinander zu verweisen, wodurch Verweise auf dieses Element verloren gehen werden anschließend vom Garbage Collector gelöscht. Das heißt, die algorithmische Komplexität ist immer noch dieselbe – von O(1) bis O(n/2) . Für ArrayList ähnelt dieser Vorgang eher dem Vorgang des Hinzufügens eines neuen Elements (add). Zuerst wird das gewünschte Element gefunden - O(1) , dann wird es entfernt und alle Elemente, die sich rechts davon befanden, werden um eine Einheit nach links verschoben, um die entstandene Lücke zu schließen. Die Löschoperation hat die gleiche algorithmische Komplexität wie die Additionsoperation – von O(1) bis O(n) . Je näher die Löschung am Ende der Liste erfolgt, desto geringer ist die algorithmische Komplexität. Eigentlich waren das alles die Haupteinsätze. Ich möchte Sie daran erinnern: Beim Vergleich dieser beiden Listen müssen Sie klären, um welche konkrete Situation es sich handelt, und können dann die gestellte Frage eindeutig beantworten.

90. Wie unterscheidet sich ArrayList von HashSet?

Wenn ArrayList und LinkedList hinsichtlich der Operationen verglichen werden könnten – was besser ist –, dann ist es nicht so einfach, ArrayList mit HashSet zu vergleichen, da es sich um völlig unterschiedliche Sammlungen handelt. Man kann ein süßes Gericht mit einem anderen vergleichen, aber mit einem Fleischgericht klappt es – die sind zu unterschiedlich. Ich werde jedoch versuchen, einige Unterschiede zwischen ihnen aufzuzeigen:

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

• In ArrayList ist der Zugriff über den Elementindex möglich: Die Get- Operation hat eine algorithmische Komplexität von O(1) und in HashSet kann das erforderliche Element nur durch rohe Gewalt abgerufen werden, und zwar von O(1) bis O(n). ;

• ArrayList erlaubt doppelte Elemente. In einem HashSet sind alle Elemente eindeutig: Das Hinzufügen eines Elements zu einem HashSet , dessen Analogon bereits in der Sammlung vorhanden ist, funktioniert nicht (Duplikate werden mithilfe von Hashcode überprüft, daher der Name dieser Sammlung);

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

• Eine ArrayList behält die Einfügereihenfolge der Elemente bei, während ein HashSet eine ungeordnete Menge ist und die Reihenfolge der Elemente nicht beibehält;

• ArrayList erlaubt eine beliebige Anzahl leerer Werte (null), in ein HashSet kann nur ein Nullwert eingefügt werden (schließlich die Eindeutigkeit der Elemente).

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

Nun, das ist eher eine philosophische Frage. Warum entwickeln sie so viele verschiedene neue Technologien? Für Komfort. Tatsächlich ist es bei einer großen Anzahl dynamischer Array-Implementierungen dasselbe. Keines davon kann als das Beste oder Ideal bezeichnet werden. Jeder hat in einer bestimmten Situation einen Vorteil. Und unsere Aufgabe ist es, ihre Unterschiede, ihre Stärken/Schwächen zu kennen, um das am besten geeignete in der richtigen Situation einsetzen zu können.

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

Hier ist die Situation dieselbe wie bei dynamischen Array-Implementierungen. Es gibt niemanden, der der Beste ist: Jeder hat Stärken und Schwächen. Und natürlich müssen wir unsere Stärken optimal nutzen. Beispiel: Das Concurrent-Paket, das viele Multithread-Technologien enthält, verfügt über eigene Concurrent- Sammlungen. Dieselbe ConcurrentHashMap hat im Vergleich zu einer regulären HashMap einen Vorteil in Bezug auf die Sicherheit der Multithread-Arbeit mit Daten , verliert jedoch in einer Umgebung ohne Multithread an Geschwindigkeit. Nun, Implementierungen, die nicht in jeder Situation die stärksten sind, werden nach und nach nicht mehr verwendet. Beispiel: Hashtable , das ursprünglich als threadsichere HashMap gedacht war , aber ConcurrentHashMap übertrifft es in einer Multithread-Umgebung, und schließlich geriet Hashtable in Vergessenheit und wurde nicht mehr verwendet.

93. Wie sortiere ich eine Sammlung von Elementen?

Als Erstes ist zu sagen, dass die Sammlungselementklasse die Comparable- Schnittstelle und ihre CompareTo- Methode implementieren muss . Oder Sie benötigen eine Klasse, die Comaprator mit seiner Vergleichsmethode implementiert . Mehr darüber können Sie in diesem Beitrag lesen . Beide Methoden geben an, wie Objekte eines bestimmten Typs verglichen werden sollen. Beim Sortieren ist dies von entscheidender Bedeutung, da Sie das Prinzip verstehen müssen, nach dem Elemente verglichen werden können. Der wichtigste Weg hierfür ist die Implementierung von Comparable direkt in der Klasse, die Sie sortieren möchten. Gleichzeitig ist die Verwendung von Comparator seltener. Nehmen wir an, Sie verwenden eine Klasse aus einer Bibliothek, die keine Comparable- Implementierung hat , aber Sie müssen sie irgendwie sortieren. Ohne den Code dieser Klasse ändern zu können (außer durch Erweiterung), können Sie eine Implementierung von Comparator schreiben , in der Sie angeben, nach welchem ​​Prinzip Sie Objekte dieser Klasse vergleichen möchten. Und noch ein Beispiel. Nehmen wir an, Sie benötigen unterschiedliche Prinzipien zum Sortieren von Objekten desselben Typs und schreiben daher mehrere Komparatoren , die Sie in unterschiedlichen Situationen verwenden. In der Regel implementieren viele standardmäßige Klassen bereits die Comparable- Schnittstelle – denselben String . Wenn Sie sie verwenden, müssen Sie sich eigentlich keine Gedanken darüber machen, wie Sie sie vergleichen können. Man nimmt sie einfach und benutzt sie. Der erste und naheliegendste Weg ist die Verwendung einer Sammlung vom Typ TreeSet oder TreeMap , die die Elemente in bereits sortierter Reihenfolge gemäß dem Elementklassenkomparator speichert. Denken Sie daran, dass TreeMap Schlüssel sortiert, aber keine Werte. Wenn Sie die Comparator- Implementierung anstelle von Comparable verwenden , müssen Sie deren Objekt bei der Erstellung an den Sammlungskonstruktor übergeben:

TreeSet treeSet = new TreeSet(customComparator);

Aber was ist, wenn Sie eine andere Art von Sammlung haben? Wie sortiere ich es? In diesem Fall eignet sich die zweite Methode der Dienstprogrammklasse Collections – die Methode sort() . Da es statisch ist, benötigen Sie lediglich den Namen der Klasse und eine Methode, an die die erforderliche Liste übergeben wird. Zum Beispiel:

Collections.sort(someList);

Wenn Sie Comparable nicht verwenden , sondern eine Implementierung von Comparator , müssen Sie diese als zweiten Parameter übergeben:

Collections.sort(someList, customComparator);

Dadurch ändert sich die interne Reihenfolge der Elemente der übergebenen Liste: Sie werden nach dem Elementkomparator sortiert. Ich stelle fest, dass die übertragene Liste der Elemente veränderbar sein muss, d.h. veränderbar, andernfalls funktioniert die Methode nicht und es wird eine UnsupportedOperationException ausgelöst . Als dritte Möglichkeit können Sie die Stream- Sortieroperation verwenden , die die Elemente der Sammlung sortiert, wenn die Comparable- Implementierung verwendet wird :

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

wenn Komparator :

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

Weitere Informationen zu Stream finden Sie in diesem Artikel . Die vierte Methode besteht darin, die Sortierung manuell zu implementieren, z. B. Blasensortierung oder Zusammenführungssortierung .

ClassObject. Gleicht und HashCode

94. Geben Sie eine kurze Beschreibung des Klassenobjekts in Java

Im zweiten Teil der Analyse haben wir bereits über die Methoden der Object- Klasse gesprochen , und ich möchte Sie daran erinnern, dass die Object- Klasse der Vorläufer aller Klassen in Java ist. Es verfügt über 11 Methoden, die dementsprechend von allen Klassen geerbt werden. Informationen zu allen 11 Methoden finden Sie im zweiten Teil der Diskussion.

95. Wofür werden Equals 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 die Verwendung dieser Methode ist ihre Verwendung in einer HashMap für ein Schlüsselobjekt, um den lokalen Hashcode weiter zu bestimmen, der die Zelle des internen Arrays (Bucket) bestimmt, in dem das Paar gespeichert wird. Wir haben in Teil 9 der Analyse ausführlich über die Arbeit von HashMap gesprochen , daher werden wir uns nicht zu sehr damit befassen. Außerdem wird diese Methode in der Regel in der Methode equal() als eines ihrer Hauptwerkzeuge zur Bestimmung der Identität von Objekten verwendet. equal() ist eine Methode der Object- Klasse , deren Aufgabe es ist, Objekte zu vergleichen und festzustellen, ob sie gleich sind oder nicht. Diese Methode wird überall dort verwendet, wo wir Objekte vergleichen müssen, da der übliche Vergleich mit == für Objekte nicht geeignet ist, weil vergleicht nur Links zu ihnen.

96. Erzählen Sie uns etwas über den Vertrag zwischen Equals und HashCode in Java?

Das erste, was ich sagen möchte, ist, dass die Methoden equal() und hashCode() korrekt überschrieben werden müssen, damit sie ordnungsgemäß funktionieren. Danach müssen sie die Regeln befolgen:

• identische Objekte, für die ein Vergleich über „equals“ „ true“ zurückgibt, müssen identische Hash-Codes haben ;
• Objekte mit denselben Hash-Codes sind möglicherweise nicht immer gleich.

An dieser Stelle machen wir eine Pause bis zum nächsten Teil der Analyse!