Java에서 객체의 equals를 오버라이딩할 때 hashCode를 같이 오버라이딩하는 이유 (프로그래머스 삼총사 풀이)

 

프로그래머스 코딩테스트 연습문제 '삼총사'를 풀이하면서 Java 객체의 equals와 hashCode 메서드를 오버라이딩해야 하는 이슈가 있었고, 그 과정을 통해 알게 된 equals를 오버라이딩할 때 일반적으로 hashCode를 같이 오버라이딩하는 이유를 정리했다.

 

다음의 링크들에서 문제와 문제풀이를 위해 고려한 접근법을 확인할 수 있다.

 

프로그래머스

GitHub - hsjkdss228/daily-coding-dojo: 주간 코딩 도장 문제 풀이 저장소

 

 

문제 해결을 위해 가능한 쌍의 모든 경우의 수를 고려하는 방법을 생각했다. 이를 위해 주어진 배열에서 학생 3명의 index 정수를 요소로 갖는 값 객체를 선언하는 방식을 택해 보았다. 다음과 같이 값 객체를 정의했다.

public class Indices {
    private final int index1;
    private final int index2;
    private final int index3;

    public Indices(int index1, int index2, int index3) {
        this.index1 = index1;
        this.index2 = index2;
        this.index3 = index3;
    }

    public static Indices of(int index1, int index2, int index3) {
        return new Indices(index1, index2, index3);
    }
}

 

값 객체라면 객체가 저장되는 주소의 고유한 위치 값이 아닌, 두 객체가 갖는 값이 동일하다는 등의 특정 조건을 만족하는 경우에도 두 객체가 같은 객체임을 나타낼 수 있도록 equals를 정의해야 했다. 위의 객체에서 두 객체가 같은 경우는 어떤 경우일까.

 

 

삼총사의 구성원이 로사, 로이, 나옹이라고 한다면

 

(로사, 나옹, 로이) 순서대로 서 있어도

(로사, 로이, 나옹) 순서대로 서 있어도

 

이들은 모두 같은 로켓단이다. 즉 index들이 가진 세 값의 묶음이 순서는 달라도, 3개의 index 값 자체는 같은 경우가 있을 수 있다. 해당 경우를 위해 각 index들을 모두 비교하는 방식으로 equals를 재정의했다. hashCode는 IntelliJ에서 제공하는 방식을 사용했다.

@Override
public boolean equals(Object object) {
    if (this == object) {
        return true;
    }
    if (object == null || getClass() != object.getClass()) {
        return false;
    }
    Indices other = (Indices) object;
    return (this.index1 == other.index1
        && this.index2 == other.index2
        && this.index3 == other.index3)
        || (this.index1 == other.index1
        && this.index2 == other.index3
        && this.index3 == other.index2)
        || (this.index1 == other.index2
        && this.index2 == other.index1
        && this.index3 == other.index3)
        || (this.index1 == other.index2
        && this.index2 == other.index3
        && this.index3 == other.index1)
        || (this.index1 == other.index3
        && this.index2 == other.index1
        && this.index3 == other.index2)
        || (this.index1 == other.index3
        && this.index2 == other.index2
        && this.index3 == other.index1);
}

@Override
public int hashCode() {
	return Objects.hash(index1, index2, index3);
}

 

다소 무식하지만, 확실하기는 하다.

 

이제 모든 쌍의 경우의 수를 만들어 중복을 허용하지 않는 Set에 삽입하면, 값 객체가 중복인 경우에는 Set에 추가되지 않기 때문에 서로 다른 객체들만이 Set에 삽입되어 있을 것을 기대했다.

public Set<Indices> createIndicesSet(int length) {
    Set<Indices> indicesSet = new HashSet<>();
    for (int index1 = 0; index1 < length; index1 += 1) {
        for (int index2 = 0; index2 < length; index2 += 1) {
            if (index2 == index1) {
                continue;
            }
            for (int index3 = 0; index3 < length; index3 += 1) {
                if (index3 == index1 || index3 == index2) {
                    continue;
                }
                Indices indices = new Indices(index1, index2, index3);
                indicesSet.add(indices);
            }
        }
    }
    return indicesSet;
}

@Test
void createIndicesSet() {
    int length = 4;
    assertThat(test.createIndicesSet(length))
        .isEqualTo(Set.of(
            Trio.Indices.of(0, 1, 2),
            Trio.Indices.of(0, 1, 3),
            Trio.Indices.of(0, 2, 3),
            Trio.Indices.of(1, 2, 3)
        ));
}

 

결과는 그렇지 않았다.

expected:
    [{0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3}]
but was:
    [{0, 1, 2}, {0, 2, 3}, {2, 1, 0}, {3, 2, 0}, 
    {0, 1, 3}, {1, 2, 3}, {3, 1, 0}, {3, 2, 1}, 
    {1, 0, 2}, {2, 0, 1}, {1, 0, 3}, {2, 1, 3}, 
    {3, 0, 1}, {3, 1, 2}, {2, 0, 3}, {3, 0, 2}, 
    {0, 3, 1}, {1, 3, 0}, {0, 2, 1}, {0, 3, 2}, 
    {1, 2, 0}, {2, 3, 0}, {1, 3, 2}, {2, 3, 1}]

 

