Wo finde ich das Kapitel, das mich in einem Buch interessiert? Wohin geht Ana Garcías Bitte? Wo kann ich diese Uhr mit dem braunen Lederarmband kaufen? Gemeinsam ist diesen Sätzen, dass sie nicht nur Fragen sind, sondern auch nach einem Ort fragen: Wo? wo? Ein weiterer gemeinsamer Punkt ist, dass alle drei davon ausgehen, dass das gesuchte Objekt existiert. Diese Denkstruktur kann leicht als Beispiel dafür verwendet werden, was in einer Datenbank geschieht.

Stellen Sie sich einen Online- Shop mit Tausenden von Artikeln und Kunden vor. Die Daten aller von ihnen werden in Datenbanken gespeichert: Der Kunde durchsucht eine Datenbank nach einem bestimmten Artikel und gibt seine Bestellung auf; Der Versender verwendet eine Datenbank, um den Artikel dem Käufer und seiner Postanschrift zuzuweisen. Dieser Prozess umfasst das Sortieren, Hinzufügen und Entfernen von Aufgaben während der Bestellung. Um sie effizienter verwalten zu können , werden große Datenmengen mit gemeinsamen Elementen zusammengefasst an einer Adressposition in der Datenbank. Diese Position wird mit Hash- Werten berechnet und besteht aus einer Tabelle mit Kombinationen von Zahlen und Buchstaben gleicher Länge. In diesem Artikel erklären wir die Grundlagen, damit Sie Tabellen- Hash ( Hash-Tabellen ) verwenden können.

1. Welchem ​​Prinzip folgt eine Hash-Tabelle?
   1. Hash-Sicherheit
   2. Beschleunigen Sie Datenbankprozesse
2. Welche Varianten des Hash-Prozesses gibt es?
3. Vor- und Nachteile von Hash-Tabellen

Ein Hash- Wert wird zuerst aus den Daten in einem Datensatz berechnet . Die Hashes aller Datensätze in einer Datenbank werden in der Hash- Tabelle gespeichert . Durch eine andere mathematische Operation wird der Ort dieser Informationen in der Datenbank aus dem Hashwert berechnet . Wenn der Benutzer dann einen Begriff in das Suchfeld eingibt , wird dieser Begriff ebenfalls gehasht . Von da an wird daher nicht mehr nach “Mit braunem Lederarmband beobachten” gesucht , sondern nach einer Übereinstimmung zwischen dem ursprünglich gehashten Wert für den Artikel und dem Hash- Wert des aktuell gesuchten Begriffs. Mit anderen Worten wird eine Übereinstimmung zwischen zwei Kombinationen von Zahlen und Buchstaben gesucht. Dieser Ansatz wird für alle Arten von Anwendungen verwendet.

Eine Hash- Tabelle ist das Ergebnis der Zuweisung automatisch generierter Hashes zu bestimmten Suchbegriffen. Hierzu wird eine Hash-Funktion verwendet, die eine Folge von Zeichen mit einer konstanten Länge erzeugt, die als Hash bezeichnet wird . Die Länge der Sequenz und die Zeichen, aus denen sie besteht, werden durch die verwendete Hash- Methode festgelegt . Diese Methode wird beispielsweise verwendet, um Zugriffsdaten vor Datendiebstahl zu schützen .

Bei angemeldeten Anmeldungen in der Bilddatenbank, das Passwort durch den Benutzer eingegeben ist auf einem umgebauten Hash – Wert nach dem gleichen Verfahren. Dieser Wert wird dann mit dem entsprechenden Eintrag im Feld user_pass der Datenbank verglichen . Wenn beide 34-stelligen Hashes übereinstimmen, wird der Zugriff gewährt. Im umgekehrten Sinne ist es nicht möglich, ein Passwort von einem Hash- Wert zu entschlüsseln : Dies ist eine der Eigenschaften von Hash- Funktionen .

Wenn der nicht autorisierte Zugriffsversuch auf einem Brute-Force-Angriff basiert, sollte die Sequenz mit allen zulässigen Zeichen getestet werden, bis eine genaue Übereinstimmung gefunden wird. Wenn Kleinbuchstaben, Großbuchstaben und Zahlen enthalten sind und der Angreifer die verwendete Hash- Funktion kennt , würde ein 10- stelliges Kennwort genau 839.299.365.868.340.200 Versuche erfordern, die richtige Kombination zu finden.

