Probleme von Kollisionen und Methoden zu ihrer Lösung

7.1 Definition von Kollisionen in einer Hash-Tabelle

Kollision in einer Hash-Tabelle tritt auf, wenn zwei verschiedene Schlüssel auf den gleichen Index im Array gehasht werden. Dies führt dazu, dass mehr als ein Element versucht, dieselbe Zelle in der Hash-Tabelle zu besetzen.

Beispiel einer Kollision:

Angenommen, wir haben eine einfache Hash-Funktion, die den Rest des Schlüssels durch die Größe der Tabelle zurückgibt. Für die Schlüssel 5 und 15 bei einer Tabellengröße von 10 ergeben beide Schlüssel den gleichen Index: 5 % 10 = 5 und 15 % 10 = 5. Das ist eine Kollision.

Ein weiteres Beispiel:

Angenommen, du erstellst ein Namensverzeichnis und hast eine einfache Hash-Funktion, die den ersten Buchstaben des Namens zurückgibt. Aber es stellt sich heraus, dass 80% der Namen mit dem Buchstaben „A“ beginnen. Das ist nicht nur eine Kollision, das ist ein Problem.

7.2 Methoden zur Kollision-Behebung – Verkettung

Es gibt mehrere Methoden zur Lösung von Kollisionen in Hash-Tabellen. Die zwei häufigsten Methoden sind Verkettung (chaining) und offene Adressierung (open addressing).

Verkettung (Chaining)

Vorteile:

• Einfache Implementierung.
• Effektiv bei einer geringen Anzahl von Kollisionen.
• Weniger abhängig von der Füllrate der Hash-Tabelle.

Nachteile:

• Benötigt zusätzlichen Speicher für Zeiger in der verketteten Liste.
• Die Leistung kann bei vielen Kollisionen aufgrund langer Ketten sinken.

Beispiel der Implementierung des Verkettungsverfahrens:

Du kannst nur die Besonderheit der Funktion insert untersuchen, aber ich habe den vollständigen Code aus Bequemlichkeit beigefügt.

class HashTableChaining:
    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 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

    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 = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Ausgabe: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Ausgabe: None

7.3 Methode Nummer zwei – offene Adressierung

Offene Adressierung bedeutet die Suche nach der nächsten verfügbaren Zelle im Array, wenn eine Kollision auftritt. Es gibt verschiedene Strategien zur Suche nach einer neuen Zelle: lineare Sondierung, quadratische Sondierung und doppeltes Hashing.

Vorteile:

• Benötigt keinen zusätzlichen Speicher für Zeiger.
• Kompaktere Datenrepräsentation.

Nachteile:

• Die Leistung kann bei hoher Füllrate der Tabelle erheblich sinken.
• Benötigt mehr Rechenressourcen zur Kollision-Behebung.

Beispiele für Strategien der offenen Adressierung

Lineare Sondierung (Linear Probing):

• Sondierung mit Schrittweite 1: index = (index + 1) % size.
• Einfach, kann aber zur „Clusterbildung“ führen.

Quadratische Sondierung (Quadratic Probing):

• Sondierung mit quadratisch wachsendem Schritt: index = (index + i^2) % size.
• Reduziert das Problem der Clusterbildung, aber schwieriger zu implementieren.

Doppeltes Hashing (Double Hashing):

• Nutzung einer zweiten Hash-Funktion zur Berechnung des Schritts: index = (index + i * hash2(key)) % size.
• Weniger Probleme mit Clusterbildung, aber schwieriger zu implementieren.

Beispiel der Implementierung der offenen Adressierung (lineare Sondierung): Ich bringe den vollständigen funktionierenden Code, zur Einfachheit kannst du nur die Funktion insert untersuchen.

class HashTableOpenAddressing:
    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)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None
                return
            index = (index + 1) % self.size
            if index == original_index:
                break

# Beispiel der Nutzung:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Ausgabe: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # Ausgabe: None

7.4 Einfluss von Kollisionen auf eine Hash-Tabelle

Einfluss von Kollisionen auf die Leistung.

Mittlere Zugriffszeit:

• Unter idealen Bedingungen (keine Kollisionen) beträgt die mittlere Zugriffszeit auf die Elemente in einer Hash-Tabelle O(1).
• Kollisionen erhöhen die Zugriffszeit, da die Verarbeitung von Ketten oder die Sondierung von Zellen erforderlich ist, was die Anzahl der Operationen erhöht.

Verlängerung der Ketten:

• Im Verkettungsverfahren kann die Verlängerung der Ketten bei vielen Kollisionen zu einer linearen Zugriffszeit O(n) für Such-, Einfüge- und Löschvorgänge führen.
• Lange Ketten erhöhen die Anzahl der Vergleiche, die für die Suche oder das Einfügen eines Elements erforderlich sind.

Speicherkomplexität:

• Im Verkettungsverfahren wird zusätzlicher Speicher für die Speicherung von Zeigern in verketteten Listen benötigt.
• Im Verfahren der offenen Adressierung erhöht eine Tabellenauslastung über einem bestimmten Niveau (meist etwa 70-80%) die Anzahl der Kollisionen erheblich und damit die Zugriffszeit.

Clusterbildung: Im Verfahren der offenen Adressierung (insbesondere bei linearer Sondierung) kommt es zur Clusterbildung, wenn mehrere aufeinanderfolgende Zellen belegt werden, was die Wahrscheinlichkeit von Kollisionen erhöht und die Leistung verschlechtert.

Beispielanalyse des Einflusses von Kollisionen auf die Leistung:

Das ist direkt für diejenigen, die tiefer einsteigen wollen

import time
import random

# Lineare Sondierung
class HashTableOpenAddressing:
    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)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size
            if index == original_index:
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:
                break
        return None

# Generierung einer großen Datenmenge zum Einfügen
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# Einfügen von Daten und Messung der Zeit
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"Einfügezeit: {time.time() - start_time:.6f} Sekunden")

# Suchen von Daten und Messung der Zeit
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"Suchzeit: {time.time() - start_time:.6f} Sekunden")