hashCode contract in sets

Beginner Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

HashSet/HashMap: first hashCode for the bucket, then equals within the chain. Contract: equals true => same hashCode.

Changing mutable keys after insertion is an error.

Where used

The correctness of productive HashMap relies on the contract. Incorrect hashCode distribution creates hotspots and latency spikes under load.

Depth

Hash-based sets use hash values and equality together. Objects that are considered identical according to equals must land in the same search region. Conversely, different objects can have the same hash value; the data structure resolves this case through additional comparisons.

Fields that affect equals should not be modified during membership in a HashSet. Otherwise, the object is placed under an old mapping while a later search examines a different position. The entry is then present but hardly reachable through normal search.

Difficulty levels

Check consistency requirements between equals and hashCode.
Understand the impact of a mutable key field.
Design suitable immutable key types.

Pitfalls

A common misconception is that different objects must have different hash values. More harmful is the opposite: logically identical keys with conflicting mappings can appear simultaneously in the set.

University approvals: 0

Tasks

Question 1

If a.equals(b) holds true, what must hold for hashCode?

hashCodes may differ

hashCodes must be equal

hashCode can be null.

Only TreeMap checks that.

Question 2

A key stored in a HashSet changes a field that affects equals and hashCode. What is a plausible consequence?

The set automatically moves the entry to a new bucket.

may miss the existing entry at the newly calculated position.

Only the iteration order changes, the search remains secure.

The compiler prevents the field change.

Question 3

Implement Point with consistent equals and hashCode. uniqueCount should determine the number of different points using a HashSet.

Hint

Objects.hash(x, y) generates a hash value from both fields. HashSet.add and HashSet.size belong to the 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: Algorithms and Data Structures
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy