👨🏽‍🎓 ❄️ 👙 Was Sie über Hash-basierte Sammlungen wissen müssen 😲 🍥 ♋️

Hallo alle zusammen. In Kontakt Vladislav Rodin. Derzeit bin ich Leiter des High Load Architect-Kurses bei OTUS und unterrichte auch Kurse zur Softwarearchitektur.

Wie Sie vielleicht bemerkt haben, unterrichte ich neben dem Unterrichten auch urheberrechtlich geschütztes Material für den OTUS-Blog auf Habré und möchte den heutigen Artikel dem Start eines neuen Streams des Kurses "Algorithmen für Entwickler" widmen .

Einführung

Hash-Tabellen (HashMap) sind zusammen mit dynamischen Arrays die beliebtesten Datenstrukturen, die in der Produktion verwendet werden. Sehr oft können Sie bei Interviews Fragen zu ihrem Zweck, den Merkmalen ihrer internen Struktur sowie zu verwandten Algorithmen hören. Diese Datenstruktur ist klassisch und findet sich nicht nur in Java, sondern auch in vielen anderen Programmiersprachen.

Formulierung des Problems

Setzen wir uns ein Ziel, um eine Datenstruktur zu erstellen, mit der Sie:

enthält (Element element) prüfe, ob ein Element darin ist oder nicht, für O (1)
add (Element element) füge ein Element in O (1) hinzu
delete (Element element) lösche ein Element in O (1)

Array

Versuchen wir, diese Operationen über einem Array auszuführen, das die einfachste Datenstruktur darstellt. Wir sind uns einig, dass wir die Zelle als leer betrachten, wenn sie null enthält.

Verfügbarkeitsprüfung

Es ist erforderlich, eine lineare Suche durch das Array durchzuführen, da sich das Element möglicherweise in einer beliebigen Zelle befinden kann. Asymptotisch kann dies in O (n) erfolgen, wobei n die Größe des Arrays ist.

Hinzufügen

Wenn wir irgendwo ein Element hinzufügen müssen, müssen wir zuerst eine leere Zelle finden und dann das Element darauf schreiben. Wir führen also erneut eine lineare Suche durch und erhalten das asymptotische Verhalten von O (n).

Löschen

Um ein Element zu löschen, müssen Sie es zuerst suchen und dann null in die gefundene Zelle schreiben. Wieder führt uns die lineare Suche zu O (n).

Das einfachste Hash-Set

Bitte beachten Sie, dass wir bei jeder Operation zuerst nach dem Index der gewünschten Zelle gesucht und dann die Operation ausgeführt haben. Diese Suche verdirbt die Asymptotik für uns! Wenn wir lernen würden, diesen Index für O (1) zu erhalten, wäre das ursprüngliche Problem gelöst.

Ersetzen wir nun die lineare Suche durch den folgenden Algorithmus: Wir berechnen den Wert einer bestimmten Funktion - einer Hash-Funktion , die ein Klassenobjekt einer Ganzzahl zuordnet. Danach vergleichen wir die resultierende Ganzzahl mit dem Index der Array-Zelle (dies ist beispielsweise recht einfach, wenn Sie den Rest dieser Zahl durch die Größe des Arrays dividieren). Wenn die Hash-Funktion so geschrieben ist, dass sie als O (1) betrachtet wird (und normalerweise so geschrieben wird), erhalten wir die einfachste Implementierung der Hash-Menge. Eine Array-Zelle in Bezug auf einen Hash-Satz kann als Bucket bezeichnet werden .

Die Probleme der einfachsten Implementierung eines Hash-Sets

Unabhängig davon, wie die Hash-Funktion geschrieben wird, ist die Anzahl der Zellen im Array immer begrenzt, während die Anzahl der Elemente, die in der Datenstruktur gespeichert werden sollen, unbegrenzt ist. Schließlich würden wir uns nicht um die Datenstruktur kümmern, wenn nur zehn zuvor bekannte Elemente gespeichert werden müssten, oder? Dieser Zustand führt zu unvermeidlichen Konflikten . Eine Kollision ist eine Situation, in der wir beim Hinzufügen verschiedener Objekte in dieselbe Zelle im Array fallen.

Zwei Methoden wurden erfunden, um Kollisionen aufzulösen: die Verkettungsmethode und die offene Adressierungsmethode .

Verkettungsmethode

Die Verkettungsmethode ist die einfachste Methode zum Auflösen von Kollisionen. In der Zelle des Arrays speichern wir nicht die Elemente, sondern eine verknüpfte Liste dieser Elemente. Da das Hinzufügen zum Anfang der Liste (und es ist uns egal, zu welchem Teil der Liste das Element hinzugefügt werden soll) das asymptotische Verhalten von O (1) aufweist, wird das allgemeine asymptotische Verhalten nicht beeinträchtigt, und es bleibt gleich O (1).

