Warum sollte die Länge Ihrer Hash-Tabelle eine Primzahl sein?

Blog

Warum sollte die Länge Ihrer Hash-Tabelle eine Primzahl sein?

Jeder gründliche Kurs zu Datenstrukturen und Algorithmen behandelt die Datenstruktur der Hashtabelle und damit auch die Hashfunktionen. Bei der Überprüfung von Datenstrukturen bin ich kürzlich auf die Idee gestoßen, Kollisionen zu reduzieren, indem ich die Länge Ihrer Hash-Tabelle zu einer Primzahl mache. Aufgrund des begrenzten Umfangs des Kurses ging der Autor nicht ins Detail, warum dies funktioniert, und regte bei Bedarf zur Selbstrecherche an. Es stellte sich heraus, dass ich so geneigt bin und dieser scheinbar magischen Lösung auf den Grund gehen wollte. Um einen kleinen Kontext zu schaffen, gehen wir zunächst kurz auf Hash-Tabellen, Hash-Funktionen ein, welche Eigenschaften eine gute Hash-Funktion ausmachen und schließlich, wie eine Hash-Tabelle mit Primzahlenlänge Kollisionen reduziert.

Hash-Tabellen

Da die meisten Sprachen über eine integrierte Version einer Hash-Tabelle verfügen, sind sie eine äußerst nützliche und gängige Datenstruktur. Sie sind in Python als Wörterbücher, in JavaScript als Objekte, in Java, Go und Scala als Maps und in Ruby als Hashes bekannt. Hash-Tabellen werden hauptsächlich verwendet, um Daten in Schlüssel-Wert-Paaren zu speichern. Mit der Möglichkeit, Daten mithilfe des zugehörigen Schlüssels schnell zu finden, sind Hash-Tabellen eine ausgezeichnete Option für den Datenzugriff, das Einfügen und Entfernen. Dies ist eine deutliche Verbesserung gegenüber Arrays, die zwar einen schnellen Zugriff unter Verwendung von Indizes ermöglichen, aber beim Hinzufügen und Entfernen von Elementen einen kostspieligen Zeitaufwand verursachen können.

In den meisten Fällen ist die Verwendung der integrierten Hash-Funktion einer Sprache wahrscheinlich die beste Option, sie können jedoch mithilfe eines Arrays von Grund auf neu modelliert werden. In diesem Fall würden wir den Schlüssel entsprechend den Daten bereitstellen, auf die wir zugreifen möchten. Dieser Schlüssel muss in einen Index umgewandelt werden, in dem das Schlüssel-Wert-Paar gespeichert wird und dann unter Verwendung des Index die gewünschten Daten zurückgegeben werden. Hier kommen Hash-Funktionen ins Spiel.

Hash-Funktionen

Im Allgemeinen nehmen Hashfunktionen eine Eingabe beliebiger Größe und geben eine Ausgabe einer festen Größe zurück; es könnte eine kurze Zeichenfolge oder eine ganze Zahl sein. Diese Funktionen sind „unidirektional“, was bedeutet, dass wir die ursprüngliche Eingabe nicht erstellen können, indem wir von der Ausgabe rückwärts arbeiten. Daher werden in der Kryptographie häufig Hashfunktionen verwendet.

Nehmen wir zur Veranschaulichung an, dass wir eine has-Tabelle verwenden, um Daten zu einer Sammlung von Büchern mit Schlüsseln zu speichern, die den ISBNs der Bücher und den Werten des Buchtitels entsprechen. Unsere Hash-Funktion würde die ISBN als Argument nehmen und einen Index zurückgeben, in dem die Daten zu dieser ISBN gefunden werden könnten. Mit diesem Index können wir den Buchtitel nachschlagen und zurückgeben.

#algorithms #data-structures #hash-table #javascript #hash-function #function

medium.com

Warum sollte die Länge Ihrer Hash-Tabelle eine Primzahl sein?

Und andere Hash-Grundlagen. Jeder gründliche Kurs zu Datenstrukturen und Algorithmen behandelt die Datenstruktur der Hashtabelle und damit auch die Hashfunktionen.

lodash den ersten Buchstaben groß schreiben