Was ist eine Hash-Tabelle?

Eine Hash-Tabelle ist als Datenstruktur definiert, die zum schnellen Einfügen, Nachschlagen und Entfernen von Schlüssel-Wert-Paaren verwendet wird. Es arbeitet auf der Hashing-Konzept , wobei jeder Schlüssel durch eine Hash-Funktion in einen eindeutigen Index in einem Array übersetzt wird. Der Index fungiert als Speicherort für den passenden Wert. Mit einfachen Worten: Es ordnet den Schlüsseln den Wert zu.

Was ist der Lastfaktor?

Der Auslastungsfaktor einer Hash-Tabelle wird dadurch bestimmt, wie viele Elemente dort im Verhältnis zur Größe der Tabelle gespeichert werden. Wenn der Auslastungsfaktor hoch ist, kann die Tabelle unübersichtlich sein und zu längeren Suchzeiten und Kollisionen führen. Durch die Verwendung einer guten Hash-Funktion und die richtige Größenänderung der Tabelle kann ein idealer Auslastungsfaktor aufrechterhalten werden.

Gewerkschaft vs. Gewerkschaft alle

Was ist eine Hash-Funktion?

Eine Funktion, die Schlüssel in Array-Indizes übersetzt, wird als Hash-Funktion bezeichnet. Die Schlüssel sollten über eine gute Hash-Funktion gleichmäßig über das Array verteilt werden, um Kollisionen zu reduzieren und schnelle Suchgeschwindigkeiten zu gewährleisten.

• Annahme eines ganzzahligen Universums: Gemäß der Annahme des Ganzzahluniversums wird davon ausgegangen, dass die Schlüssel ganze Zahlen innerhalb eines bestimmten Bereichs sind. Dies ermöglicht die Verwendung grundlegender Hashing-Operationen wie Divisions- oder Multiplikations-Hashing.
• Hashing nach Division: Diese unkomplizierte Hashing-Technik verwendet den verbleibenden Wert des Schlüssels, nachdem er durch die Größe des Arrays dividiert wurde, als Index. Wenn die Größe eines Arrays eine Primzahl ist und die Schlüssel gleichmäßig verteilt sind, ist die Leistung gut.
• Hashing durch Multiplikation: Bei dieser einfachen Hashing-Operation wird der Schlüssel mit einer Konstante zwischen 0 und 1 multipliziert, bevor der Bruchteil des Ergebnisses ermittelt wird. Danach wird der Index durch Multiplikation der Bruchkomponente mit der Größe des Arrays bestimmt. Außerdem funktioniert es effektiv, wenn die Tasten gleichmäßig verteilt sind.

Auswahl einer Hash-Funktion :

Die Auswahl einer geeigneten Hash-Funktion basiert auf den Eigenschaften der Schlüssel und der beabsichtigten Funktionalität der Hash-Tabelle. Entscheidend ist die Verwendung einer Funktion, die die Tasten gleichmäßig verteilt und Kollisionen reduziert.

Kriterien, anhand derer eine Hash-Funktion ausgewählt wird:

• Um sicherzustellen, dass die Anzahl der Kollisionen auf ein Minimum beschränkt wird, sollte eine gute Hash-Funktion die Schlüssel gleichmäßig in der Hash-Tabelle verteilen. Dies bedeutet, dass für alle Schlüsselpaarungen die Wahrscheinlichkeit, dass zwei Schlüssel an derselben Position in der Tabelle gehasht werden, ziemlich konstant sein sollte.
• Um ein schnelles Hashing und einen schnellen Schlüsselabruf zu ermöglichen, sollte die Hash-Funktion recheneffizient sein.
• Es dürfte eine Herausforderung sein, den Schlüssel aus seinem Hash-Wert abzuleiten. Dadurch ist es weniger wahrscheinlich, dass Versuche, den Schlüssel mithilfe des Hash-Werts zu erraten, erfolgreich sind.
• Eine Hash-Funktion sollte flexibel genug sein, um sich an Änderungen der zu hashenden Daten anzupassen. Beispielsweise muss die Hash-Funktion weiterhin ordnungsgemäß funktionieren, wenn sich die Größe oder das Format der gehashten Schlüssel ändert.

Techniken zur Kollisionsauflösung :

Kollisionen treten auf, wenn zwei oder mehr Schlüssel auf denselben Array-Index verweisen. Verkettung, offene Adressierung und doppeltes Hashing sind einige Techniken zur Lösung von Kollisionen.

