Hashing ist eine grundlegende Datenstruktur, die Daten effizient speichert und abruft, sodass ein schneller Zugriff möglich ist. Dabei werden Daten mithilfe von a einem bestimmten Index in einer Hash-Tabelle zugeordnet Hash-Funktion Dies ermöglicht ein schnelles Abrufen von Informationen basierend auf ihrem Schlüssel. Diese Methode wird häufig in Datenbanken verwendet. C schmerzende Systeme und verschiedene Programmieranwendungen zur Optimierung von Such- und Abrufvorgängen.

10 von 60

Datenstrukturen – Hashing

Inhaltsverzeichnis

• Hash-Funktion
• Was ist eine Hash-Kollision?
• Techniken zur Kollisionsauflösung
• Anwendungen von Hashing
• Einfaches Problem beim Hashing
• Mittleres Problem beim Hashing
• Schwieriges Problem beim Hashing

Wie es funktioniert:

1. Hash-Funktion: Sie stellen Ihre Datenelemente in der Hash-Funktion bereit.
2. Hash-Code: Die Hash-Funktion verarbeitet die Daten und gibt einen eindeutigen Hash-Code aus.
3. Hash-tabelle: Der Hash-Code verweist Sie dann auf eine bestimmte Stelle innerhalb der Hash-Tabelle.

Hash-Funktion

Der Hash-Funktion ist eine Funktion, die a benötigt Schlüssel und gibt eine zurück Index in die Hash-tabelle . Das Ziel einer Hash-Funktion besteht darin, Schlüssel gleichmäßig über die Hash-Tabelle zu verteilen und so Kollisionen zu minimieren (wenn zwei Schlüssel demselben Index zugeordnet sind).

Zu den gängigen Hash-Funktionen gehören:

• Teilungsmethode: Schlüssel-%-Hash-Tabellengröße
• Multiplikationsmethode: (Schlüssel * Konstante) % Hash-Tabellengröße
• Universelles Hashing: Eine Familie von Hash-Funktionen zur Minimierung von Kollisionen

Was ist eine Hash-Kollision?

Eine Hash-Kollision tritt auf, wenn zwei verschiedene Schlüssel demselben Index in einer Hash-Tabelle zugeordnet sind. Dies kann auch bei einer guten Hash-Funktion passieren, insbesondere wenn die Hash-Tabelle voll ist oder die Schlüssel ähnlich sind.

Ursachen für Hash-Kollisionen:

• Schlechte Hash-Funktion: Eine Hash-Funktion, die Schlüssel nicht gleichmäßig über die Hash-Tabelle verteilt, kann zu mehr Kollisionen führen.
• Hoher Lastfaktor: Ein hoher Lastfaktor (Verhältnis von Schlüsseln zur Hash-Tabellengröße) erhöht die Wahrscheinlichkeit von Kollisionen.
• Ähnliche Schlüssel: Bei Schlüsseln mit ähnlichem Wert oder ähnlicher Struktur ist die Wahrscheinlichkeit größer, dass sie kollidieren.

Techniken zur Kollisionsauflösung

Es gibt zwei Arten von Kollisionsauflösungstechniken:

Stellvertretender Polizeikommissar

1. Offene Adressierung:
   • Lineare Sondierung: Suchen Sie nacheinander nach einem leeren Steckplatz
   • Quadratische Sondierung: Suchen Sie mithilfe einer quadratischen Funktion nach einem leeren Steckplatz
2. Geschlossene Adressierung:
   • Verkettung: Speichern Sie kollidierende Schlüssel in einer verknüpften Liste oder einem binären Suchbaum an jedem Index
   • Kuckucks-Hashing: Verwenden Sie mehrere Hash-Funktionen, um Schlüssel zu verteilen

Anwendungen von Hashing

Hash-Tabellen werden in einer Vielzahl von Anwendungen verwendet, darunter:

• Datenbanken: Speichern und Abrufen von Daten basierend auf eindeutigen Schlüsseln
• Caching: Speicherung häufig aufgerufener Daten zum schnelleren Abrufen
• Symboltabellen: Zuordnung von Bezeichnern zu ihren Werten in Programmiersprachen
• Netzwerkrouting: Ermittlung des besten Pfades für Datenpakete

Was ist Hashing?

Indexzuordnung (oder triviales Hashing)

