Lastfaktor und Rehash

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Der Lastfaktor ist n / Kapazität. Überschreitet er eine Schwelle, reallociert die Tabelle (Rehash): neue Kapazität, Einträge neu verteilen.

Rehash ist amortisiert $O(n)$, hält aber die erwartete Bucketlänge klein.

$$\alpha = n/m$$

Wo gebraucht

Kapazitätsplanung für Caches und Maps: zu voll bedeutet lange Ketten und Rehash-Pausen. In Services sichtbare GC-/Latenzphasen beim Wachsen grosser Maps.

Vertiefung

Der Lastfaktor ist das Verhältnis von gespeicherten Einträgen zur Zahl der Tabellenplätze. Steigt er, wachsen bei Chaining im Mittel die lokalen Sammlungen; bei offener Adressierung werden freie Plätze schwerer erreichbar. Implementierungen definieren deshalb einen Schwellenwert für eine Grössenänderung.

Nach der Vergrösserung müssen alle Einträge anhand der neuen Kapazität erneut einsortiert werden. Das ist ein einzelner teurer Vorgang, tritt aber nur gelegentlich auf. Über viele Einfügungen verteilt bleiben die amortisierten Kosten daher klein, sofern die Kapazität geometrisch wächst.

Schwierigkeitsstufen

Den Lastfaktor aus Eintragszahl und Kapazität berechnen.
Begründen, warum blosses Kopieren an dieselben Indizes falsch ist.
Die amortisierten Kosten geometrischer Vergrösserung erklären.

Fallstricke

Ein gespeicherter Tabellenindex ist keine dauerhafte Eigenschaft eines Schlüssels. Wird die Kapazität geändert, ändert sich meist auch die Indexabbildung. Eine Vergrösserung um jeweils nur einen Platz führt zudem zu zu vielen vollständigen Umbauten.

University approvals: 0

Tasks

Question 1

Was passiert typischerweise bei zu hohem Lastfaktor?

Die JVM beendet sich

Rehash auf grössere Tabelle

equals wird abgeschaltet

Nur BFS startet

Question 2

Warum müssen Einträge nach einer Kapazitätsänderung neu einsortiert werden?

Weil sich die Schlüsselwerte beim Vergrössern ändern.

Weil die Indexberechnung von der Tabellenlänge abhängt.

Weil equals nach jeder Einfügung neu definiert wird.

Weil nur neue Einträge Hashwerte besitzen.

Question 3

Implementiere needsRehash. Ein Rehash ist nötig, wenn size geteilt durch capacity grösser als maxLoad ist.

Hint

Mindestens einen Operanden musst du nach double casten, damit Java keine Ganzzahldivision ausführt.

class LoadFactor {
  static boolean needsRehash(int size, int capacity, double maxLoad) {
    // TODO
    return false;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy