Was sie bei einem Vorstellungsgespräch fragen könnten: Datenstrukturen in Java. Teil 2

TEIL 1 Jetzt sprechen wir über die Grundlagen, die jeder Java-Entwickler kennen sollte. Über das klassische Wissen, mit dem alles beginnt. Heute möchte ich auf eines der grundlegenden Themen jedes Interviews eingehen – Datenstrukturen in Java . Anstatt also um den heißen Brei herumzureden, fangen wir an. Sehen Sie sich die Fortsetzung der Liste der Fragen an, die Ihnen zu diesem Thema während eines Vorstellungsgesprächs gestellt werden könnten.

6. Erzählen Sie uns etwas über List

Liste ist eine Schnittstelle, die eine geordnete Struktur von Objekten darstellt, die als Liste bezeichnet wird. Der „Trick“ dieser Struktur besteht darin, dass die in der Liste enthaltenen Elemente über den Index, also den internen Bezeichner der Liste , eingefügt, geändert oder gelöscht werden können . Mit anderen Worten bedeutet Index: „Wie viele Elemente befinden sich vom Anfang der Liste an.“ Das erste Listenelement hat den Index 0, das zweite den Index 1 und so weiter. Das fünfte Element ist also vier Elemente vom Anfang der Liste entfernt. Wie oben erwähnt, ist die Reihenfolge, in der Elemente zu einer Liste hinzugefügt werden, wichtig. Aus diesem Grund wird die Datenstruktur als Liste bezeichnet . Wir listen für diese Struktur einzigartige Methoden auf, die auf die Arbeit mit Elementen nach Index abzielen:

• get – gibt das Element an der angegebenen Position zurück (nach Indexwert),
• entfernen – entfernt das Element an der angegebenen Position,
• set – ersetzt das Element an der angegebenen Position durch das in der Methode angegebene Element.

Die Hauptimplementierungen sind ArrayList und LinkedList . Wir werden etwas später mehr darüber sprechen. Vector ist eine Thread-sichere Liste, sodass jede Methode in dieser Klasse synchronisiert ist. Bedenken Sie jedoch, dass Sie eine ganze Abfolge von Vorgängen synchronisieren, wenn Sie einige Listenaktionen sichern möchten. Und die Synchronisierung einzelner Vorgänge ist sowohl weniger sicher als auch viel langsamer. Natürlich hat Vector auch einen Sperraufwand, auch wenn Sie die Sperre nicht benötigen. Daher gilt diese Klasse mittlerweile als veraltet und wird nicht mehr verwendet. Übrigens: ArrayList ähnelt Vector , verwendet jedoch keine Sperrung und wird daher überall verwendet. Stack ist eine Unterklasse der Vector- Klasse mit einem Standardkonstruktor und allen Methoden der Vector- Klasse sowie einigen eigenen (wir werden später darüber sprechen). Als Beispiel können Sie sich den Vorgang als einen Stapel von Ordnern mit Dokumenten vorstellen. Sie legen einen Ordner oben auf den Stapel und können diese Ordner nur in umgekehrter Reihenfolge, beginnend von oben, aufnehmen. Tatsächlich handelt es sich hierbei um einen LIFO -Mechanismus , d. h. Last In First Out : Der Letzte, der kommt, ist der Erste, der geht. Der Stack implementiert seine eigenen Methoden:

• push – fügt das übergebene Element oben im Stapel hinzu;
• peek – gibt das Element zurück, das sich oben im Stapel befindet;
• pop – gibt auch das Element zurück, das sich oben im Stapel befindet, entfernt es jedoch;
• empty – prüft, ob der Stapel leer ist – true oder nicht – false ;
• Suche – durchsucht den Stapel nach einem bestimmten Element. Wenn ein Element gefunden wird, wird seine Sequenznummer relativ zur Oberseite des Stapels zurückgegeben. Wird das Element nicht gefunden, wird der Wert -1 zurückgegeben.

