hashCode-Vertrag in Sets

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

HashSet/HashMap: zuerst hashCode für den Bucket, dann equals innerhalb der Kette. Vertrag: equals true => gleicher hashCode.

Mutable Schlüssel nach dem Einfügen zu ändern ist ein Fehler.

Wo gebraucht

Produktive HashMap-Korrektheit hängt am Vertrag. Falsche hashCode-Streuung erzeugt Hotspots und Latenzspikes unter Last.

Vertiefung

Hashbasierte Sets benutzen Hashwert und Gleichheit gemeinsam. Objekte, die nach equals als identisch gelten, müssen in dieselbe Suchregion gelangen. Umgekehrt dürfen verschiedene Objekte denselben Hashwert besitzen; die Datenstruktur löst diesen Fall durch zusätzliche Vergleiche.

Felder, die equals beeinflussen, sollten während der Mitgliedschaft in einem HashSet nicht verändert werden. Sonst wurde das Objekt unter einer alten Zuordnung abgelegt, während eine spätere Suche eine andere Position untersucht. Der Eintrag ist dann vorhanden, aber über die normale Suche kaum noch erreichbar.

Schwierigkeitsstufen

Konsistenzanforderungen zwischen equals und hashCode prüfen.
Die Wirkung eines veränderlichen Schlüsselfeldes nachvollziehen.
Geeignete unveränderliche Schlüsseltypen entwerfen.

Fallstricke

Eine häufige Fehlannahme ist, dass verschiedene Objekte zwingend verschiedene Hashwerte brauchen. Schädlicher ist die Gegenrichtung: logisch identische Schlüssel mit widersprüchlicher Zuordnung können gleichzeitig im Set erscheinen.

University approvals: 0

Tasks

Question 1

Wenn a.equals(b) gilt, was muss für hashCode gelten?

hashCodes dürfen differieren

hashCodes müssen gleich sein

hashCode darf null sein

Nur TreeMap prüft das

Question 2

Ein im HashSet gespeicherter Schlüssel ändert ein Feld, das equals und hashCode beeinflusst. Welche Folge ist plausibel?

Das Set verschiebt den Eintrag automatisch in einen neuen Bucket.

contains kann den vorhandenen Eintrag an der neu berechneten Stelle verfehlen.

Nur die Iterationsreihenfolge ändert sich, die Suche bleibt sicher.

Der Compiler verhindert die Feldänderung.

Question 3

Implementiere Point mit konsistentem equals und hashCode. uniqueCount soll die Anzahl verschiedener Punkte mit einem HashSet bestimmen.

Hint

Objects.hash(x, y) erzeugt einen Hashwert aus beiden Feldern. HashSet.add und HashSet.size gehören zur Collection-API.

import java.util.HashSet;
import java.util.Objects;

class Point {
  final int x;
  final int y;

  Point(int x, int y) {
    this.x = x;
    this.y = y;
  }

  @Override public boolean equals(Object other) {
    // TODO
    return false;
  }

  @Override public int hashCode() {
    // TODO
    return 0;
  }
}

class PointSet {
  static int uniqueCount(Point[] points) {
    // 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