왜 이런 일이 발생했을까. 구글링도 해보고 ChatGPT 형님께도 물어본 과정 끝에 알아낸 이유는 HashSet에 값이 저장되는 방식에 있었다.

 

간단히 설명하자면 HashMap, HashSet에 데이터가 삽입될 때, 데이터가 저장되는 index는 다음의 연산을 통해 결정된다.

index = 객체의 hashCode 값 % 해당 컬렉션 내에서 가용되는 버킷의 수

 

Java에서는 버킷의 수는 16부터 시작하고, 저장되는 데이터의 수가 정해진 기준 이상이 될 때마다 버킷을 2배로 늘리고 기존에 저장된 데이터들을 바뀐 버킷에 맞게끔 다시 index를 구해 저장하는 연산을 수행한다.

 

즉 각 객체는 HashMap이나 HashSet에 각 객체의 hashCode 값에 의거한 고유한 index를 갖게 되고, 해당 index의 위치에 저장된다. 이로 인해 탐색을 수행하는 경우에는 해당 고유한 index를 알아내는 것으로 데이터가 HashSet 내에 저장된 위치를 바로 알 수 있으며, 그렇기 때문에 HashSet과 HashMap의 탐색 연산 속도가 O(1)이라는 사실도 유추할 수 있다.

 

그렇다면 이미 저장된 객체와 새로 저장하려는 객체의 hashCode 값에서 차이가 발생한다면 HashSet 내에서 저장되는 index의 위치가 달라지기 때문에 두 객체에 대한 equals 연산을 수행하기 위해 대조할 수조차 없겠구나 싶은 생각이 들었다. IntelliJ에서 자동으로 생성해 준 hash 값 생성 메서드의 결과값을 한번 살펴보았다.

@Test
void hash() {
    assertThat(Objects.hash(1, 2, 3)).isEqualTo(Objects.hash(2, 3, 1));
}

expected: 31807
but was: 30817

 

역시 결과는 다른 hashCode 값을 반환했다. 그러면 두 객체가 같은 hashCode 값을 갖게 하려면 어떻게 해야 할까.

떠오른 방법은, 세 개의 index 값의 hashCode를 각각 구한 뒤, 값들을 모두 더하는 방식이었다. 그렇게 하면 위처럼 index의 순번이 다르더라도 구성되어 있는 index들이 모두 같다면 같은 hashCode를 반환하게 할 수 있을 것이었다. 이를 위해 hashCode 메서드도 다시 다르게 오버라이딩했다.

@Override
public int hashCode() {
    return Objects.hash(index1) + Objects.hash(index2) + Objects.hash(index3);
}

@Test
void hash() {
    assertThat(Objects.hash(1) + Objects.hash(2) + Objects.hash(3))
        .isEqualTo(Objects.hash(2) + Objects.hash(3) + Objects.hash(1));
}

 

다만 이렇게 하면 (2, 3, 5)와 (7, 1, 2)처럼 실제로 서로 다른 객체들이라 하더라도 hashCode 값이 같게 도출되는 경우가 생길 수 있고, 그에 따라 해당 index에서 같은 hashCode 값을 갖는 데이터들을 다시 한 번 컬렉션의 형태로 저장하는 연산을 수행하고, 탐색 시에도 해당 index에 존재하는 컬렉션을 다시 탐색해야 하는 문제는 있을 수 있을 것이다.

 

hashCode를 수정함으로써 해당 방식으로 직접 정의한 createIndicesSet 메서드의 동작이 의도한 방식으로 동작하게끔 수정할 수 있었다. hashCode를 수정하지 않았었을 때 일단 문제를 해결하기 위해 index 묶음 객체를 생성할 때마다 객체를 저장하는 HashSet에 해당 객체가 존재하는지 검증하는 동작을 HashSet의 모든 요소와 대조하는 방식으로 일단 문제를 풀이하기는 했었지만, 해당 방식은 비교에 O(n)의 시간 복잡도가 소요되는 방식이었다. 기존 방식과 hashCode를 오버라이딩해 데이터를 삽입하는 순간에 비교를 수행하는 O(1)의 시간 복잡도가 소요되는 방식의 수행 시간 차이 또한 확인해볼 수 있었다.

 

왼쪽 사진이 비교 연산에 O(n)의 시간 복잡도가 소요되고, 오른쪽 사진이 O(1)의 시간 복잡도가 소요되는 로직이다.

 

값 객체를 정의할 때 equals를 오버라이딩하면서 hashCode를 오버라이딩하는 이유도 구체적으로 알 수 있었던, 그래서 문제 해결에 3시간이나 투자해야 했지만 3시간이 아깝지 않았던 트러블슈팅이었다.

 

References

- Java HashSet의 원리

- HashMap/HashSet의 원리

- ChatGPT