Im Moment wird die Stack- Unterklasse aufgrund ihrer Einfachheit und Inflexibilität nicht wirklich verwendet, aber dennoch kann es vorkommen, dass Sie auf sie stoßen. Wenn Sie beispielsweise eine Fehlermeldung erhalten und in der Konsole eine Reihe von Meldungen dazu angezeigt werden. Weitere Informationen zum Stapel und zur Warteschlange finden Sie in diesem Artikel .

7. Erzählen Sie uns etwas über Map

Wie oben erwähnt, ist eine Map eine Sammlung, die über eine separate Struktur von Schnittstellen und deren Implementierungen verfügt. Es ist getrennt, da hier die Werte nicht einzeln, sondern in einem „Schlüssel-Wert“-Paar gespeichert werden. Grundlegende Kartenmethoden :

• put(K-Taste, V-Wert) – Hinzufügen eines Elements zur Karte;
• get(Objektschlüssel) – Suche nach einem Wert anhand des Schlüssels;
• enthältKey(Objektschlüssel) – prüft die Karte auf das Vorhandensein dieses Schlüssels;
• enthältValue(Objektwert) – prüft die Karte auf das Vorhandensein dieses Werts;
• remove(Object key) – Entfernen eines Werts anhand seines Schlüssels.

Wie Sie sehen, funktionieren die meisten Vorgänge über einen Schlüssel. Als Schlüssel werden in der Regel unveränderliche Objekte gewählt . Ein typisches Beispiel für dieses Objekt ist String . Grundlegende Kartenimplementierungen :

1. HashMap – dient zum Speichern von Werten in zufälliger Reihenfolge, ermöglicht aber auch die schnelle Suche nach Kartenelementen. Ermöglicht die Angabe eines Schlüssels mit dem Schlüsselwort null , jedoch nicht mehr als einmal, weil Paare mit gleichen Schlüsseln werden übereinander geschrieben. Die Hauptbedingung ist die Eindeutigkeit der Schlüssel: Die Werte können wiederholt werden (es können mehrere Nullwerte vorhanden sein).
2. LinkedHashMap ist ein Analogon von HashMap , das Werte in der Reihenfolge speichert, in der sie hinzugefügt wurden. Dementsprechend verfügt es wie LinkedList über einen Header – den Kopf einer doppelt verknüpften Liste. Bei der Initialisierung zeigt es auf sich selbst.

   LinkedHashMap verfügt außerdem über eine accessOrder , die angibt, wie auf die Elemente zugegriffen wird, wenn der Iterator verwendet wird. Wenn accessOrder den Wert false hat, erfolgt der Zugriff in der Reihenfolge, in der die Elemente eingefügt wurden. Wenn „true“, werden die Elemente in der Reihenfolge des letzten Zugriffs angezeigt (das Element, auf das zuletzt zugegriffen wurde, wird am Ende platziert).

3. TreeMap ist eine Karte , die Elemente nach Schlüsselwerten sortiert. Ähnlich wie TreeSet , jedoch für Paare basierend auf Schlüsselwerten. Um TreeMap- Sortierregeln festzulegen, müssen Schlüssel die Comparable- Schnittstelle implementieren . Andernfalls sollte es einen schlüsselorientierten Komparator geben (denjenigen, der im TreeMap- Konstruktor angegeben ist ), ein TreeSet – implementiert mit einem TreeMap-Objekt darin, in dem tatsächlich die ganze Magie passiert.

   Weitere Informationen zum Sortieren in TreeMap anhand rot-schwarzer Bäume finden Sie im Artikel über die Funktionen von TreeMap .

4. Hashtable ähnelt HashMap , erlaubt jedoch nicht die Speicherung von Nullen als Schlüssel oder Werte. Es ist aus Multi-Threading-Sicht sorgfältig synchronisiert, was wiederum bedeutet, dass es aus Multi-Threading-Sicht sicher ist. Diese Implementierung ist jedoch veraltet und langsam, sodass Sie Hashtable jetzt nicht mehr in mehr oder weniger neuen Projekten sehen werden.

