DBMS - Hashing: Ein Anfängerleitfaden

Hallo, zukünftige Datenbank-Zauberer! Heute tauchen wir in die magische Welt der Hashing in Datenbank-Management-Systemen (DBMS) ein. Keine Sorge, wenn du noch nie eine Zeile Code geschrieben hast – ich werde dein freundlicher Guide auf diesem Abenteuer sein. Also, hol dir deine virtuellen Zauberstäbe (Tastaturen) und los geht's!

Was ist Hashing?

Bevor wir ins Detail gehen, lassen Sie uns verstehen, worum es bei Hashing geht. Stell dir vor, du organisierst eine riesige Bibliothek. Anstatt Bücher alphabetisch zu ordnen, entscheidest du dich, jedem Buch eine eindeutige Nummer basierend auf seinem Titel zu geben. Das ist im Grunde genommen, was Hashing in Datenbanken macht – es konvertiert Daten in eine festgelegte Größe (genannt Hash) für eine einfachere Speicherung und Abrufung.

Ein einfaches Hashing-Beispiel

Lassen Sie uns mit einem einfachen Python-Beispiel beginnen, um Hashing zu veranschaulichen:

def simple_hash(string):
total = 0
for char in string:
total += ord(char)
return total % 10

print(simple_hash("Hello"))  # Ausgabe: 2
print(simple_hash("World"))  # Ausgabe: 7

In diesem Beispiel erstellen wir eine sehr einfache Hash-Funktion. Sie addiert die ASCII-Werte jedes Zeichens in der Zeichenkette und verwendet den Modulo-Operator, um eine Zahl zwischen 0 und 9 zu erhalten. Dies ist eine sehr grundlegende Form von Hashing, aber sie gibt dir eine Vorstellung davon, wie es funktioniert.

Hash-Organisation

Nun, da wir ein grundlegendes Verständnis von Hashing haben, schauen wir uns an, wie es in Datenbanken organisiert ist.

Hash-Tabellen

Hash-Tabellen sind das Rückgrat der Hash-Organisation. Stell dir eine schicke Tabelle vor, bei der jedes Element (oft als Bucket bezeichnet) mehrere Artikel speichern kann.

Hier ist eine einfache Implementierung einer Hash-Tabelle in Python:

class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
return hash(key) % self.size

def insert(self, key, value):
hash_key = self.hash_function(key)
self.table[hash_key].append((key, value))

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.table[hash_key]:
if k == key:
return v
return None

# Verwendung unserer Hash-Tabelle
ht = HashTable(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple"))  # Ausgabe: 5
print(ht.get("grape"))  # Ausgabe: None

Diese Hash-Tabelle verwendet die eingebettete hash()-Funktion von Python und Modulo, um zu bestimmen, wo jedes Schlüssel-Wert-Paar gespeichert werden soll. Wenn wir einen Wert abrufen möchten, verwenden wir den gleichen Prozess, um zu finden, wo er gespeichert sein sollte.

Statisches Hashing

Statisches Hashing ist wie das Besitzen einer festen Anzahl von Regalen in deiner Bibliothek. Du weißt genau, wie viele Bücher du speichern kannst, aber du könntest in Schwierigkeiten geraten, wenn du zu viele Bücher zu einem Thema bekommst.

Vor- und Nachteile des statischen Hashings

Vor- und Nachteile	Nachteile
Einfach zu implementieren	Kann zu einer ungleichen Verteilung führen
Schnell für kleine Datensätze	Nicht flexibel für wachsende Datensätze
Vorhersehbares Verhalten	Kann Platz verschwenden

Bucket-Überlauf

Manchmal könnte unsere Hash-Funktion zu viele Elemente in denselben Bucket schicken. Dies wird als Bucket-Überlauf bezeichnet und ist wie das Versuchen, zu viele Bücher auf ein Regal zu packen.

Umgang mit Überläufen

Es gibt mehrere Möglichkeiten, Überläufe zu behandeln:

1. Chaining: Jeder Bucket enthält eine verkettete Liste von Einträgen.
2. Offene Adressierung: Wenn ein Bucket voll ist, suchen wir nach dem nächsten leeren Bucket.

Lassen Sie uns Chaining in unserer vorherigen Hash-Tabelle implementieren:

class ChainedHashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(self.size)]

