HashSet — 해시 기반 중복 없는 컬렉션

지난 글에서 레거시 Vector와 Stack을 살펴봤다. 이번에는 HashSet을 다룬다. HashSet은 Java에서 가장 많이 쓰이는 Set 구현체로, 중복 없는 원소 저장과 O(1) 평균 검색 성능을 제공한다.

HashSet은 HashMap 위에 올라탄 Set

HashSet의 핵심을 한 줄로 표현하면: HashMap<E, Object>의 키 집합을 Set처럼 노출하는 래퍼다.

// java.util.HashSet 내부 (간략화)
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object(); // 더미 값

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

public boolean contains(Object o) {
    return map.containsKey(o);
}

public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

원소는 HashMap의 키로, 더미 싱글턴 PRESENT는 항상 동일한 값으로 저장된다. 덕분에 키의 중복 감지 로직(hashCode + equals)이 그대로 Set의 중복 제거 로직으로 활용된다.

해시 버킷과 충돌 처리

원소를 추가할 때 내부에서 일어나는 과정:

1. element.hashCode() 계산
2. 보조 해시 함수 적용: (h = key.hashCode()) ^ (h >>> 16) (높은 비트와 낮은 비트 믹싱)
3. 버킷 인덱스 계산: hash & (capacity - 1)
4. 해당 버킷에 원소 삽입 (충돌 시 연결 리스트로 체이닝)

Java 8 이후 버킷 하나에 원소가 8개 이상 쌓이면 연결 리스트를 Red-Black Tree로 전환한다. 이로써 최악의 경우 O(n) 검색이 O(log n)으로 개선된다.

import java.util.HashSet;
import java.util.Set;

Set<String> fruits = new HashSet<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("apple");  // 중복 — 무시됨

System.out.println(fruits.size());      // 2
System.out.println(fruits.contains("banana")); // true
System.out.println(fruits);             // 순서 보장 없음

equals/hashCode 계약

HashSet이 올바르게 작동하려면 원소 클래스가 equals와 hashCode를 일관되게 구현해야 한다.

계약 핵심: equals() 가 true를 반환하면 반드시 같은 hashCode()를 반환해야 한다. 반대는 성립하지 않아도 된다(충돌). equals만 재정의하고 hashCode를 재정의하지 않으면 같은 값을 가진 두 객체가 다른 버킷에 저장되어 중복 원소가 생긴다.

import java.util.Objects;

public class Point {
    private final int x, y;

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);  // 두 필드 모두 반영
    }
}

Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
points.add(new Point(1, 2)); // 중복 제거
System.out.println(points.size()); // 1

Objects.hash(...) 또는 IDE 생성 코드를 쓰면 안전하다. Java 14+ record는 equals/hashCode를 자동으로 올바르게 생성해준다.

load factor와 initialCapacity 튜닝

// 기본: capacity=16, loadFactor=0.75
Set<String> s1 = new HashSet<>();

// 예상 원소 수를 알 때: initialCapacity 지정 (rehash 방지)
// 원소 수 N을 저장하려면 capacity >= N / loadFactor
Set<String> s2 = new HashSet<>(200); // 최소 150개 원소 수용

// loadFactor 조정: 낮을수록 메모리 낭비, 높을수록 충돌 증가
Set<String> s3 = new HashSet<>(16, 0.5f); // 공간-성능 트레이드오프

• loadFactor 기본값 0.75는 공간 효율과 충돌률의 균형점이다.
• 원소 수를 미리 알고 있다면 initialCapacity = (int)(expectedSize / loadFactor) + 1로 설정해 rehash 비용을 줄인다.

집합 연산

Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

// 합집합
Set<Integer> union = new HashSet<>(a);
union.addAll(b);              // {1, 2, 3, 4, 5, 6}

// 교집합
Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);    // {3, 4}

// 차집합
Set<Integer> diff = new HashSet<>(a);
diff.removeAll(b);            // {1, 2}

성능 특성

연산	평균	최악 (Java 8 이후)
add(e)	O(1)	O(log n)
remove(o)	O(1)	O(log n)
contains(o)	O(1)	O(log n)
순회	O(capacity + size)	O(capacity + size)

순회 비용에 capacity가 포함되는 점 주의 — 버킷이 크고 원소가 적으면 빈 버킷을 다 건너뛰어야 한다.

---

지난 글: Vector와 Stack — 레거시 스레드 안전 컬렉션

다음 글: LinkedHashSet — 삽입 순서를 유지하는 Set

읽어주셔서 감사합니다. 😊