8. ArrayList vs. LinkedList. Welches ist vorzuziehen?

Diese Frage ist vielleicht die am häufigsten gestellte Frage zu Datenstrukturen und birgt einige Fallstricke. Bevor wir darauf antworten, erfahren Sie mehr über diese Datenstrukturen. ArrayList implementiert die List- Schnittstelle und arbeitet mit einem internen Array, das nach Bedarf erweitert wird. Wenn das interne Array vollständig gefüllt ist und ein neues Element eingefügt werden muss, wird ein neues Array mit einer Größe von (oldSize * 1,5) +1 erstellt. Danach werden alle Daten aus dem alten Array in das neue + neue Element kopiert und das alte vom Garbage Collector gelöscht . Die Add- Methode fügt der letzten leeren Zelle des Arrays ein Element hinzu. Das heißt, wenn wir dort bereits 3 Elemente haben, wird das nächste zur 4. Zelle hinzugefügt. Lassen Sie uns die Leistung der grundlegenden Methoden durchgehen:

• get(int index) – Das Erfassen eines Elements in einem Array anhand des Index ist in O(1) am schnellsten .
• add(Object obj) – Wenn im internen Array genügend Platz für ein neues Element vorhanden ist, wird bei einer normalen Einfügung O(1) Zeit aufgewendet , da die Hinzufügung auf die letzte Zelle ausgerichtet ist.

  Wenn wir ein neues Array erstellen und den Inhalt hineinkopieren müssen, ist unsere Zeit direkt proportional zur Anzahl der Elemente im Array O(n) ;

• remove(int index) – wenn wir beispielsweise ein Element aus der Mitte entfernen, erhalten wir O(n/2) Zeit, da wir die Elemente rechts davon eine Zelle nach hinten verschieben müssen. Wenn dementsprechend vom Anfang der Liste gelöscht wird, dann O(n), vom Ende - O(1);
• add(int index, Object obj) – eine ähnliche Situation wie beim Löschen: Beim Hinzufügen zur Mitte müssen wir die Elemente auf der rechten Seite eine Zelle nach vorne verschieben, sodass die Zeit O(n/2) beträgt. Natürlich vom Anfang - O(n), vom Ende - O(1);
• set(int index, Object obj) – hier ist die Situation anders, da Sie nur das gewünschte Element finden und darüber schreiben müssen, ohne den Rest zu verschieben, also O(1).

Lesen Sie mehr über ArrayList in diesem Artikel . LinkedList implementiert zwei Schnittstellen gleichzeitig – List und Queue und verfügt daher über Eigenschaften und Methoden, die beiden Datenstrukturen innewohnen. Von der Liste erhielt er Zugriff auf ein Element über den Index, von der Warteschlange das Vorhandensein eines „Kopfes“ und eines „Schwanzes“. Intern ist es als Datenstruktur implementiert, die eine doppelt verknüpfte Liste darstellt. Das heißt, jedes Element hat eine Verbindung zum nächsten und vorherigen, mit Ausnahme des „Schwanzes“ und des „Kopfes“.

• get(int index) – Bei der Suche nach einem Element, das sich in der Mitte der Liste befindet, werden alle Elemente der Reihe nach durchsucht, bis das gewünschte Element gefunden wird. Logischerweise sollte die Suche O(n/2) dauern , aber LinkedList hat auch einen Schwanz, sodass die Suche gleichzeitig von beiden Seiten durchgeführt wird. Dementsprechend verkürzt sich die Zeit auf O(n/4) .

  Befindet sich das Element nahe am Anfang oder Ende der Liste, ist die Zeit O(1) ;