• Offene Adressierung : Kollisionen werden behandelt, indem nach dem folgenden leeren Platz in der Tabelle gesucht wird. Wenn der erste Slot bereits belegt ist, wird die Hash-Funktion auf die nachfolgenden Slots angewendet, bis einer leer bleibt. Es gibt verschiedene Möglichkeiten, diesen Ansatz zu verwenden, einschließlich doppeltem Hashing, linearer Sondierung und quadratischer Sondierung.
• Separate Verkettung : Bei der separaten Verkettung ist eine verknüpfte Liste von Objekten vorhanden, die zu jedem Slot in der Hash-Tabelle gehasht werden. Zwei Schlüssel werden in die verknüpfte Liste aufgenommen, wenn sie mit demselben Slot verknüpft sind. Diese Methode ist recht einfach anzuwenden und kann mehrere Kollisionen bewältigen.
• Robin Hood-Hashing: Um die Länge der Kette zu reduzieren, werden Kollisionen beim Robin Hood-Hashing durch das Ausschalten von Schlüsseln behoben. Der Algorithmus vergleicht den Abstand zwischen dem Steckplatz und dem belegten Steckplatz der beiden Schlüssel, wenn ein neuer Schlüssel auf einen bereits belegten Steckplatz hasht. Der vorhandene Schlüssel wird durch den neuen ersetzt, wenn er näher an seinem idealen Steckplatz ist. Dadurch wird der vorhandene Schlüssel seinem idealen Steckplatz näher gebracht. Diese Methode neigt dazu, Kollisionen und die durchschnittliche Kettenlänge zu reduzieren.

Dynamische Größenänderung:

Mit dieser Funktion kann die Hash-Tabelle als Reaktion auf Änderungen in der Anzahl der in der Tabelle enthaltenen Elemente erweitert oder verkleinert werden. Dies fördert einen idealen Auslastungsfaktor und schnelle Suchzeiten.

Tupel Java

Implementierungen der Hash-Tabelle

Python, Java, C++ und Ruby sind nur einige der Programmiersprachen, die Hash-Tabellen unterstützen. Sie können als kundenspezifische Datenstruktur verwendet werden und werden häufig in die Standardbibliothek aufgenommen.

Beispiel – Zeichen im String „geeksforgeeks“ zählen.

In diesem Beispiel verwenden wir eine Hashing-Technik zum Speichern der Anzahl der Zeichenfolgen.

#include  using namespace std; int main() {  //initialize a string  string s='geeksforgeeks';    // Using an array to store the count of each alphabet   // by mapping the character to an index value  int arr[26]={0};    //Storing the count  for(int i=0;i

public class CharacterCount {  public static void main(String[] args) {  // Initialize a string  String s = 'geeksforgeeks';  // Using an array to store the count of each alphabet  // by mapping the character to an index value  int[] arr = new int[26];  // Storing the count  for (int i = 0; i < s.length(); i++) {  arr[s.charAt(i) - 'a']++;  }  // Search the count of the character  char ch = 'e';  // Get count  System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

# Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])>

using System; class Program {  static void Main(string[] args) {  //initialize a string  string s = 'geeksforgeeks';  // Using an array to store the count of each alphabet   // by mapping the character to an index value  int[] arr = new int[26];  //Storing the count  for (int i = 0; i < s.Length; i++) {  arr[s[i] - 'a']++;  }  //Search the count of the character  char ch = 'e';  // get count  Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']);  } }>

// Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) {  arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>

Ausgabe:

The count of e is 4>

Komplexitätsanalyse einer Hash-Tabelle:

Für Such-, Einfüge- und Löschvorgänge haben Hash-Tabellen eine durchschnittliche Zeitkomplexität von O(1). Im schlimmsten Fall können diese Operationen jedoch O(n) Zeit erfordern, wobei n die Anzahl der Elemente in der Tabelle ist.

Anwendungen der Hash-Tabelle:

• Hash-Tabellen werden häufig zum Indizieren und Durchsuchen großer Datenmengen verwendet. Eine Suchmaschine könnte eine Hash-Tabelle verwenden, um die von ihr indizierten Webseiten zu speichern.
• Daten werden normalerweise über Hash-Tabellen im Speicher zwischengespeichert, was einen schnellen Zugriff auf häufig verwendete Informationen ermöglicht.
• Hash-Funktionen werden in der Kryptographie häufig verwendet, um digitale Signaturen zu erstellen, Daten zu validieren und die Datenintegrität zu gewährleisten.
• Hash-Tabellen können zur Implementierung von Datenbankindizes verwendet werden und ermöglichen so einen schnellen Zugriff auf Daten basierend auf Schlüsselwerten.