[JAVA] Set 인터페이스에 대하여 (3)

대부분의 자바 개발자라면 Set을 "중복을 허용하지 않는 컬렉션"이라고 알고 있다. 하지만 실무에서 이를 제대로 활용하려면 Set 내부가 어떻게 동작하는지, 왜 해시 알고리즘을 사용하는지, 그리고 hashCode()와 equals()를 왜 꼭 오버라이딩해야 하는지를 정확히 이해해야 한다.

 

이번 글에서는 단순히 사용하는 수준을 넘어, Set 내부 구조와 해시 기반 탐색 방식, 그리고 대표 구현체들의 차이까지 정리해본다.

 

1. Set이란?

Set은 자바 컬렉션 프레임워크에서 중복되지 않는 객체들의 집합을 의미한다.
한 번 추가한 값은 다시 추가되지 않으며, 저장 순서를 보장하지 않는 것이 일반적이다. 대표적으로 HashSet, LinkedHashSet, TreeSet이 있다.

• 중복 허용 X
• 순서 보장 X (TreeSet, LinkedHashSet은 예외)
• 검색, 추가, 삭제 중심의 컬렉션

 

2. 검색 성능을 위해 도입된 해시 알고리즘

기본적으로 Set은 검색과 중복 검사에 강한 컬렉션이다. 하지만 내부 구조가 단순 배열이나 리스트라면 검색 시 O(n)이 걸린다. 이를 해결하기 위해 도입된 것이 바로 해시 알고리즘이다.

해시 알고리즘(hash algorithm)은 객체를 정수로 변환한 후, 이 정수를 해시 함수에 넣어 특정 위치(인덱스)를 계산해낸다. 이를 통해 값이 어디에 저장될지 빠르게 결정할 수 있고, 조회도 빠르게 가능하다.

 

 

3. Set 내부의 해시 동작 방식

자바의 HashSet은 내부적으로 HashMap을 이용해 동작하며, 다음과 같은 흐름을 따른다.

1. 객체가 들어오면 먼저 hashCode() 메서드를 호출한다.
2. 이 해시 코드를 해시 함수에 넣어 해시 인덱스를 구한다.
3. 해당 인덱스 위치에 값이 없으면 바로 저장한다.
4. 해당 인덱스에 이미 값이 있다면, equals() 메서드로 동등성 비교를 수행하여 중복 여부를 판단한다.

이 구조를 통해 Set은 평균적으로 O(1)의 성능으로 데이터를 저장하고 검색할 수 있다.

 

4. 해시 충돌과 성능 저하

이상적으로는 해시코드가 잘 분산되어야 하지만, 서로 다른 객체라도 같은 해시코드를 반환할 수 있다. 이를 해시 충돌(hash collision)이라 하며, 이런 경우에는 해당 버킷에 여러 객체가 연결리스트 형태로 저장된다.

최악의 경우 해시 충돌이 반복되면 리스트의 길이가 길어져 검색 성능이 O(n)까지 떨어질 수 있다. 자바 8 이후로는 일정 수 이상의 충돌이 발생하면 해당 버킷을 Red-Black Tree 구조로 자동 전환하여 탐색 성능을 O(log n)으로 유지한다.

 

5. equals()와 hashCode()는 반드시 함께 오버라이딩해야 한다

해시 자료구조에서 발생하는 실무 문제로 이해하는 핵심 원리

자바에서 Set이나 Map과 같은 해시 기반 자료구조를 사용할 때, equals()와 hashCode()를 반드시 함께 오버라이딩해야 한다. 두 메서드 중 하나라도 제대로 구현하지 않으면, 다음과 같은 문제가 발생한다.

• 중복 데이터가 저장된다.
• 데이터 검색이 실패한다.
• 성능이 급격히 저하된다.

이 두 메서드는 해시 자료구조의 핵심 요소다. hashCode()는 값을 저장할 버킷 위치를 결정하며, equals()는 해시 충돌 발생 시 값의 동일성 판단에 사용된다. 순서대로 예제를 통해 그 차이를 살펴본다.

 

1) hashCode()와 equals()를 모두 구현하지 않은 경우

public class MemberNoHashNoEq {
    private String id;
    public MemberNoHashNoEq(String id) {
        this.id = id;
    }
}

 

