Was ist Hashing? Wie Hash-Codes funktionieren - mit Beispielen

Einführung in das Hashing

Hashing wurde entwickelt, um das Problem zu lösen, dass ein Gegenstand in einer Sammlung effizient gefunden oder gespeichert werden muss.

Wenn wir beispielsweise eine Liste mit 10.000 englischen Wörtern haben und prüfen möchten, ob ein bestimmtes Wort in der Liste enthalten ist, ist es ineffizient, das Wort nacheinander mit allen 10.000 Elementen zu vergleichen, bis wir eine Übereinstimmung finden. Selbst wenn die Liste der Wörter wie in einem Wörterbuch lexikografisch sortiert ist, benötigen Sie noch einige Zeit, um das gesuchte Wort zu finden.

Hashing ist eine Technik, um die Dinge effizienter zu gestalten, indem die Suche von Anfang an effektiv eingegrenzt wird.

Was ist Hashing?

Hashing bedeutet, eine Funktion oder einen Algorithmus zu verwenden, um Objektdaten einem repräsentativen ganzzahligen Wert zuzuordnen.

Dieser sogenannte Hash-Code (oder einfach Hash) kann dann verwendet werden, um unsere Suche bei der Suche nach dem Element in der Karte einzugrenzen.

Im Allgemeinen werden diese Hash-Codes verwendet, um einen Index zu generieren, in dem der Wert gespeichert wird.

Wie Hashing funktioniert

In Hash-Tabellen speichern Sie Daten in Form von Schlüssel- und Wertepaaren. Der Schlüssel, mit dem die Daten identifiziert werden, wird als Eingabe für die Hashing-Funktion angegeben. Der Hash-Code, der eine Ganzzahl ist, wird dann der festen Größe zugeordnet, die wir haben.

Hash-Tabellen müssen 3 Funktionen unterstützen.

  • einfügen (Schlüssel, Wert)
  • get (Schlüssel)
  • löschen (Schlüssel)

Nehmen wir als Beispiel an, um das Konzept besser zu verstehen, nehmen wir an, wir möchten eine Liste von Zeichenfolgenschlüsseln Zeichenfolgenwerten zuordnen (z. B. eine Liste von Ländern ihren Hauptstädten zuordnen).

Nehmen wir also an, wir möchten die Daten in der Tabelle in der Karte speichern.

Nehmen wir an, unsere Hash-Funktion besteht darin, einfach die Länge des Strings zu nehmen.

Der Einfachheit halber werden wir zwei Arrays haben: eines für unsere Schlüssel und eines für die Werte.

Um ein Element in die Hash-Tabelle aufzunehmen, berechnen wir seinen Hash-Code (in diesem Fall zählen Sie einfach die Anzahl der Zeichen) und setzen dann den Schlüssel und den Wert in die Arrays am entsprechenden Index.

Zum Beispiel hat Kuba einen Hash-Code (Länge) von 4. Also speichern wir Kuba an der 4. Position im Schlüssel-Array und Havanna an der 4. Stelle des Werte-Arrays usw. Und am Ende haben wir Folgendes:

In diesem speziellen Beispiel funktionieren die Dinge recht gut. Unser Array muss groß genug sein, um die längste Zeichenfolge aufzunehmen, aber in diesem Fall sind das nur 11 Steckplätze.

Wir verschwenden etwas Platz, weil unsere Daten beispielsweise keine 1-Buchstaben-Schlüssel oder Schlüssel zwischen 8 und 10 Buchstaben enthalten.

Aber in diesem Fall ist der verschwendete Platz auch nicht so schlecht. Die Länge eines Strings zu nehmen ist schön und schnell, ebenso wie das Finden des Werts, der einem bestimmten Schlüssel zugeordnet ist (sicherlich schneller als bis zu fünf String-Vergleiche).

Was tun wir jedoch, wenn unser Datensatz eine Zeichenfolge mit mehr als 11 Zeichen enthält?

Was ist, wenn wir ein anderes Wort mit 5 Zeichen, "Indien", haben und versuchen, es mit unserer Hash-Funktion einem Index zuzuweisen? Da der Index 5 bereits belegt ist, müssen wir uns überlegen, was wir damit machen sollen. Dies wird als Kollision bezeichnet.

Wenn unser Datensatz eine Zeichenfolge mit tausend Zeichen hätte und Sie ein Array von tausend Indizes zum Speichern der Daten erstellen, würde dies zu einer Verschwendung von Speicherplatz führen. Wenn unsere Schlüssel zufällige Wörter aus dem Englischen wären, wo es so viele Wörter mit derselben Länge gibt, wäre die Verwendung der Länge als Hashing-Funktion ziemlich nutzlos.

Kollisionsbehandlung

Zwei grundlegende Methoden werden verwendet, um Kollisionen zu behandeln.

  1. Separate Verkettung
  2. Adressierung öffnen

Separate Verkettung

Die Behandlung von Hash-Kollisionen durch separate Verkettung verwendet eine zusätzliche Datenstruktur, vorzugsweise eine verknüpfte Liste für die dynamische Zuordnung, in Buckets. Wenn wir in unserem Beispiel Indien zum Datensatz hinzufügen, wird es an die im Index 5 gespeicherte verknüpfte Liste angehängt. Dann sieht unsere Tabelle folgendermaßen aus.

Um einen Gegenstand zu finden, gehen wir zuerst zum Eimer und vergleichen dann die Schlüssel. Dies ist eine beliebte Methode, und wenn eine Liste von Links verwendet wird, füllt sich der Hash nie. Die Kosten für get(k)sind im Durchschnitt, O(n)wobei n die Anzahl der Schlüssel im Eimer ist, die Gesamtzahl der Schlüssel N.

Das Problem bei der separaten Verkettung besteht darin, dass die Datenstruktur unbegrenzt wachsen kann.

Adressierung öffnen

Durch die offene Adressierung wird keine neue Datenstruktur eingeführt. Wenn eine Kollision auftritt, suchen wir nach der Verfügbarkeit an der nächsten Stelle, die von einem Algorithmus generiert wird. Open Addressing wird im Allgemeinen verwendet, wenn der Speicherplatz begrenzt ist, dh eingebettete Prozessoren. Offene Adressierung nicht unbedingt schneller als separate Verkettung.

Methoden zur offenen Adressierung

  • [Lineare Abtastung
  • Quadratische Prüfung
  • Double Hashing

So verwenden Sie Hashing in Ihrem Code.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:Rakete:

Code ausführen

Java

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:Rakete:

Code ausführen

Weitere Infos zum Hashing

  • Die codelose Anleitung zu Hashing- und Hash-Tabellen
  • So implementieren Sie eine einfache Hash-Tabelle in JavaScript
  • Hash-Tabellen erklärt