Separate Verkettung zur Kollisionsbehandlung

Offene Adressierung für die Kollisionsbehandlung

Doppeltes Hashing

Lastfaktor und Aufwärmen

Einfaches Problem beim Hashing

• Finden Sie heraus, ob ein Array eine Teilmenge eines anderen Arrays ist
• Vereinigung und Schnittmenge zweier verknüpfter Listen
• Suchen Sie bei einem gegebenen Array A[] und einer Zahl x nach einem Paar in A[] mit der Summe x
• Maximaler Abstand zwischen zwei Vorkommen desselben Elements im Array
• Zählen Sie die maximale Punktzahl auf derselben Linie
• Häufigstes Element in einem Array
• Finden Sie das einzige sich wiederholende Element zwischen 1 und n-1
• Wie kann man überprüfen, ob zwei gegebene Mengen disjunkt sind?
• Nicht überlappende Summe zweier Mengen
• Überprüfen Sie, ob zwei Arrays gleich sind oder nicht
• Finden Sie fehlende Elemente eines Bereichs
• Mindestanzahl von Teilmengen mit unterschiedlichen Elementen
• Entfernen Sie die Mindestanzahl an Elementen, sodass in beiden Arrays kein gemeinsames Element vorhanden ist
• Finden Sie Paare mit einer bestimmten Summe, sodass sich die Elemente des Paares in verschiedenen Zeilen befinden
• Zähle Paare mit gegebener Summe
• Zählen Sie Vierfache aus vier sortierten Arrays, deren Summe einem gegebenen Wert x entspricht
• Sortieren Sie Elemente nach Häufigkeit
• Finden Sie alle Paare (a, b) in einem Array, sodass a % b = k
• Gruppieren Sie Wörter mit demselben Zeichensatz
• k-tes eindeutiges (oder sich nicht wiederholendes) Element in einem Array.

Mittleres Problem beim Hashing

• Finden Sie die Reiseroute aus einer bestimmten Ticketliste
• Finden Sie die Anzahl der Mitarbeiter unter jedem Mitarbeiter
• Längstes Subarray mit durch k teilbarer Summe
• Finden Sie das größte Subarray mit der Summe 0
• Längste ansteigende aufeinanderfolgende Teilsequenz
• Zählen Sie verschiedene Elemente in jedem Fenster der Größe k
• Finden Sie ein Subarray mit der angegebenen Summe | Satz 2 (Verarbeitet negative Zahlen)
• Implementierung unserer eigenen Hash-Tabelle mit separater Verkettung in Java
• Implementierung einer eigenen Hash-Tabelle mit Open Addressing Linear Probing in C++
• Minimale Einfügungen zur Bildung eines Palindroms mit zulässigen Permutationen
• Maximal mögliche Differenz zweier Teilmengen eines Arrays
• Sortieren mit trivialer Hash-Funktion
• Kleinstes Subarray mit k unterschiedlichen Zahlen

Schwieriges Problem beim Hashing

• Klonen Sie einen Binärbaum mit zufälligen Zeigern
• Größtes Subarray mit gleicher Anzahl von Nullen und Einsen
• Alle eindeutigen Tripel, die in der Summe einen bestimmten Wert ergeben
• Palindrom-Teilzeichenfolgenabfragen
• Bereichsabfragen für Häufigkeiten von Array-Elementen
• Elemente, die hinzugefügt werden sollen, sodass alle Elemente eines Bereichs im Array vorhanden sind
• Cuckoo Hashing – Worst Case O(1) Lookup!
• Zählen Sie Subarrays, deren Gesamtzahl unterschiedlicher Elemente mit der des ursprünglichen Arrays übereinstimmt
• Maximales Array aus zwei gegebenen Arrays, wobei die Reihenfolge gleich bleibt
• Finden Sie die Summe aller eindeutigen Sub-Array-Summen für ein bestimmtes Array.
• Recamans Sequenz
• Länge der längsten streng bitonischen Teilsequenz
• Alle doppelten Teilbäume finden
• Finden Sie heraus, ob es in der Binärmatrix ein Rechteck mit den Ecken 1 gibt

Quicklinks:

• „Übungsprobleme“ beim Hashing
• Top 20 der auf Hashing-Technik basierenden Interviewfragen
• „Videos“ zum Thema Hashing