Why must you override both equals() and hashCode() together in Java?

import java.util.Objects;

public class EmployeeId {
    private final String department;
    private final int number;

    public EmployeeId(String department, int number) {
        this.department = department;
        this.number = number;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof EmployeeId other)) return false;
        return number == other.number && Objects.equals(department, other.department);
    }

    @Override
    public int hashCode() {
        return Objects.hash(department, number);
    }
}