이 상태에서 객체 두 개를 만들어 Set에 저장하면 다음과 같은 문제가 발생한다.

MemberNoHashNoEq m1 = new MemberNoHashNoEq("A");
MemberNoHashNoEq m2 = new MemberNoHashNoEq("A");

System.out.println(m1.hashCode());      // 1029283 (예시)
System.out.println(m2.hashCode());      // 1092345 (예시)
System.out.println(m1.equals(m2));      // false

set.add(m1);
set.add(m2);                            // 중복인데도 저장됨

set.contains(new MemberNoHashNoEq("A")); // false (검색 실패)

• hashCode()는 Object의 기본 메서드를 사용해 참조값 기준으로 생성된다.
• equals()도 참조 비교를 하므로, 논리적으로 동일한 데이터라도 다른 객체로 판단된다.
• 결과적으로 중복 데이터가 저장되고, 검색도 실패한다.

 

2)hashCode()만 구현한 경우

 

public class MemberOnlyHash {
    private String id;
    public MemberOnlyHash(String id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

이 경우 해시 인덱스는 같게 계산되지만, equals()는 여전히 Object의 기본 메서드를 따른다.

MemberOnlyHash m1 = new MemberOnlyHash("A");
MemberOnlyHash m2 = new MemberOnlyHash("A");

System.out.println(m1.hashCode() == m2.hashCode()); // true
System.out.println(m1.equals(m2));                  // false

set.add(m1);
set.add(m2);                                         // 중복 저장됨

set.contains(new MemberOnlyHash("A"));              // false

• 같은 해시코드 → 같은 버킷에 저장되지만,
• equals()가 참조 비교를 하므로 중복 체크 실패
• contains()도 equals() 실패로 검색 실패

3) hashCode()와 equals()를 모두 구현한 경우

public class Member {
    private String id;
    public Member(String id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Member)) return false;
        Member other = (Member) obj;
        return Objects.equals(this.id, other.id);
    }
}

 

 

Member m1 = new Member("A");
Member m2 = new Member("A");

System.out.println(m1.hashCode() == m2.hashCode()); // true
System.out.println(m1.equals(m2));                  // true

set.add(m1);
set.add(m2);                                         // 중복 저장 안됨

set.contains(new Member("A"));                       // true (검색 성공)

• 해시 인덱스도 같고, equals()도 true → 중복 제거 성공
• contains()로 검색 성공

 

4). 해시 충돌이 있어도 문제가 되지 않는 이유

해시 충돌은 현실적으로 완전히 피할 수 없다. 예를 들어:

System.out.println("Aa".hashCode()); // 2112
System.out.println("BB".hashCode()); // 2112

다른 문자열이지만 해시코드가 같다. 그러나 equals()로 다시 비교하기 때문에 Set은 서로 다른 값으로 정확히 구분한다.

 

결론적으로 해시 기반 자료구조를 사용할 때는 hashCode()와 equals()를 반드시 함께 구현해야 한다. 이 둘은 각각 다른 역할을 맡고 있지만, 해시 구조에서는 서로를 보완하며 작동하기 때문에 어느 하나라도 빠지면 자료구조의 기본 동작이 무너진다.

 

hashCode()는 객체가 저장될 위치(해시 버킷)를 결정하는 데 사용된다. 같은 데이터를 가진 객체라면 같은 해시코드를 반환하도록 구현해야, 중복 데이터가 다른 위치에 저장되는 일을 방지할 수 있다. 하지만 해시코드가 같다고 해서 완전히 같은 객체라고 보장할 수는 없기 때문에, 해시 충돌이 발생할 경우 equals()를 통해 실제 동등한 객체인지를 판단해야 한다. 이때 equals()가 제대로 구현되어 있지 않으면, 충돌된 객체들 간의 비교에서 오류가 발생하고, 그 결과로 중복된 객체가 저장되거나 검색에 실패하는 문제가 생긴다.

 

정리하면, hashCode()만 구현하면 해시 인덱스는 같게 계산되지만 equals()를 통해 중복 여부를 확인하지 못해 중복 저장이 발생하고, 반대로 equals()만 구현하면 올바른 해시 인덱스를 찾지 못해 검색이 불안정해진다. 둘 다 구현하지 않으면 중복 저장과 검색 실패가 동시에 일어나며, 둘 다 제대로 구현했을 때만 비로소 중복 없이 안정적으로 데이터를 저장하고 검색할 수 있다.

 

