Aus welchen Komponenten besteht eine Hashtabelle?

Eine Hashtabelle besteht aus zwei Hauptkomponenten:

1. Array (oder Liste) von Zellen (Buckets): Dies ist die Hauptspeicherstruktur. Jede Zelle kann ein oder mehrere Datenelemente (Schlüssel-Wert-Paare) enthalten.

2. Hash-Funktion: Ein Algorithmus, der den Eingabeschlüssel in einen numerischen Index umwandelt, der verwendet wird, um die Zelle zu bestimmen, in der das entsprechende Datenelement gespeichert oder gefunden werden soll.

Außerdem werden Mechanismen wie verwendet, um Kollisionen aufzulösen (Situationen, in denen verschiedene Schlüssel auf denselben Index hashiert werden):

• Kettungsmethode: In jeder Zelle wird eine Liste (z.B. eine verkettete Liste) der dort hashierten Elemente gespeichert.
• Offene Adressierung: Bei Kollision sucht der Algorithmus die nächste freie Zelle nach einer bestimmten Strategie (lineares Sondieren, quadratisches Sondieren, doppelte Hashing).

# Beispiel einer einfachen Hash-Funktion
def simple_hash(schlüssel, array_größe):
    # Umwandlung des Schlüssels in eine Zahl
    if isinstance(schlüssel, str):
        hash_wert = sum(ord(zeichen) for zeichen in schlüssel)
    elif isinstance(schlüssel, int):
        hash_wert = schlüssel
    else:
        raise TypeError("Nicht unterstützter Schlüsseltyp")

    # Rückgabe des Index innerhalb der Array-Größe
    return hash_wert % array_größe

# Beispiel für eine Komponente des Array von Zellen für die Kettungsmethode
class HashTable:
    def __init__(self, größe):
        self.größe = größe
        self.array = [[] for _ in range(self.größe)] # Array von Listen (Kettungen)

    def einfügen(self, schlüssel, wert):
        index = simple_hash(schlüssel, self.größe)
        self.array[index].append((schlüssel, wert)) # Hinzufügen des Schlüssel-Wert-Paares zur Liste

    def suchen(self, schlüssel):
        index = simple_hash(schlüssel, self.größe)
        for k, v in self.array[index]:
            if k == schlüssel:
                return v
        return None # Schlüssel nicht gefunden