In den Datenbank – Tabellen werden verwendet Hash zu beschleunigen den Suchvorgang, Registrierung und Löschung von Datensätzen. Stellen wir uns vor, ein Nachname wird in einer Datenbank gesucht, die alle Mitarbeiter eines Unternehmens enthält: Die Aufgabe kann lange dauern, da auf herkömmliche Weise jedes der Felder in der Datenbank nach einer Übereinstimmung durchsucht wird nacheinander (nacheinander). Wenn Sie stattdessen den Suchbegriff in einen Hashwert konvertieren und ihn dann in der Hash- Tabelle nachschlagen , dauert der Vorgang normalerweise viel weniger Zeit.

Wie genau wird das gemacht? Jedem Datensatz ist eine eindeutige Adresse zugeordnet . Die Regeln für diese Zuordnung sind in jeder Datenbank immer gleich (001, 002, 003 oder 00A1, 00A2, 00A3 usw.). Die Adresse wird mit der Hash- Funktion berechnet .

Nehmen wir als einfaches Beispiel an , wir haben eine Datenbank mit Platz für 11 Einträge an den Positionen 0 bis 10. Der Name Lisa besteht aus 4 ASCII-Zeichen mit jeweils einem ASCII-Code: L ist 76, i ist 105, s ist 115 und a ist 97. Sie können diese Zuordnung selbst über den Ziffernblock überprüfen: Sie werden sehen, dass beispielsweise mit [Alt] + 0076 ein L angezeigt wird . Dann werden alle ASCII-Werte von Lisa addiert , was zu einem Hash- Wert 393 führt. In diesem Fall entspricht die Summe der ASCII-Werte einer Hash- Funktion .

Darauf folgt eine Berechnung des Restes mit ganzen Zahlen : 393% 11 (Einträge, die in die Basis passen) = 35, Rest 8 (in vielen Programmiersprachen entspricht das prozentuale Symbol % dem mathematischen Operator der Restberechnung). Dieser Rest bestimmt, wo in der Datenbank (in unserer Beispielberechnung Indexnummer 8 ) Lisa und alle sie betreffenden Daten gespeichert werden . Wie Sie vielleicht bereits vermutet haben, werden bei dieser Art der Adressierung die resultierenden Residuen häufig wiederholt. Je mehr Speicherplatz und je länger der verwendete Hashwert ist , desto unwahrscheinlicher ist es, dass solche Wiederholungen auftreten. Im Fall des Namens Alis wäre die Positionierung anders , selbst wenn die Buchstaben des Namens mit denen von Lisa übereinstimmen , da A in Großbuchstaben und L in Kleinbuchstaben geschrieben ist.

Im vorherigen Bild sehen wir ein Wiederholungsproblem : Es ist möglich, dass verschiedene Namen dieselben Indexwerte erhalten, was zu sogenannten Kollisionen (hellblauen Pfeilen) führt. Wie reagiert die Datenbank auf dieses Hindernis? Suchen Sie den Datensatz an der nächstgelegenen freien Position. Wenn beispielsweise Berta Torres durchsucht wird, beginnt die Suche nicht an Position 001, sondern der Suchzeiger geht direkt zur Indexposition 003, was eine (leichte) Beschleunigung des Prozesses bedeutet. Diese Methode, die dann linear durchsucht wird, wird als offenes Hashing (oder lineares Probing) bezeichnet.

Inzwischen ist das Verfahren des Hashing gekettet ( Chaining ) funktioniert anders: nicht öffnet keine neue Datensatz, sondern geht die erste Datensatz Anpassung an den nächsten verketten. Auf diese Weise wird der gesuchte Datensatz mit einer einzigen Suchanforderung gefunden, da er sich nach dem ersten Satz im Speicherort befindet. Infolgedessen wird die Verarbeitung schneller.

Bei der Suche nach Berta Torres wird der Datenzeiger also von Anfang an auf den aus der Hash- Tabelle berechneten Wert 003 gesetzt und muss fortan nur noch einen verketteten Datensatz untersuchen. Auf diese Weise können große Datenmengen schneller und komplexer gruppiert und untersucht werden.