실무에서는 Objects.hash(...)를 활용하면 필드 기반의 안정적인 해시코드를 쉽게 만들 수 있고, IDE에서 제공하는 자동 생성 기능을 통해 equals()와 hashCode()를 빠짐없이 구현할 수 있다. 또한 Java 16 이상에서는 record 키워드를 사용하면 두 메서드를 자동으로 생성해주기 때문에, 불변 객체를 만들거나 DTO 구조를 설계할 때 특히 유용하다.

 

결국 해시 자료구조의 신뢰성과 성능은 hashCode()와 equals()의 정확한 구현에 달려 있다. 이 두 메서드는 단순한 오버라이딩 대상이 아니라, 해시 기반 컬렉션의 근간을 이루는 핵심 동작 방식이라는 점을 명확히 이해해야 한다.

 

 

6. 자바에서 제공하는 Set 구현체

자바는 다양한 상황에 맞게 선택할 수 있도록 여러 종류의 Set 구현체를 제공한다. 각 구현체는 내부 구조와 동작 방식이 다르며, 사용 목적에 따라 성능과 기능 면에서 차이를 보인다. 주로 사용되는 Set 구현체는 HashSet, LinkedHashSet, TreeSet의 세 가지이다.

 

HashSet

HashSet은 가장 기본적인 Set 구현체로, 내부적으로 HashMap을 사용해 데이터를 저장한다. 저장된 순서를 유지하지 않기 때문에, 데이터를 삽입한 순서와 출력 순서는 일치하지 않는다. 가장 큰 장점은 성능이다. 평균적으로 요소의 추가, 삭제, 검색이 모두 O(1)의 시간 복잡도를 가지며, 많은 양의 데이터를 빠르게 처리할 수 있다.

 

HashSet은 저장 순서가 중요하지 않고, 중복을 허용하지 않는 데이터를 빠르게 처리하고자 할 때 가장 적합하다. 예를 들어, 사용자가 중복 입력한 태그를 한 번만 저장하고 싶을 때 사용할 수 있다.

그림을 단순화 했지만, hashCode(), equals()를 모두 사용한다.

 

LinkedHashSet

LinkedHashSet은 HashSet을 확장한 구조로, 해시 기반의 저장 방식은 유지하면서도, 요소가 삽입된 순서를 기억한다. 이는 내부적으로 이중 연결 리스트(doubly-linked list)를 함께 사용하기 때문이다. 데이터를 반복하거나 출력할 때는 항상 삽입한 순서대로 나타난다.

 

성능은 HashSet보다 약간 느릴 수 있지만, 순서 유지와 빠른 검색을 동시에 만족시켜야 하는 상황에서는 매우 유용하다. 예를 들어, 사용자가 방문한 페이지 목록을 중복 없이 순서대로 저장하려는 경우에 적합하다.

 

TreeSet

TreeSet은 Set 중 유일하게 자동 정렬 기능을 제공한다. 내부적으로는 Red-Black Tree 구조의 이진 탐색 트리를 사용하며, 저장되는 모든 요소는 정렬된 상태로 유지된다. 기본적으로는 객체의 Comparable 구현에 따라 정렬되지만, 필요하다면 Comparator를 통해 사용자 정의 정렬 기준도 설정할 수 있다.

 

TreeSet은 성능 면에서 삽입, 삭제, 검색 모두 O(log n)의 시간 복잡도를 가진다. 비록 HashSet보다는 느리지만, 데이터를 정렬된 상태로 유지하면서 탐색이나 범위 검색을 자주 수행해야 하는 상황에서는 가장 효율적인 선택이다. 예를 들어, 알파벳 순으로 사용자 ID를 정렬해서 보관하거나, 특정 범위에 해당하는 데이터를 빠르게 조회해야 할 때 사용된다.

 

7. Set의 기본 메서드 정리

다음은 Set이 제공하는 주요 메서드이다:

메서드                                                                                          설명