Diese Implementierung hat ein Problem: Wenn die Listen sehr stark wachsen (als letztes Mittel können wir eine Hash-Funktion in Betracht ziehen, die für jedes Objekt eine Konstante zurückgibt), erhalten wir die Asymptotik O (m), wobei m die Anzahl der Elemente in der Menge ist, wenn die Größe Array ist fest. Um solche Probleme zu vermeiden, wird das Konzept des Arbeitszyklus eingeführt.(es kann zum Beispiel gleich 1,5 sein). Wenn sich beim Hinzufügen eines Elements herausstellt, dass der Bruchteil der Anzahl der Elemente in der Datenstruktur in Bezug auf die Größe des Arrays den Füllfaktor überschreitet, geschieht Folgendes: Es wird ein neues Array ausgewählt, dessen Größe die Größe des alten Arrays überschreitet (z. B. zweimal), und die Datenstruktur wird neu erstellt auf dem neuen Array.

Diese Methode zum Auflösen von Kollisionen wird in Java verwendet, und die Datenstruktur heißt HashSet .

Adressierungsmethode öffnen

Bei dieser Methode werden die Zellen selbst in den Zellen gespeichert, und im Falle einer Kollision tritt eine Folge von Proben auf , dh wir beginnen, die Zellen unter Verwendung eines Algorithmus zu sortieren, in der Hoffnung, eine freie zu finden. Dies kann durch verschiedene Algorithmen ( lineare / quadratische Folge von Abtastwerten , doppeltes Hashing ) erfolgen, von denen jeder seine eigenen Probleme hat (zum Beispiel die Entstehung von primären oder sekundären Clustern ).

Von einem Hash-Set zu einer Hash-Tabelle (HashMap)

Erstellen wir eine Datenstruktur, mit der Sie Elemente hinzufügen, löschen und nach Elementen suchen können, jedoch mit einem bestimmten Schlüssel, so schnell wie ein Hash-Satz (dh für O (1)).

Wir werden dieselbe Datenstruktur wie die Hash-Menge verwenden, aber wir werden keine Elemente, sondern Elementpaare speichern.

Das Einfügen (put (Schlüsselschlüssel, Wertwert)) wird also wie folgt ausgeführt: Wir berechnen die Zelle des Arrays durch ein Objekt vom Typ Schlüssel, wir erhalten die Anzahl der Buckets. Lassen Sie uns die Liste im Bucket durchgehen und den Schlüssel mit dem Schlüssel in gespeicherten Paaren vergleichen. Wenn Sie denselben Schlüssel finden - drücken Sie einfach den alten Wert heraus, wenn Sie ihn nicht gefunden haben - fügen Sie ein Paar hinzu.

Wie wird ein Artikel per Schlüssel empfangen? Ja, nach einem ähnlichen Prinzip: Wir erhalten Bucket für Schlüssel, gehen die Paare durch und geben den Wert in einem Paar zurück, wobei der Schlüssel dem Schlüssel in der Anforderung entspricht, wenn es ein solches Paar gibt, und ansonsten null.

Diese Datenstruktur wird als Hash-Tabelle bezeichnet .

Typische Interviewfragen

F: Wie sind HashSet und HashMap angeordnet? Wie werden die Hauptoperationen in diesen Sammlungen durchgeführt? Wie werden die Methoden equals () und hashCode () angewendet?
A : Antworten auf diese Fragen finden Sie oben.

F: Was ist der Vertrag für equals () und hashCode ()? Woran liegt es?
A : Wenn die Objekte gleich sind, muss der Hashcode gleich sein. Daher muss hashCode durch die Fähigkeit der an equals beteiligten Felder bestimmt werden. Verstöße gegen diesen Vertrag können zu sehr interessanten Auswirkungen führen. Wenn die Objekte gleich sind, ihr Hashcode jedoch unterschiedlich ist, erhalten Sie möglicherweise nicht den Wert, der dem Schlüssel entspricht, mit dem Sie das Objekt gerade zum HashSet oder zur HashMap hinzugefügt haben.

Fazit

Bei Interviews fragen sie gerne nach verschiedenen Fällen im Zusammenhang mit diesen Datenstrukturen. Darüber hinaus kann die Entscheidung eines jeden von ihnen aus dem Verständnis der Prinzipien seiner Arbeit abgeleitet werden, ohne dass es zu „Engpässen“ kommt.

Das ist alles. Wenn Sie das Material bis zum Ende gelesen haben, lade ich meinen Kollegen Evgeny Volosatov ein, Ihnen zu zeigen, wie Sie das Olympiadenproblem mit den Ideen der dynamischen Programmierung lösen können, um eine kostenlose Lektion zum Thema „Geheimnisse der dynamischen Programmierung“ zu erhalten .

Was Sie über Hash-basierte Sammlungen wissen müssen