6.1 Definition der Hash-Tabelle und ihre Struktur
Hash-Tabelle – ist eine Datenstruktur, die es ermöglicht, Elemente schnell zu finden, einzufügen und zu löschen, indem eine Hash-Funktion verwendet wird, um Indizes in einem Array oder einer Liste zu berechnen. Hash-Tabellen werden häufig zur Implementierung von assoziativen Arrays verwendet, die auch als Wörterbücher bekannt sind.
Wichtige Aspekte der Hash-Tabelle
Array – ist die Hauptkomponente der Hash-Tabelle, das Zeiger auf Elemente oder Listen von Elementen speichert.
Hash-Funktion: Eine Funktion, die Wörterbuchschlüssel in Array-Indizes umwandelt.
Kollisionen: Eine Situation, in der zwei verschiedene Schlüssel denselben Hash-Wert haben. Um Kollisionen zu lösen, werden verschiedene Methoden verwendet, wie z. B. Chaining oder Open Addressing.
Beispiel eines Wörterbuchs:
{
"apple": 101,
"banana": 102,
"cherry": 103
}
Beispiel einer Hash-Tabellenstruktur:
| Index | Wert |
|---|---|
| 0 | None |
| 1 | [('apple', 101)] |
| 2 | None |
| 3 | [('banana', 102)] |
| 4 | None |
| 5 | None |
| 6 | None |
| 7 | [('cherry', 103)] |
| 8 | None |
| 9 | None |
6.2 Grundlegende Operationen in der Hash-Tabelle
Grundlegende Operationen in der Hash-Tabelle: Einfügen, Suchen, Löschen
1. Einfügen (Insertion): Der Prozess, ein neues Element (Schlüssel-Wert-Paar) in die Hash-Tabelle einzufügen.
Schritte zum Einfügen:
- Berechne den Hash-Wert des Schlüssels mithilfe der Hash-Funktion.
- Finde den Index im Array basierend auf dem Hash-Wert.
- Wenn am Index im Array bereits ein Element vorhanden ist (Kollision), füge das Element in die Liste ein (im Falle von Chaining) oder finde den nächsten verfügbaren Index (im Falle von Open Addressing).
Beispiel eines Einfügens in eine Hash-Tabelle mit Chaining:
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
# Beispiel der Nutzung:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
2. Suchen (Search): Der Prozess, einen Wert basierend auf einem gegebenen Schlüssel in der Hash-Tabelle zu finden.
Schritte zum Suchen:
- Berechne den Hash-Wert des Schlüssels mithilfe der Hash-Funktion.
- Finde den Index im Array basierend auf dem Hash-Wert.
- Überprüfe das Vorhandensein des Schlüssels in der Liste der Elemente (im Falle von Chaining) oder am Index (im Falle von Open Addressing).
Beispiel einer Suche in einer Hash-Tabelle mit Chaining:
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
# Beispiel der Nutzung:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Ausgabe: 2
print(hash_table.search("grape")) # Ausgabe: None
3. Löschen (Deletion): Der Prozess, ein Element (Schlüssel-Wert-Paar) aus der Hash-Tabelle zu löschen.
Schritte zum Löschen:
- Berechne den Hash-Wert des Schlüssels mithilfe der Hash-Funktion.
- Finde den Index im Array basierend auf dem Hash-Wert.
- Entferne das Element aus der Liste (im Falle von Chaining) oder setze den Wert am Index auf
None(im Falle von Open Addressing).
Beispiel eines Löschens aus einer Hash-Tabelle mit Chaining:
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# Beispiel der Nutzung:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana")) # Ausgabe: None
6.3 Zeitkomplexität der Hash-Tabelle
Zeitkomplexität der Operationen in der Hash-Tabelle
Einfügen (Insertion):
- Durchschnittlicher Fall:
O(1) - Schlechtester Fall:
O(n)(im Falle vieler Kollisionen oder wenn alle Elemente auf dieselbe Stelle fallen)
Suchen (Search):
- Durchschnittlicher Fall:
O(1) - Schlechtester Fall:
O(n)(im Falle vieler Kollisionen oder wenn alle Elemente auf dieselbe Stelle fallen)
Löschen (Deletion):
- Durchschnittlicher Fall:
O(1) - Schlechtester Fall:
O(n)(im Falle vieler Kollisionen oder wenn alle Elemente auf dieselbe Stelle fallen)
Erklärung:
Durchschnittlicher Fall: Im Durchschnittsfall verteilt die Hash-Funktion die Elemente gleichmäßig über die Tabelle, und jedes Element befindet sich in seiner einzigartigen Zelle, was konstante Zugriffszeit O(1) gewährleistet.
Schlechtester Fall: Im schlechtesten Fall fallen alle Elemente in eine Zelle aufgrund einer schlechten Hash-Funktion oder vieler Kollisionen. Dann verwandelt sich die Hash-Tabelle in eine verkettete Liste, und die Zeitkomplexität der Operationen wird O(n).
6.4 Anwendungsbeispiele von Hash-Tabellen
1. Implementierung eines Wörterbuchs (assoziatives Array)
Hash-Tabellen werden häufig zur Implementierung von Wörterbüchern verwendet, die es ermöglichen, Schlüssel-Wert-Paare zu speichern und schnellen Zugriff über den Schlüssel zu gewähren.
Beispiel:
# Erstellen eines Wörterbuchs
dictionary = {}
# Einfügen von Elementen
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3
# Suchen eines Elements
print(dictionary["banana"]) # Ausgabe: 2
# Löschen eines Elements
del dictionary["cherry"]
# Überprüfung der Existenz eines Schlüssels
if "apple" in dictionary:
print("Der Schlüssel 'apple' existiert im Wörterbuch") # Ausgabe: Der Schlüssel 'apple' existiert im Wörterbuch
Jetzt weißt du ein bisschen mehr über das Wörterbuch in Python und wie es funktioniert.
2. Caching von Berechnungsergebnissen
Hash-Tabellen werden verwendet, um die Ergebnisse teurer Berechnungen zu cachen, um nachfolgende Anfragen zu beschleunigen.
Beispiel:
# Cache zum Speichern von Ergebnissen
cache = {}
def expensive_computation(x):
if x in cache:
return cache[x]
result = x * x # Beispiel einer teuren Berechnung
cache[x] = result
return result
# Nutzung des Caches
print(expensive_computation(10)) # Ausgabe: 100 (Berechnung und Caching)
print(expensive_computation(10)) # Ausgabe: 100 (aus dem Cache)
3. Zählen der Wortfrequenz im Text
Hash-Tabellen werden zum Zählen der Häufigkeit jedes Wortes in einem Text verwendet.
Beispiel:
from collections import defaultdict
text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)
for word in text.split():
word_count[word] += 1
# Ausgabe der Ergebnisse
for word, count in word_count.items():
print(f"Das Wort '{word}' erscheint {count} Mal")
4. Suche nach Duplikaten in einer Liste
Hash-Tabellen werden zur effizienten Suche nach Duplikaten in einer Liste verwendet.
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Beispiel der Nutzung
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Ausgabe: [2, 4]
GO TO FULL VERSION