def hash_function(self, key):
return hash(key) % self.size

def insert(self, key, value):
hash_key = self.hash_function(key)
for item in self.table[hash_key]:
if item[0] == key:
item[1] = value
return
self.table[hash_key].append([key, value])

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.table[hash_key]:
if k == key:
return v
return None

# Verwendung unserer verketteten Hash-Tabelle
cht = ChainedHashTable(10)
cht.insert("apple", 5)
cht.insert("banana", 7)
cht.insert("cherry", 3)
print(cht.get("apple"))  # Ausgabe: 5
print(cht.get("cherry"))  # Ausgabe: 3

In dieser Implementierung kann jeder Bucket mehrere Schlüssel-Wert-Paare enthalten, was das Überlaufproblem löst.

Dynamisches Hashing

Dynamisches Hashing ist wie das Besitzen einer magischen Bibliothek, die neue Regale wächst, wenn du sie benötigst. Es ist flexibler als statisches Hashing und kann sich an wachsende Datensätze anpassen.

Erweiterbares Hashing

Eine beliebte Form des dynamischen Hashings ist das erweiterbare Hashing. Es verwendet eine Verzeichnisstruktur, die wachsen oder schrumpfen kann, je nachdem, was erforderlich ist.

Hier ist eine vereinfachte Implementierung von erweiterbarem Hashing:

class ExtendibleHashTable:
def __init__(self, bucket_size=2):
self.bucket_size = bucket_size
self.global_depth = 1
self.directory = [[] for _ in range(2**self.global_depth)]

def hash_function(self, key):
return hash(key) % (2**self.global_depth)

def insert(self, key, value):
hash_key = self.hash_function(key)
if len(self.directory[hash_key]) < self.bucket_size:
self.directory[hash_key].append((key, value))
else:
self._split(hash_key)
self.insert(key, value)

def _split(self, index):
self.global_depth += 1
new_directory = [[] for _ in range(2**self.global_depth)]
for i, bucket in enumerate(self.directory):
new_index = i if i < index else i + 2**(self.global_depth-1)
new_directory[new_index] = bucket
self.directory = new_directory

def get(self, key):
hash_key = self.hash_function(key)
for k, v in self.directory[hash_key]:
if k == key:
return v
return None

# Verwendung unserer erweiterbaren Hash-Tabelle
eht = ExtendibleHashTable()
eht.insert("apple", 5)
eht.insert("banana", 7)
eht.insert("cherry", 3)
eht.insert("date", 9)
print(eht.get("apple"))  # Ausgabe: 5
print(eht.get("date"))   # Ausgabe: 9

Diese Implementierung ermöglicht es der Hash-Tabelle, dynamisch zu wachsen, wenn mehr Elemente hinzugefügt werden.

Organisation und Operationen

Nun, da wir die Grundlagen des Hashings und einige Implementierungen behandelt haben, lassen Sie uns die wichtigsten Operationen und ihre Komplexitäten zusammenfassen:

Operation	Durchschnittliche Zeitkomplexität	Schlimmster Fall
Einfügen	O(1)	O(n)
Löschen	O(1)	O(n)
Suchen	O(1)	O(n)

Der Durchschnittsfall ist normalerweise sehr schnell, was Hashing so beliebt macht. Im schlimmsten Fall (wenn alle Elemente in denselben Bucket hashen) kann die Leistung jedoch auf die eines verketteten Listen zurückfallen.

Schlussfolgerung

Glückwunsch! Du hast deine ersten Schritte in die Welt des Hashings in DBMS gemacht. Denke daran, dass Hashing darum geht, ein Gleichgewicht zwischen Geschwindigkeit und Speicherplatz zu finden. Es ist ein mächtiges Werkzeug, das, wenn es richtig eingesetzt wird, die Geschwindigkeit deiner Datenbankoperationen erheblich verbessern kann.

Während du deine Reise im Bereich Informatik fortsetzt, wirst du Hashing in vielen anderen Kontexten begegnen – von Passwortspeicherung bis hin zu Caching-Systemen. Jedes Mal, wenn du ein Wörterbuch in Python oder ein Objekt in JavaScript verwendest, profitierst du vom Zauber des Hashings!

Weiters üben, neugierig bleiben und viel Spaß beim Programmieren!

Credits: Image by storyset