add(E e)	요소 추가 (중복 무시)
addAll(Collection c)	여러 요소 추가
contains(Object o)	특정 요소 존재 여부 확인
containsAll(Collection c)	여러 요소 존재 여부 확인
remove(Object o)	특정 요소 제거
removeAll(Collection c)	여러 요소 제거
retainAll(Collection c)	교집합 유지
clear()	전체 요소 제거
size()	요소 개수 반환
isEmpty()	비어 있는지 확인
iterator()	반복자 반환
toArray()	배열로 변환

 

8. 어떤 Set을 선택해야 할까?

Set은 상황에 따라 어떤 구현체를 사용하는지가 매우 중요하다. 각각의 Set 구현체는 내부 구조가 다르기 때문에, 목적에 맞게 골라야 성능도 좋고 코드도 명확해진다.

 

먼저, 데이터를 자동으로 정렬된 상태로 저장하고 싶다면 TreeSet을 사용하는 것이 적절하다. TreeSet은 내부적으로 정렬 가능한 트리 구조를 사용하기 때문에, 데이터를 넣는 즉시 정렬된 상태를 유지한다. 이 구조는 삽입, 삭제, 검색이 모두 O(log n)의 시간 복잡도로 동작하며, 정렬이 필요한 경우에는 가장 효율적이다.

 

만약 데이터가 입력된 순서를 그대로 유지해야 한다면 LinkedHashSet을 사용하면 된다. 이 구현체는 데이터를 저장한 순서대로 출력되도록 연결 리스트를 함께 유지하며, 중복 제거와 순서 유지라는 두 가지 기능을 동시에 만족시킨다.

 

반면, 특별한 정렬도 순서 유지도 필요 없다면 기본적으로는 HashSet을 사용하는 것이 가장 좋다. HashSet은 Set 중에서 가장 빠른 성능을 제공하며, 대부분의 일반적인 상황에서는 이 구현체만으로 충분하다.

 

참고로, HashSet은 내부적으로 데이터를 저장할 배열을 사용하며, 이 배열이 75% 이상 차게 되면 자동으로 크기를 늘리고, 기존 데이터를 새 배열로 옮기는 과정인 '재해싱(rehashing)'을 수행한다. 이 과정을 통해 해시 충돌이 발생할 가능성을 줄이고, 성능을 일정 수준 이상으로 유지할 수 있도록 설계되어 있다.

 

또한, 자바 8 이상에서는 해시 충돌이 너무 많아지는 경우, 내부적으로 연결 리스트 대신 트리 구조(Red-Black Tree)로 자동 전환하여 탐색 속도를 유지한다. 즉, 해시 기반의 구조에서 발생할 수 있는 성능 저하까지도 자바는 자체적으로 보완하고 있다.

요약하자면,

• 정렬이 필요하다면 TreeSet
• 입력 순서를 기억해야 한다면 LinkedHashSet
• 빠르고 단순한 중복 제거가 목적이라면 HashSet

이렇게 목적에 따라 명확히 구분하여 선택하는 것이 가장 효과적이다.

 

마무리하며

이번 글에서는 자바의 Set이 단순한 중복 제거 용도가 아니라, 내부에 해시 알고리즘과 정렬 구조가 적용된 정교한 자료구조임을 살펴보았다. 특히 hashCode()와 equals()를 제대로 구현하지 않으면 발생할 수 있는 중복 저장, 검색 실패, 성능 저하 같은 문제들은 실무에서 자주 겪는 실질적인 이슈이며, 이를 정확히 이해하는 것이 자바 컬렉션을 안정적으로 다루는 첫걸음이다.

 

또한, Set의 각 구현체는 사용 목적에 따라 분명히 구분되어야 한다. 정렬이 필요하면 TreeSet, 순서 유지가 필요하면 LinkedHashSet, 빠른 성능이 최우선이라면 HashSet을 선택하는 것이 가장 바람직하다. 자바는 내부적으로 충돌을 최소화하기 위한 해시 리사이징과 Tree 구조 전환까지 자동으로 처리해주므로, 개발자는 구조와 원리를 정확히 이해하고 적절히 활용하는 데 집중하면 된다.

 

컬렉션은 자바 프로그래밍에서 가장 자주 사용되는 구성 요소 중 하나이며, 그만큼 깊이 이해할수록 코드 품질과 성능 모두에서 차이를 만든다. 다음 단계에서는 Map 구조에 대해 살펴볼 것이다.

 

감사합니다.