Wie funktioniert eine Hashtabelle?

Eine Hashtabelle (hash table) ist eine Datenstruktur, die ein assoziatives Array implementiert.

Funktionsprinzip:

1. Hashing. Für jeden Schlüssel (key) wird ein Hash-Code (hash code) mit einer Hash-Funktion (hash function) berechnet. Der Hash-Code ist eine ganze Zahl.
2. Indexierung. Der Hash-Code wird verwendet, um einen Index (index) im Array (oder Vektor) der internen Struktur der Hashtabelle zu bestimmen. Der Index wird üblicherweise als hash_code % array_size berechnet, wobei array_size die Größe des Arrays ist.
3. Speicherung. An dem gefundenen Index wird der mit dem Schlüssel verknüpfte Wert (value) gespeichert.

Probleme und Lösungen:

• Kollisionen. Verschiedene Schlüssel können denselben Hash-Code ergeben und somit denselben Index im Array. Dies nennt man Kollision.
  • Methoden zur Lösung von Kollisionen:
    • Kettenmethode (Separate Chaining): In jeder Zelle des Arrays wird eine Liste (Liste, Vektor, etc.) von "Schlüssel-Wert"-Paaren gespeichert. Bei Kollision wird das neue Paar zu dieser Liste hinzugefügt. Bei der Suche nach einem Index wird die entsprechende Liste durchlaufen, um den gewünschten Schlüssel zu finden.
    • Offene Adressierung (Open Addressing): Bei Kollision wird nach einer anderen freien Zelle im Array gesucht, nach einer bestimmten Regel (Sondierung).
      • Lineare Sondierung (Linear Probing): Es werden sequenziell die Zellen index + 1, index + 2, etc., modulo der Array-Größe überprüft.
      • Quadratische Sondierung (Quadratic Probing): Es werden die Zellen index + 1^2, index + 2^2, etc., modulo der Array-Größe überprüft.
      • Doppeltes Hashing (Double Hashing): Es wird eine zweite Hash-Funktion verwendet, um den Schritt der Sondierung zu bestimmen.

Vorteile:

• Im Durchschnitt werden Einfüge-, Lösch- und Suchoperationen mit einer Komplexität von O(1) durchgeführt.

Nachteile:

• Im schlimmsten Fall (z.B. bei vielen Kollisionen oder schlechter Hash-Funktion) kann die Komplexität O(n) erreichen, wobei n die Anzahl der Elemente ist.
• Es wird zusätzlicher Speicher benötigt (z.B. für Listen bei der Kettenmethode oder für die Sondierung bei offener Adressierung).

Beispiel für die Verwendung in C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Erstellen einer Hashtabelle (unordered_map)
    std::unordered_map<std::string, int> alter;

    // Elemente einfügen
    alter["Alice"] = 30;
    alter["Bob"] = 25;
    alter["Charlie"] = 35;

    // Wert anhand des Schlüssels abrufen
    std::cout << "Alter von Alice: " << alter["Alice"] << std::endl;

    // Element suchen
    if (alter.count("Bob")) {
        std::cout << "Bob ist in der Tabelle." << std::endl;
    }

    // Element entfernen
    alter.erase("Charlie");

    return 0;
}