Hashtabelle: Mit der Hashfunktion erzeugte Hashwerte schneller finden


Für Datenbanken werden Hashtabellen genutzt, um Suchvorgänge sowie das Eintragen oder Löschen von Datensätzen zu beschleunigen. Wenn man zum Beispiel eine Datenbank aller Mitarbeiter eines Unternehmens nach einem Nachnamen durchsucht, kann das sehr viel Zeit in Anspruch nehmen, weil jedes Datenbankfeld nacheinander (sequenziell) auf Übereinstimmung durchsucht wird. Wandelt man den Suchbegriff in einen Hashwert um und sucht damit in der Hashtabelle nach Übereinstimmung, geht es in der Regel viel schneller.

Wie wird dies realisiert? Jeder Datensatz bekommt eine eindeutige Adresse. Die Artwork dieser Adressierung ist innerhalb der Datenbank immer identisch (001, 002, 003 oder 00A1, 00A2, 00A3 usw.). Diese Adresse wird mithilfe der Hashfunktion berechnet.

Ein einfaches Beispiel: Eine Datenbank hat Platz für 11 Einträge, von Place zero bis Place 10. Der Title „Lisa“ besteht aus vier ASCII-Zeichen mit den jeweiligen ASCII-Codes: L ist 76, i ist 105, s ist 115 und a ist 97. Das können Sie in Home windows mit dem Nummernfeld selbst ausprobieren: [Alt] + 0076 beispielsweise ergibt „L“. Alle ASCII-Werte werden addiert und ergeben für „Lisa“ den Hashwert 393. Die Addition der ASCII-Werte entspricht hier nun einer Hashfunktion.

Dann wird eine Restwertberechnung mit Ganzzahlen ausgeführt: 393 % 11 (Speicherplätze) = 35, Relaxation 8 (das Prozentzeichen „%“ ist in vielen Programmiersprachen der mathematische Operator für die Restwertberechnung). Dieser Restwert bestimmt nun, an welcher Stelle der Datenbank – hier im Rechenbeispiel additionally der Index Nummer 8 – Lisa und alle weiteren Angaben von ihr gespeichert werden. Es ist leicht vorzustellen, dass bei dieser Artwork von Adressierung häufig gleiche Restwerte auftreten. Je mehr Speicherplätze und je länger der benutzte Hashwert, desto geringer ist jedoch die Wahrscheinlichkeit, dass eine solche Dopplung auftritt. Bei „Alis Meyer“ träte trotz „gleicher“ Buchstaben eine ganz andere Positionierung auf, da das „A“ jetzt groß- und das „l“ jetzt kleingeschrieben ist.



Source link

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.