Was ist der Grundgedanke einer Hashtabelle?
Schlüssel werden auf ganzzahlige Indizes abgebildet, und an diesem Index im Array wird eine Markierung (z.B. der Schlüssel selbst oder ein Eintrag) abgelegt. Die Hashtabelle ist im Kern dieses Array. Der Test, ob ein Schlüssel enthalten ist (contains), besteht aus: Hashwert berechnen, auf den Indexbereich abbilden, Arrayzugriff und Prüfen, ob dort etwas gespeichert ist. Das ist konstanter Aufwand O(1) im Average Case. [file:33]
Warum kann man nicht einfach jeden Schlüssel eindeutig auf einen Index im Array abbilden?
Typischerweise ist der Schlüsselraum sehr groß oder sogar unendlich. Eine Eins-zu-eins-Zuordnung Schlüssel <=> Index würde bedeuten, dass das Array extrem groß oder unendlich groß sein müsste. Das ist in der Praxis unmöglich, daher arbeitet man mit einem kleineren Array und Hashfunktionen. [file:33]
Wie wird das Array einer Hashtabelle dimensioniert und wie werden Schlüssel auf Indizes abgebildet?
Das Array der Hashtabelle erhält eine feste Größe M. Zu jedem Schlüssel wird ein Hashwert berechnet und dann per Modulo-Operation auf den Indexbereich 0 bis M-1 abgebildet (z.B. index = hash(key) mod M). So wird der große Schlüsselraum in einen begrenzten Indexbereich projiziert. [file:33]
Welches Problem entsteht durch die Abbildung vieler Schlüssel auf ein Array der Größe M und wie heißt die Standardlösung?
Mehrere verschiedene Schlüssel können auf denselben Arrayindex abgebildet werden, dies nennt man Kollision. Eine Standardlösung ist separate chaining: An jedem Arrayeintrag (Bucket) wird eine Liste von Schlüsseln verwaltet, die alle auf diesen Index gehasht wurden. [file:33]
Wie funktioniert das Einfügen eines Schlüssels k in eine Hashtabelle mit separate chaining (schrittweise)?
1) Berechne den Hashwert des Schlüssels k. 2) Bilde den Hashwert per Modulo auf einen Index im Bereich 0 bis M-1 ab. 3) Gehe zur Liste (Bucket) an diesem Arrayindex. 4) Durchlaufe die Liste und prüfe, ob k bereits enthalten ist. 5) Falls k noch nicht enthalten ist, füge am Ende der Liste einen neuen Eintrag mit k ein. 6) Prüfe ggf., ob durch das Einfügen der maximale Load-Faktor überschritten würde und vergrößere die Tabelle falls nötig. [file:33]
Was ist der Load-Faktor einer Hashtabelle und was bezeichnet ein maximaler Load-Faktor?
Der Load-Faktor ist die durchschnittliche Listenlänge je Bucket und berechnet sich als N / M, wobei N die Anzahl der Schlüssel und M die Anzahl der Buckets (Arrayeinträge) ist. Der maximale Load-Faktor ist eine vorher festgelegte Schranke, die die durchschnittliche Listenlänge begrenzt, um Operationen effizient zu halten. [file:33]
Was passiert beim Einfügen, wenn der maximale Load-Faktor überschritten würde?
1) Die Bucketanzahl M wird um einen Faktor vergrößert (analog zum Vergrößern einer Arrayliste). 2) Es wird ein neues größeres Array angelegt. 3) Alle vorhandenen Schlüssel werden neu gehasht und in die neue Tabelle (mit größerem M) eingetragen (Rehashing). 4) Danach wird der neue Schlüssel k in die vergrößerte Hashtabelle eingefügt. So bleibt der tatsächliche Load-Faktor auch nach dem Einfügen unter der maximalen Schranke. [file:33]
Wie ist die Laufzeitkomplexität für das Einfügen in einer Hashtabelle im Worst Case und im Average Case?
Im Worst Case landen alle N Schlüssel in einem einzigen Bucket, die Liste hat dann Länge N und das Einfügen hat Laufzeit O(N). Im Average Case verteilen sich die Schlüssel annähernd Gleichmäßig über die Buckets. Durch Einhaltung eines maximalen Load-Faktors bleibt die durchschnittliche Listenlänge konstant beschränkt. Die Suche im Bucket und das Einfügen am Ende der Liste sind dann im Durchschnitt O(1). Berücksichtigt man die gelegentlichen Vergrößerungen (Rehashing), ergibt sich amortisiert O(1) für Einfügen im Average Case. [file:33]
Warum ist das Einfügen in einer Hashtabelle amortisiert O(1), obwohl das Vergrößern und Rehashen O(N) kostet?
Die Vergrößerung des Arrays und das Rehashen aller N Schlüssel kosten zwar O(N), treten aber nur selten auf (z.B. wenn der Load-Faktor eine Grenze überschreitet). Dazwischen gibt es viele Einfügungen, die jeweils nur konstanten Aufwand haben. Man kann zeigen, dass der teure Rehash-Aufwand durch die vielen billigen Einfügungen „angespart“ wird. Verteilt man die Gesamtkosten auf alle Einfügungen, erhält man amortisierte Kosten von O(1) pro Einfügen im Average Case. [file:33]
Wie funktioniert die Suche nach einem Schlüssel k in einer Hashtabelle (separate chaining) schrittweise?
1) Berechne den Hashwert des gesuchten Schlüssels k. 2) Bilde den Hashwert per Modulo auf einen Index im Bereich 0 bis M-1 ab. 3) Gehe zum Bucket (Liste) an diesem Arrayindex. 4) Durchlaufe die Liste und vergleiche jeden Eintrag mit k. 5) Falls ein Eintrag mit Schlüssel k gefunden wird, ist die Suche erfolgreich. 6) Falls das Listenende erreicht wird, ohne k zu finden, ist die Suche erfolglos. [file:33]
Welche Laufzeitkomplexität hat die Suche in einer Hashtabelle im Worst Case und im Average Case?
Im Worst Case befinden sich alle N Schlüssel in einem einzigen Bucket, die Liste hat Länge N und die Suche benötigt O(N). Im Average Case verteilen sich die Schlüssel gleichmäßig über die Buckets und der Load-Faktor wird beim Einfügen unterhalb einer festen Schranke gehalten. Dadurch ist die erwartete Listenlänge konstant beschränkt und die durchschnittliche Suche ist in O(1). [file:33]
Wie funktioniert das Löschen eines Schlüssels k aus einer Hashtabelle (separate chaining) schrittweise?
1) Berechne den Hashwert des zu löschenden Schlüssels k. 2) Bilde den Hashwert per Modulo auf einen Index im Bereich 0 bis M-1 ab. 3) Gehe zur Liste (Bucket) an diesem Arrayindex. 4) Durchlaufe die Liste und suche nach einem Eintrag mit Schlüssel k. 5) Wenn ein solcher Eintrag gefunden wird, entferne ihn aus der Liste. 6) Optional: Prüfe, ob der Load-Faktor unter eine untere Schranke fällt und verkleinere ggf. die Hashtabelle (Reorganisation). [file:33]
Was ist die Idee einer Reorganisation beim Löschen in Hashtabellen und wann kann sie sinnvoll sein?
Analog zur Vergrößerung beim Einfügen kann beim Unterschreiten eines bestimmten Load-Faktors das Array verkleinert werden, um Speicher zu sparen und den Load-Faktor wieder zu erhöhen. Dazu wird ein kleineres Array angelegt und alle verbleibenden Schlüssel werden neu gehasht und eingetragen. Die Verkleinerung sollte aber erst erfolgen, wenn die Auslastung wirklich deutlich unter einem Schwellwert liegt, damit Reorganisationen nicht zu häufig auftreten. [file:33]
Wie ist die Laufzeitkomplexität für das Löschen in einer Hashtabelle im Worst Case und im Average Case?
Die Argumentation ist analog zum Einfügen: Im Worst Case befinden sich alle N Schlüssel in einer Liste an einem Index, sodass das Löschen O(N) dauern kann. Im Average Case bleibt die durchschnittliche Listenlänge durch Kontrolle des Load-Faktors konstant beschränkt, sodass das Löschen eines vorhandenen Schlüssels im Durchschnitt O(1) benötigt. Berücksichtigt man ggf. seltene Reorganisationen, ergibt sich amortisiert O(1) im Average Case. [file:33]
Welche Rolle spielt der Hashwert und die Modulo-Operation in einer Hashtabelle?
Der Hashwert bildet den Schlüssel in eine ganzzahlige Zahl ab. Die Modulo-Operation mit der Bucketanzahl M reduziert diesen Wert auf einen Index im Bereich 0 bis M-1. Dadurch wird der große (theoretisch unendliche) Schlüsselraum auf die feste Größe des Arrays projiziert. Eine gute Hashfunktion und geeignete Wahl von M sind wichtig, damit die Schlüssel möglichst gleichmäßig auf die Buckets verteilt werden. [file:33]
Was bedeutet separate chaining in Hashtabellen genau?
Separate chaining ist eine Kollisionsstrategie, bei der jeder Bucket des Arrays eine Liste (oder eine andere dynamische Struktur) von Einträgen enthält. Alle Schlüssel, die auf denselben Index gehasht werden, werden in dieser Liste gespeichert. Beim Einfügen, Suchen oder Löschen wird nur die Liste an einem einzigen Index durchsucht, nicht das gesamte Array. [file:33]
Warum ist die Verteilung der Schlüssel auf die Buckets so wichtig für die Performance einer Hashtabelle?
Wenn sich die Schlüssel gleichmäßig über die Buckets verteilen, bleiben die Listen in den Buckets kurz. Dadurch sind Suchen, Einfügen und Löschen in der Regel O(1). Wenn die Verteilung schlecht ist (z.B. viele Kollisionen an wenigen Buckets), werden manche Listen sehr lang, was die Laufzeiten in Richtung O(N) verschlechtert. Deshalb sind eine gute Hashfunktion, geeignete Wahl von M und Kontrolle des Load-Faktors entscheidend für gute Average-Case-Performance. [file:33]
Last changed9 days ago