Hashing: Idee und Buckets

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Hashing bildet Schlüssel auf Bucketindizes ab. Erwartete Zugriffszeit ist $O(1)$, wenn die Hashfunktion streut und die Tabelle nicht überfüllt ist.

Schlechte Hashfunktionen oder extreme Lastfaktoren führen zu Ketten und $O(n)$-Verhalten.

$$i = h(k) \bmod m$$

Index statt Doppelsschleife: Two Sum [1].

Wo gebraucht

Dictionaries, Caches, Datenbank-Hash-Joins, Deduplizierung, Streuen von Shards. Hashing ist der Standardweg von Key zu Slot.

Vertiefung

Eine Hashtabelle bildet einen Schlüssel zunächst auf einen ganzzahligen Hashwert und daraus auf einen Tabellenplatz ab. Ein Bucket ist der Bereich, in dem Einträge mit demselben berechneten Index verwaltet werden. Gute Verteilung reduziert die durchschnittliche Zahl der dort zu prüfenden Schlüssel.

Der Hashwert ersetzt den Gleichheitsvergleich nicht. Er grenzt nur die Kandidaten ein; innerhalb des Buckets muss weiterhin die definierte Schlüsselgleichheit geprüft werden. Die erwartete konstante Zugriffszeit setzt eine geeignete Hashfunktion und eine kontrollierte Belegung voraus.

Schwierigkeitsstufen

Aus Hashwert und Tabellenlänge einen gültigen Index berechnen.
Erklären, warum Kollisionen trotz guter Verteilung unvermeidbar sind.
Eingabemuster beurteilen, die viele Schlüssel auf wenige Buckets konzentrieren.

Fallstricke

Der Restoperator kann bei negativen Hashwerten einen negativen Wert liefern. Ausserdem ist ein identischer Hash kein Beweis für identische Schlüssel, sondern nur ein Anlass für den eigentlichen Vergleich.

Sources

[1]https://leetcode.com/problems/two-sum/Return to text

University approvals: 0

Tasks

Question 1

Was ist das Ziel einer guten Hashfunktion?

Immer denselben Bucket wählen

Schlüssel gleichmässig streuen

Sortierung erzwingen

Rekursion ersetzen

Question 2

Zwei verschiedene Schlüssel erhalten denselben Bucketindex. Was folgt daraus?

Die Schlüssel gelten automatisch als gleich.

Der zweite Schlüssel darf nicht gespeichert werden.

Innerhalb des Buckets ist ein Gleichheitsvergleich nötig.

Die Tabellenkapazität muss sofort verdoppelt werden.

Question 3

Implementiere bucketIndex so, dass auch negative Hashwerte einen gültigen Bucketindex liefern.

Hint

Math.floorMod(hash, capacity) liefert für positive Kapazitäten einen nichtnegativen Rest, auch wenn hash negativ ist.

class Buckets {
  static int bucketIndex(int hash, int capacity) {
    // TODO
    return 0;
  }
}

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