(25.06.26) equals() 와 hashCode() 의 contract에 관하여

알고리즘 문제를 풀면서 공부를 하던 중,

Java 에서 HashSet같은 Hash 자료구조에서의 객체간 비교를 위해 equals를 override 통해 참조값을 비교하지 않도록 만들었지만,

추가로 contract를 살펴서 hashCode() 까지 오버라이드를 해야할 부분을 Java 명세를 읽어보면서 알게 되었다.

관련 개념은 쉽지만, 인는 객체의 특성보다는 Java 매뉴얼에 가깝기 때문에 기억을 해야하므로 기록을 하고자한다.

---

 

class Solution {

    public int solution(int[] arrows) {

        // 방향 하드코딩
        int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
        int[] dy = {1, 1, 0, -1, -1, -1, 0, 1};

        // 방수
        int rooms = 0;

        // 저장 자료구조
        Set<Node> visitedNodes = new HashSet<>();
        Set<Edge> visitedEdges = new HashSet<>();

        // 시작
        int currX = 0;
        int currY = 0;

        // 초기 세팅
        visitedNodes.add(new Node(currX, currY));

        for (int arrow : arrows) {

            // 스케일업 해서 두번씩 지날 수 있도록 함
            for (int i = 0; i < 2; i++) {

                int nextX = currX + dx[arrow];
                int nextY = currY + dy[arrow];

                Node currNode = new Node(currX, currY);
                Node nextNode = new Node(nextX, nextY);

                Edge edge = new Edge(currNode, nextNode);

                // [방 생성 여부 검증]
                // 1. nextNode 이미 방문한 노드 = visited 일 경우 &&
                // 2. edge가 새로 생길 경우 = visited 아닐 경우 -> 방 생성
                if (visitedNodes.contains(nextNode)
                        && !visitedEdges.contains(edge)) {
                    rooms++;
                }

                // 기록하기
                visitedNodes.add(nextNode);
                visitedEdges.add(edge);

                // 현재 좌표 갱신
                currX = nextX;
                currY = nextY;
            }
        }

        return rooms;
    }
}

class Node {
    int x;
    int y;

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        return x == node.x && y == node.y;
    }
}

class Edge {
    Node node1;
    Node node2;

    public Edge(Node node1, Node node2) {
        // 무조건 X 오름차순, Y 오름차순으로 등록
        if (node1.x > node2.x || (node1.x == node2.x && node1.y > node2.y)) {
            this.node1 = node2;
            this.node2 = node1;
        } else {
            this.node1 = node1;
            this.node2 = node2;
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;

        Edge edge = (Edge) o;

        return node1.equals(edge.node1) && node2.equals(edge.node2);
    }
}

이슈

• 위의 알고리즘은 정상적으로 이미 방문한 점(node) 이면서, 이전에 그어진 선분(edge)이 아닐 경우 → 방이 생긴다는 알고리즘 맞음
• visitedNodes.contains(nextNode) && !visitedEdges.contains(edge) 조건 내 Set 자료구조에서 해당 객체의 값(Node의 x,y, Edge의 node1, node2)이 같을 경우 → TRUE가 나오도록 클래스 변경 필요
  • Java에서 객체는 기본적으로 고유 주소 참조값을 비교하기 때문
  • equals(Object o)를 오버라이드해서 값을 비교할 경우 TRUE를 반환하도록 함

→ 하지만, contains가 무조건 FALSE, 조건문도 무조건 FALSE로 작동함

→ Hash 작동과 hashCode() 메서드의 정확한 이해 필요

---

Java의 Hash 기반 컬렉션 작동방식 이해

• 위 코드에서는 HashSet 사용

1. 객체의 hashCode() 값을 먼저 비교
2. hashCode()가 같을 경우에만 equals() 호출하여 진짜 같은 객체인지 확인
3. hashCode()가 다르면 아예 다른 객체로 판단 → equals() 호출하지 않음

→ 즉, equals()가 오버라이드 되어 true를 반환해도, hashCode()가 오버라이드 되지 않으면 hashCode가 달라서 contains 등에서 false가 나옴

---

Object 클래스의 기본 hashCode() 메서드 정의

public native int hashCode();

• native 키워드는 JVM 내부(C/C++ 등 네이티브 코드)에서 실행됨을 의미
• JVM마다 다르지만 보통 객체의 메모리 주소를 기반으로 정수 해시값 생성
• 객체의 논리적 동등성을 위해 equals()를 재정의했다면 hashCode()도 값 기반으로 일관되게 재정의해야 함 (Contract)

---

hashCode()와 equals()의 계약 (Contract)

1. equals() 계약

• Reflexive (반사성): x.equals(x)는 항상 true
• Symmetric (대칭성): x.equals(y)가 true면 y.equals(x)도 true
• Transitive (추이성): x.equals(y) && y.equals(z)면 x.equals(z)도 true
• Consistent (일관성): 여러 번 비교해도 결과가 변하지 않아야 함
• Non-null: x.equals(null)은 항상 false

1. hashCode() 계약

• equals()가 true인 두 객체 a, b에 대해 a.hashCode() == b.hashCode()여야 함 (반드시!)
• hashCode()가 같다고 equals()가 true일 필요는 없음
• 객체 상태가 변하지 않는 한 hashCode()는 여러 번 호출해도 같은 값을 반환해야 함

"If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result." — 자바 공식 명세

→ 즉, equals()를 오버라이드 했다면 hashCode()도 반드시 오버라이드 해야 함 (반대는 가능)

---

코드 개선

class Solution {

    ...

class Node {
    int x;
    int y;

    ...

    @Override
    public boolean equals(Object o) {
		...
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

class Edge {
    Node node1;
    Node node2;

 ...

    @Override
    public boolean equals(Object o) {
	...
    }

    @Override
    public int hashCode() {
        return Objects.hash(node1, node2);
    }
}

• 따라서 hashCode()를 오버라이드 하여 Objects.hash() 메서드로 같은 값(value)라면 객체가 아닌 객체가 가진 값들을 기준으로 해시 코드를 반환하도록 해야 함
  • new Edge() 객체의 해시값 비교가 아니라 node1, node2의 해시값을 비교하므로 Hash 자료구조에서 같다고 판단됨

→ 정상적으로 contains() 메서드가 작동함

---

참고자료

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#equals(java.lang.Object)

Object (Java SE 17 & JDK 17)

 

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/Object.html#hashCode()

Object (Java SE 17 & JDK 17)

 

---

해쉬값, 참조값을 잘 구분해서 단순하게 알고리즘이나 로직을 구현하기 보다,

이를 좀더 신경써서 contract에 위배되지 않도록 유의하면서 코드를 작성해야한다.