Java HashSet Equality Semantics

HashSet uses hashCode() to narrow down where an element may belong and equals() to decide whether an equivalent element is already present. For correct set behavior, equal objects must always produce the same hash code.

A HashSet stores elements without duplicates according to equality, but it does not normally compare every stored element with a new one. When an element is added, the set first uses its hash code to identify candidate entries and then uses equals() to check for an actual match.

The key contract is that if `a.equals(b)` is true, then `a.hashCode()` must equal `b.hashCode()`. The reverse is not required: two different objects can have the same hash code, which is called a collision, and HashSet resolves such cases with equals().

This means overriding equals() without overriding hashCode() can break HashSet behavior. Two logically equal objects may be placed in different hash locations, allowing both to appear in a set even though they should represent the same value.

Mutable fields used by equals() and hashCode() are another hazard. If an object changes after insertion so that its hash code changes, the set may no longer be able to locate it using its new state. In practice, fields participating in equality should generally be stable while the object is stored in a HashSet.

Key points

• HashSet uses `hashCode()` to find candidate entries and `equals()` to confirm equality.
• The Java equality contract requires equal objects to have equal hash codes.
• Hash collisions are allowed; `equals()` distinguishes unequal objects with the same hash.
• Overriding `equals()` without a consistent `hashCode()` implementation can produce incorrect HashSet behavior.
• Changing equality-relevant state after insertion can make an element difficult to find or remove.

Interview questions

How does HashSet determine whether an element is already present?

HashSet first uses the element's `hashCode()` to locate the relevant candidate area. It then uses `equals()` to determine whether an existing candidate represents the same logical value. A hash collision does not mean the elements are equal. Only an equality match prevents the new element from being added.

What contract must equals() and hashCode() satisfy?

If two objects are equal according to `equals()`, their `hashCode()` values must be equal. This allows hash-based collections to find equal objects in the same candidate area. Different objects are allowed to have the same hash code. Therefore, equal hash codes do not prove equality.

Why can overriding equals() without hashCode() cause problems in a HashSet?

HashSet uses the hash code before it performs equality checks. If two logically equal objects return different hash codes, they can be placed in different candidate areas. The set may then fail to compare them with each other and can contain both objects. This violates the behavior expected from a set of logically unique values.

What happens if an object stored in a HashSet changes a field used by equals() and hashCode()?

Changing that field can change the object's hash code after insertion. A later lookup may search a different candidate area from the one where the object was originally stored. As a result, `contains()` or `remove()` may fail even though the object is still physically present in the set. Equality-relevant state should therefore remain stable while the object is used as a HashSet element.