• add(Object obj) – Beim Hinzufügen eines neuen Elements erhält das „tail“-Element einen Link zum nächsten hinzugefügten Element, und das neue Element erhält einen Link zu diesem vorherigen Element und wird zum neuen „tail“. Dementsprechend wird die Zeit O(1) sein ;
• Remove(int Index) – Logik ähnlich der Methode get(int Index) . Um ein Element aus der Mitte der Liste zu entfernen, müssen Sie es zunächst finden. Dies ist wieder O(n/4) , während das Löschen selbst eigentlich nichts kostet, da es nur den Zeiger benachbarter Objekte ändert (sie beginnen, aufeinander zu verweisen). Wenn das Element am Anfang oder am Ende steht, dann wieder - O(1) ;
• add(int index, Object obj) und set(int index, Object obj) – die Methoden haben eine zeitliche Komplexität, die mit get(int index) identisch ist , da die meiste Zeit mit der Suche nach dem Element verbracht wird. Daher gilt für die Mitte der Liste O(n/4) und für den Anfang O(1).

Weitere Informationen zur Arbeit mit LinkedList finden Sie in diesem Artikel . Schauen wir uns das alles in einer Tabelle an: Wie Sie wahrscheinlich bereits verstanden haben, ist es unmöglich, diese Frage eindeutig zu beantworten. Schließlich arbeiten sie in verschiedenen Situationen unterschiedlich schnell. Wenn Ihnen eine solche Frage gestellt wird, sollten Sie daher sofort fragen, worauf sich diese Liste konzentrieren wird und welche Vorgänge am häufigsten ausgeführt werden. Geben Sie ausgehend davon eine Antwort, aber mit Erläuterungen, warum das so ist. Fassen wir unseren Vergleich zusammen: ArrayList:

• die beste Wahl, wenn die häufigste Operation darin besteht, nach einem Element zu suchen und ein Element zu überschreiben;
• Die schlechteste Wahl, wenn die Operation das Einfügen und Löschen am Anfang und in der Mitte ist, da die Verschiebungsoperationen der Elemente auf der rechten Seite stattfinden.

Verlinkte Liste:

• die beste Wahl, wenn unsere häufige Operation das Einfügen und Löschen am Anfang und in der Mitte ist;
• schlechteste Wahl, wenn die häufigste Operation die Suche ist.

9. Wie werden Elemente in einer HashMap gespeichert?

Die HashMap- Sammlung enthält ein internes Array Node[]table , dessen Zellen auch Buckets genannt werden . Knoten enthält:

• Schlüssel – Link zum Schlüssel,
• Wert – Verweis auf den Wert,
• Hash – Hashwert,
• next – Link zum nächsten Knoten .

Eine Zelle des table[] -Arrays kann einen Verweis auf ein Node- Objekt mit einem Link zum nächsten Node- Element enthalten , und sie kann einen Link zu einem anderen haben usw. Als Ergebnis können diese Node- Elemente ein bilden einfach verknüpfte Liste mit Elementen mit einem Link zum nächsten. In diesem Fall ist der Hashwert der Elemente einer Kette gleich. Schauen wir uns nach einem kurzen Exkurs an, wie Elemente in einer HashMap gespeichert werden :

1. Der Schlüssel wird auf null überprüft . Wenn es null ist , wird der Schlüssel in der Zelle table[0] gespeichert , da der Hash-Code für null immer 0 ist.
2. Wenn der Schlüssel nicht null ist, wird die Methode hashcode() des Schlüsselobjekts aufgerufen , die seinen Hash-Code zurückgibt. Dieser Hash-Code wird verwendet, um die Array-Zelle zu bestimmen, in der das Node-Objekt gespeichert wird.
3. Als nächstes wird dieser Hashcode in die interne hash()- Methode eingefügt , die den Hashcode berechnet, jedoch innerhalb der Größe des table[]- Arrays .
4. Als Nächstes wird Node je nach Hashwert in einer bestimmten Zelle im Array table[] platziert .
5. Wenn die Zelle table[] , die zum Speichern des aktuellen Node- Elements verwendet wird , nicht leer ist, sondern bereits ein Element enthält, werden die Node- Elemente über den nächsten Wert iteriert , bis das letzte Element erreicht ist. Das heißt, derjenige, dessen nächstes Feld null ist .

   Bei dieser Suche wird der Schlüssel des geschützten Node- Objekts mit den Schlüsseln der gesuchten Objekte verglichen:

   • Wenn eine Übereinstimmung gefunden wird, wird die Suche beendet und der neue Knoten überschreibt den Knoten, in dem die Übereinstimmung gefunden wurde (nur sein Wertefeld wird überschrieben ).
   • Wenn keine Schlüsselübereinstimmungen gefunden werden, wird der neue Knoten der letzte in dieser Liste und der vorherige erhält einen nächsten Link dazu.

In Vorstellungsgesprächen stellt sich oft die Frage: Was ist ein Konflikt ? Die Situation, in der eine Zelle des Arrays table[] nicht ein Element, sondern eine Kette von zwei oder mehr speichert, wird als Kollision bezeichnet . In normalen Fällen, in denen nur ein Element in einer einzelnen Tabelle[]- Zelle gespeichert ist , hat der Zugriff auf die Elemente einer HashMap eine konstante O(1) -Zeitkomplexität . Wenn jedoch eine Zelle mit dem gewünschten Element eine Kette von Elementen enthält ( Kollision ), dann O(n) , da in diesem Fall die Zeit direkt proportional zur Anzahl der sortierten Elemente ist.

10. Erklären Sie den Iterator

Im Abbildungsdiagramm der Collection -Hierarchie oben begann die gesamte Hierarchie mit der Collection- Schnittstelle, aber in der Praxis ist das nicht ganz so. Die Sammlung erbt von einer Schnittstelle mit einer iterator()- Methode , die ein Objekt zurückgibt, das die Iterator<E> -Schnittstelle implementiert . Die Iterator-Schnittstelle sieht folgendermaßen aus:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() – Durch Aufrufen dieser Methode können Sie das nächste Element abrufen. hasNext() – ermöglicht es Ihnen herauszufinden, ob es ein nächstes Element gibt und ob das Ende der Sammlung erreicht wurde. Und wenn noch Elemente vorhanden sind, gibt hasNext() true zurück . Normalerweise wird hasNext() vor der next()- Methode aufgerufen , da next() eine NoSuchElementException auslöst , wenn das Ende der Sammlung erreicht wird . remove() – Entfernt das Element, das beim letzten Aufruf von next() abgerufen wurde . Der Zweck von Iterator besteht darin, Elemente zu iterieren. Zum Beispiel:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Tatsächlich wird die for-each-Schleife unter der Haube mithilfe eines Iterators implementiert. Mehr dazu können Sie hier lesen . List bietet eine eigene Version eines Iterators, jedoch eine coolere und anspruchsvollere Version – ListIterator . Diese Schnittstelle erweitert Iterator und verfügt über zusätzliche Methoden:

• hasPrevious gibt „true“ zurück, wenn es ein vorheriges Element in der Sammlung gibt, andernfalls „false“;
• previous gibt das aktuelle Element zurück und wechselt zum vorherigen; Wenn keine vorhanden ist, wird eine NoSuchElementException ausgelöst.
• add fügt das übergebene Objekt vor dem Element ein, das beim nächsten Aufruf von next() zurückgegeben werden soll ;
• set weist dem aktuellen Element eine Referenz auf das übergebene Objekt zu;
• nextIndex gibt den Index des nächsten Elements zurück. Wenn es so etwas nicht gibt, wird die Größe der Liste zurückgegeben;
• previousIndex gibt den Index des vorherigen Elements zurück. Wenn keine vorhanden ist, wird die Zahl -1 zurückgegeben.

Nun, das ist alles für mich heute. Ich hoffe, dass Sie nach der Lektüre dieses Artikels Ihrem geliebten Traum, Entwickler zu werden, noch näher kommen.