Die als Caching bekannte Methode verwendet dieses Prinzip auch, um Daten abzurufen , die jemals verwendet wurden . Diese Daten werden im temporären Speicher oder Cache gespeichert und von dort abgerufen, wenn sie mit einem Aktivitätsmuster übereinstimmen. Dies gilt beispielsweise für besuchte Webseiten, sodass diese bei einem zweiten Besuch nicht mehr vollständig vom Server geladen werden müssen, sondern viel schneller aus dem Cache abgerufen werden. Die Cookies dienen auch als eine Art Identifikationsvergleich, der angibt, welche Websites der Benutzer im Internet besucht hat.

Der in diesem Artikel beschriebene Hashing- Prozess wird auch als offenes oder externes Hashing bezeichnet , da er zumindest theoretisch Daten in Form von verketteten Listen in einem unendlichen Raum speichern kann. Obwohl die Tasten begrenzt sind, können Sie durch Verketten größere Datenmengen verarbeiten. Die offene Bewertung bezieht sich auf die Adressierung.

Bei geschlossenem Hashing ist die Anzahl der Schlüssel jedoch durch die Kapazität der Tabelle begrenzt. Wenn Sie versuchen , zu mehr Daten zu speichern, nimmt einen Anruf Überlauf oder Überlauf . Bei jeder neuen Untersuchung wird die Tabelle abgefragt, um freie Positionen zu finden, an denen die übergelaufenen Elemente lokalisiert werden können .

Andererseits wird auch der sogenannte Kuckuck-Hash oder Kuckuck-Hashing angewendet, um Kollisionen in der Datenbanktabelle zu vermeiden . Diese Methode verdankt ihren Namen dem Verhalten des Kuckucks, der die Eier aus den Nestern anderer Leute entfernt, um ihre eigenen in sie zu legen. Ähnlich ist der Kuckuck hash Wendet zwei Hash- Funktionen an, um zwei Speicherorte zu definieren . Wenn die erste Position bereits belegt ist, wird der dort befindliche Schlüssel an eine andere Position verschoben, sodass der zweite generierte Schlüssel an der ersten Position platziert werden kann. Der Nachteil dieser Variante ist, dass sie eine endlose Suchschleife erzeugen kann, so dass eine gestartete Routine unterbrochen wird, weil sie die zugewiesene Zeit überschreitet.

Beim Abrufen der Datenbank gibt es verschiedene Methoden, die auf der Grundlage komplexer mathematischer Formeln erstellt und in Form von Programmcode auf einer Webseite versteckt werden, z. B. hinter der Suchleiste mit dem Symbol des Lupe.

Im Allgemeinen werden Datenbanken immer komplexer. Die Datenmenge, aus der sie bestehen, wächst immer schneller. Aus diesem Grund erhöht dynamisches Hashing die Hash- Tabelle , um Kollisionen zu vermeiden. Dies führt jedoch dazu, dass auch die Hashes bereits gespeicherter Daten geändert werden . Um dieses Problem effizient zu lösen, wurden spezielle Hash- Funktionen entwickelt . Damit wird die Datenspeicherkapazität wird, zumindest in der Theorie, unbegrenzt , obwohl die Suchzyklen weniger effizient geworden.

Der größte Vorteil der Verwendung einer Hash- Tabelle ist die Suchgeschwindigkeit gegenüber großen Datenmengen . Um dies zu erreichen, stehen Datenbankarchitekten jedoch vor der Herausforderung, die erforderliche Größe im Voraus zu schätzen, um das Kollisionsrisiko zu verringern. Es können viele verschiedene Datentypen verwendet werden , solange daraus Hashes berechnet werden können.

Eine der Schwachstellen dieser Methode ist die mögliche schwerwiegende Degeneration des Systems, wenn viele Kollisionen auftreten . Die Wahrscheinlichkeit von Kollisionen steigt mit zunehmender Datenmenge. Das Vorhandensein einer großen Anzahl von Hash- Funktionen verhindert das Verschieben von einem Datensatz zum vorherigen oder zum nächsten.