[Java] HashSet은 어떻게 중복을 허용하지 않는가?

HashSet의 활용

[백준] 방문 길이 문제를 풀면서 경로에 해당하는 자료형, Path 클래스를 구현해서 풀이했다.

import java.util.*;

class Solution {
    public int solution(String dirs) {
        HashSet<Path> visited = new HashSet<>();
        
        // ...
	}
    
    class Path {
        private final int fromX;
        private final int fromY;
        private final int toX;
        private final int toY;

        private Path(int fromX, int fromY, int toX, int toY) {
            this.fromX = fromX;
            this.fromY = fromY;
            this.toX = toX;
            this.toY = toY;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Path) {
                Path other = (Path) obj;
                return (this.fromX == other.fromX && this.fromY == other.fromY && this.toX == other.toX && this.toY == other.toY)
                        || (this.fromX == other.toX && this.fromY == other.toY && this.toX == other.fromX && this.toY == other.fromY);
            }
            return false;
        }
    }
}

같은 경로를 지나갈 때, 즉, 중복되는 경로는 저장하지 말아야 하기 떄문에 방문했던 경로들은 HashSet으로 관리했다. HashSet은 중복 저장을 허용하지 않는 자료구조이기 때문에 중복을 막아야 하는 문제에서 필수적이었고, 이를 활용하기 위해 Path 클래스에 equals() 메서드도 오버라이딩 했다.

하지만, 위 코드를 실행시키면 같은 경로를 지나가면 지나간 대로 다 저장하고 있다.

HashSet은 객체의 고유성을 확인하는데 equals()만 이용하지 않기 때문이다. hashCode()도 필요하다.

equals()로 일치한다는 결과가 나오더라도 이 사실만으로는 고유성을 판단하기에는 부족하다는 것이다. 당연한 소리죠?

이 글을 쓰기 전까지의 제게는 당연하지 않았어요 ㅎㅎ

그럼 hashCode()는 무엇인가?

hashCode()는 객체를 해시 테이블의 특정 위치에 저장할 때 해당 위치를 결정하는 데 중요한 역할을 한다.

특히, HashSet, HashMap, HashTable 같이 해시 기반 자료구조에서 객체의 고유성을 빠르게 판단하는 데 필요하다.

hashCode()의 역할

1. 해시 테이블의 효율적인 검색
   해시 기반 자료구조는 데이터를 배열 형태로 관리하는데, 각 배열 인덱스를 빠르게 찾기 위해 hashCode()를 사용한다. hashCode()는 객체의 고유한 정수값을 반환하여 객체가 저장될 배열의 위치를 결정한다.

2. 중복 체크와 성능 최적화
   HashSet처럼 중복 객체를 허용하지 않기 위해서는 equals(), hashCode()를 이용한다. 이 때, 저장될 객체에 대해 해당 hashCode를 먼저 확인 → 이미 존재한다?(=해시 충돌) → equals()로 2차 검사 → 얘 마저 똑같다? → 저장 거부 의 과정을 진행한다. 이로써, 빠른 중복 검사 및 데이터 관리가 가능하다고 한다.

3. 효율적인 데이터 비교
   hashCode는 일종의 사전 필터링 기능도 제공한다. equals()로 두 객체를 비교하기 전에 hashCode로 서로가 다른 객체임을 확실히 짚고 넘어갈 수 있기 때문에 불필요한 equals() 호출을 막을 수 있다.

hashCode()도 오버라이딩하여 코드 수정

@Override
public int hashCode() {
	return Objects.hash(Math.min(fromX, toX), Math.min(fromY, toY), Math.max(fromX, toX), Math.max(fromY, toY));
}

위 코드처럼 동일한 경로에 대해 같은 hashCode를 가질 수 있도록 계산해주는 로직을 구현하여 HashSet에 내가 원하는대로 중복 경로를 저장하지 않도록 수정했다.

결론

주의할 것은 이 글에서 Set 전체를 다룬 것이 아니라, HashSet으로 특정 지었다는 것.

TreeSet 등 다양한 Set이 있는데, 모든 Set이 hashCode()를 이용하는 것은 아니기 때문이다.

HashSet이 객체의 고유성을 판단하는 데 필요한 것은 equals(), hashCode()이다. 이 hashCode()는 각 객체의 식별값, id 같은 역할을 해준다. hashCode()로 객체의 고유성을 확인했으면, 그 다음 절차가 equals()이다.