Kursinhalt
Überblick Über Algorithmen und Datenstrukturen
Überblick Über Algorithmen und Datenstrukturen
Hashtabelle
Eine Hashtabelle, auch bekannt als Hashmap oder assoziatives Array, ist eine Datenstruktur, die Schlüssel-Wert-Paare speichert. Sie bietet effiziente Einfüge-, Lösch- und Suchoperationen, indem sie Schlüssel durch einen Prozess namens Hashing den entsprechenden Werten zuordnet.
Die Hashtabelle kann mit verschiedenen Datenstrukturen implementiert werden, wird jedoch häufiger mit Arrays implementiert und definiert drei Operationen: Einfügen, Löschen und Suchen eines gegebenen Elements.
Hinweis
Die Dictionary-Datenstruktur von Python implementiert eine Hashtabelle und bietet eine effiziente Speicherung und Abfrage von Schlüssel-Wert-Paaren.
Zeitkomplexität der grundlegenden Operationen
Kollisionen
Es kann jedoch vorkommen, dass die Hash-Werte für zwei oder mehr verschiedene Schlüssel gleich sind. Dies wird als Kollision bezeichnet. Daher benötigen wir Methoden, um dieses Problem zu lösen, und es gibt zwei Hauptansätze dafür.
Der erste ist die Verwendung eines Verkettungsmechanismus. Wenn wir eine Kollision haben (wenn sich bereits ein Element im Array-Slot mit einem durch die Hash-Funktion generierten Index befindet), fügen wir das neue Element als nächstes Element in der Liste ein, die mit diesem Array-Index oder Dictionary-Schlüssel verknüpft ist.
import numpy as np class HashTable: def __init__(self, size): # Initialize the hash table with a specified size self.size = size # Create a dictionary where each key corresponds to an index in the hash table # and each value is an empty numpy array self.table = {i: np.array([]) for i in range(size)} def hash_function(self, key): # Simple modular hashing function to determine the index for a given key return key % self.size def insert(self, key, value): # Compute the index using the hash function index = self.hash_function(key) # Check if the array at the computed index is empty if len(self.table[index]) == 0: # If empty, initialize the array with a tuple containing the key-value pair self.table[index] = np.array([(key, value)]) else: # If not empty, append the key-value pair to the existing array self.table[index] = np.append(self.table[index], np.array([(key, value)])) print(f"The element with value {value} inserted into a hash table at index {index}") # Define key-value pairs pairs = [ {'Phone': 12345, 'Name': 'Will'}, {'Phone': 13492, 'Name': 'Sam'}, {'Phone': 23770, 'Name': 'Mike'}, {'Phone': 12345, 'Name': 'Jack'} ] # Initialize the hash table hash_table = HashTable(size=7) # Insert key-value pairs into the hash table for pair in pairs: hash_table.insert(pair['Phone'], pair['Name'])
Beim Verkettungsansatz tritt das Worst-Case-Szenario auf, wenn eine schlecht gestaltete Hashfunktion dazu führt, dass alle Schlüssel auf denselben Index hashen. Dies führt dazu, dass die Hashtabelle im Wesentlichen als reguläres Array fungiert, was zu einer O(N)-Zeitkomplexität für Einfüge-, Such- und Löschoperationen führt.
Verkettung wird typischerweise eingesetzt, wenn die Anzahl der Schlüssel voraussichtlich die für das zugrunde liegende Array zugewiesene Speichermenge bei weitem übersteigt und die genaue Anzahl der Schlüssel unsicher ist. Eine gut gestaltete Hashfunktion ist entscheidend, um sicherzustellen, dass die Operationen mit einer durchschnittlichen Zeitkomplexität ausgeführt werden.
Offene Adressierung
Der zweite Ansatz wird offene Adressierung genannt. In diesem Fall, wenn eine Kollision auftritt und der Wert bereits im Slot mit dem vom Hash-Algorithmus generierten Index vorhanden ist, generieren wir einen neuen Index und versuchen den entsprechenden Slot, bis wir einen verfügbaren finden.
Wir können verschiedene Methoden der offenen Adressierung implementieren:
- lineares Sondieren (wenn wir einen Index um 1 erhöhen);
- quadratisches Sondieren (wenn wir einen Index um den Grad 2 erhöhen);
- doppeltes Hashing (wenn wir einen neuen Hash-Wert basierend auf dem vorherigen generieren).
import numpy as np class HashTable: def __init__(self, size): # Define an empty dictionary to represent the hash table self.table = {} # Initialize the hash table with 'None' values for each index for i in range(size): self.table[i] = None def hash_function(self, key): # Simple modular hash function return key % len(self.table) def insert(self, key, value): index = self.hash_function(key) # Check if the current index is available if self.table[index] is None: self.table[index] = value else: # Perform linear probing until an available index is found while self.table[index] is not None: print(f'Index {index} is already occupied. Trying index {index + 1}') index += 1 self.table[index] = value print(f'The element with value {value} inserted into a hash table at index {index}') # Define key-value pairs pairs = [ {'Phone': 12345, 'Name': 'Will'}, {'Phone': 13492, 'Name': 'Sam'}, {'Phone': 23770, 'Name': 'Mike'}, {'Phone': 12345, 'Name': 'Jack'} ] # Initialize the hash table hash_table = HashTable(size=7) # Insert key-value pairs into the hash table for pair in pairs: hash_table.insert(pair['Phone'], pair['Name'])
Dies ist ein effizienterer Ansatz im Vergleich zum Chaining, aber es kann vorkommen, dass die Werte in unserem zugrunde liegenden Array ungleich verteilt sind und es große Cluster gibt. In diesem Fall nimmt die Effektivität dieses Ansatzes ab.
Daher können wir zu dem Schluss kommen, dass beide Ansätze in ihrer Effektivität stark von einer guten Implementierung einer Hash-Funktion abhängen. Eine gute Hash-Funktion zu erstellen, ist ein großes Problem in der Informatik. Wir möchten eine Hash-Funktion haben, die uns eine gleichmäßige Verteilung der Elemente in einer Datenstruktur bietet.
Danke für Ihr Feedback!
