Java HashSet의 내부 동작 방식과 중복 제거 메커니즘

Java HashSet의 내부 동작 방식과 중복 제거 메커니즘을 정리한 글입니다.

 

HashSet

HashSet은 Java의 java.util 패키지에 속하는 컬렉션 클래스입니다.

요소 중복을 허용하지 않으며 순서를 보장하지 않습니다.

 

HashSet의 내부 구조

내부적으로 HashMap을 사용하여 요소를 저장합니다.

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

map은 HashMap<E, Object> 타입으로 선언되어 있으며, HashSet에 추가된 요소가 key로 저장됩니다.

PRESENT는 value 역할을 하는 더미 객체입니다.

 

HashSet의 중복 제거 메커니즘

HashSet은 hashcode()와 equals()를 활용하여 중복을 판별합니다.

hashCode()는 Hash Function의 한 종류입니다.

Hash Function은 임의의 입력값을 특정한 길이의 고유한 값(해시값)으로 변환하는 함수입니다.

 

해시 테이블

 

• hashCode()를 이용하여 해시 테이블의 버킷(bucket) 위치를 결정하고, 만약 같은 해시값을 가진 요소가 존재하지 않으면(해당 버킷이 비어있으면) 새로운 요소로 추가됩니다.
• 만약 같은 hashCode() 값을 가진 요소가 이미 존재(버킷이 차있으면)하면 equals()를 호출하여 완전히 동일한 객체인지 판별합니다.
• equals()가 true라면 중복된 요소로 간주되어 추가하지 않습니다.
• false라면 해시 충돌(Hash Collision) 해결 방법을 통해 해결합니다. 해시 충돌 해결 방법에 대한 자세한 설명은 뒤에 하겠습니다.

HashSet은 해시 테이블 기반의 데이터 저장 방식이기 때문에 Hash Function을 이용해 O(1)의 평균 시간 복잡도로 버킷을 빠르게 찾고, 필요할 경우 equals()를 호출하여 효율적인 중복 체크를 할 수 있습니다.

 

 

hashcode()와 equals() 주의점

equals()가 true를 반환하는 두 객체는 반드시 동일한 hashCode()를 가져야 합니다.

그렇지 않으면 HashSet이 중복 판단을 제대로 하지 못하고 해시 충돌이 발생하여 동일한 객체를 여러 번 저장할 수 있습니다.

 

예시

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // equals()만 오버라이드 (hashCode() 미구현)
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Person person = (Person) obj;
        return age == person.age && name.equals(person.name);
    }
}

public class EqualsWithoutHashCode {
    public static void main(String[] args) {
        Set<Person> set = new HashSet<>();

        Person p1 = new Person("Alice", 25);
        Person p2 = new Person("Alice", 25); // p1과 같은 값

        set.add(p1);
        set.add(p2); // 같은 객체인데도 HashSet에 추가됨

        System.out.println("Set 크기: " + set.size()); // 예상: 1, 실제: 2
    }
}

p1과 p2는 equals() 비교에서 동일한 객체로 판별되지만, hashCode()가 다르게 계산되므로 HashSet은 서로 다른 객체로 간주하고 중복 제거하지 못하고 동일한 객체를 저장했습니다.

 

 

따라서 다음과 같은 규칙을 지켜야합니다.

• equals()를 오버라이드하면 hashCode()도 오버라이드해야합니다.
• 같은 객체에 대해 hashCode()는 항상 동일한 값을 반환해야 합니다.
• equals()가 true를 반환하는 두 객체는 hashCode()도 같아야 합니다.

 

해시 충돌

해시 충돌(Hash Collision)은 서로 다른 객체가 같은 hashCode() 값을 가질 때 발생합니다.

해시 충돌 해결 방식으로는 대표적으로 체이닝과 오픈 어드레싱이 있습니다.

• 체이닝: 버킷 하나에 Linked List 등을 두어 충돌이 발생하면 해당 리스트에 추가 저장합니다.
• 오픈 어드레싱: 충돌이 발생하면 빈 버킷을 찾아 이동하면서 저장합니다.
  • 선형 탐사: 한 칸씩 이동하여 비어 있는 슬롯을 찾는 방식 (ex. 5번 [충돌] -> 6번 [충돌] -> 7번...)
    • 구현이 단순하나 클러스터링 문제가 발생할 수 있습니다.
    • 클러스터링 문제: 연속된 빈 슬롯이 채워지면서 충돌이 많이 발생하는 문제
  • 이차 탐사: 제곱 수만큼 이동하여 빈 슬롯을 찾는 방식 (ex. 5번 [충돌] -> 6번(5+1^2) [충돌] -> 9번(5+2^2)...)
    • 클러스터링 문제가 감소하나 테이블 크기가 소수가 아닐 경우, 무한 루프(주기적인 충돌) 문제가 발생할 수 있습니다.
    • 예를 들어 해시 테이블 크기가 16(소수가 아님)이고 5번에 접근한다면 아래와 같이 다시 5번에 접근합니다.
      • 5 -> 6(5+1^2) -> 9(5+2^2) -> 14(5+3^2) -> 5((5+4^2) % 16(해시 테이블 크기))
  • 이중 해시: 다른 해시 함수를 사용하여 새로운 해시값을 계산하는 방식
    • 선형 탐사와 이차 탐사의 클러스터링 문제를 해결할 수 있고 해시 충돌이 최소화되지만 추가 연산이 필요합니다.

자바 7까지는 체이닝 방식으로 같은 해시값을 가지는 요소들을 Linked List로 저장했습니다. 이는 해시 충돌이 많아지면 한 버킷에 여러 요소가 연결 리스트로 저장되어 최악의 경우 contains(), add() 등의 연산이 O(n)까지 증가하여 성능이 저하되는 단점이 있었습니다.

 

자바 8 이후로는 해시 충돌이 많아지면 연결 리스트 대신 Red-Black Tree(레드-블랙 트리)로 변환하여 성능을 개선했습니다.

같은 해시 버킷에 있는 요소 개수가 8개 이상이면 트리로 변환하고, 요소 개수가 6개 이하로 줄어들면 다시 연결 리스트로 변환합니다.

이러한 방식을 통해 해시 충돌이 많아도 성능이 O(n)에서 O(log n)으로 개선됩니다.