Java Set 자료구조

들어가기전에

• 제목을 보고 어떤 생각이 들으셨나요?
  • "Set은 뭐 그냥 단순히 중복 없이 객체들 저장하는거 아니야?"
  • "컬렉션 프레임워크 중 하나 아니야?" 등
• 저도 물론 위와 같이 단순하게만 생각하고 사용해 왔습니다.
• 그러다 우연한 기회로 코드 시간 복잡도를 줄일 방법이 뭐가있을까? 고민을 하던 중 Set set = new HashSet(); 으로 그냥 공식처럼 사용하던 것을 발견하고 HashSet ?!?! Hash써서 단순히 중복만 방지가 아니겠는데? 생각이 들어 정리한 내용을 포스팅하고자 합니다.

1. 흔히 아는 Set

• Set : 중복을 허용하지 않는 자료구조
• 사용 예시

Set<String> names = new HashSet<>();
names.add("철수");
names.add("영희");
names.add("철수"); // 중복!

System.out.println(names); // [철수, 영희]

• 철수가 중복되어 한건만 저장되는데 어떤 원리로 되는지는 여태 궁금해 했던 적이 없었다..
  • 현생이 바빴군..

2. 내부동작

• HashSet의 구현부를 보면 HashMap을 사용합니다.
• 내부 구현부

public class HashSet<E> extends AbstractSet<E>
        implements Set<E>, Cloneable, java.io.Serializable {
    
    private transient HashMap<E,Object> map;

    // map의 value로 사용하는 더미 객체
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

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

• HashSet은 사실상 값을 HashMap의 Key로 저장하는 구조, value는 아무 의미 없는 빈 껍대기 더미 객체를 넣어둠
• HashMap은 key 중복 허용하지 않아 결국 Set도 중복 불가

3. 중복 판단은 어떻게하지?

• hashCode()와 equals() 메서드를 활용
  • hashSet은 데이터를 저장할 때 hashCode()를 계산해서 해시 버킷(저장 칸)을 찾습니다.
  • 같은 hashCode가 나온 경우 같은 버킷 안에서 equals()로 한번 더 비교
  • equals() 결과가 true라면 이미 존재하는 값으로 판단하고 저장하지 않음

4. HashTable, 버킷? 그것들이 뭐지?

• 1~3번을 설명하며 HashTable을 사용한다하고, 버킷에서 값을 찾는다 이런 말이 생소하실수도 있을 것 같습니다.

4-1. HashTable

• HashTable(해시 테이블) 은 데이터를 빠르게 저장하고 검색하기 위한 자료구조입니다.
• 핵심 아이디어는 아래 한 줄로 정리할 수 있습니다 👇

  key → hashCode() → 버킷 인덱스 계산 → 해당 칸(버킷)에 저장

해시 과정

• 1. hashCode() 호출
  • 각 key 객체는 자신만의 hashCode() 메서드를 가지고 있음
    • 객체의 해시값(정수)를 반환
    • 예 : 철수.hashCode() -> 123456
• 2. 비트 섞기 (hash 보정)
  • HashMap은 Java 8 이후 단순한 hashCode를 그대로 쓰지 않고 충돌을 줄이기 위해 상위 비트와 하위 비트를 XOR 연산으로 섞음

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 3. 버킷 인덱스 계산
  • Hash Table의 크기(table.length)는 항상 2의 제곱수(16, 32, 64, ..)로 유지
    • 인덱스 계산 방법 : Hash 값 / Hash Table의 크기
  • % 대신 빠른 비트 연산(&) 사용
    • int index = (table.length - 1) & hash;
  • 예시:
    - hashCode() = 123456
    - hash = 123456 ^ (123456 >>> 16) = 123463
    - table.length = 16
    - index = 123463 & (16 - 1) = 123463 & 15 = 7

key	hashCode()	hash()	table.length	bucket index
"철수"	123456	123463	16	7
"영희"	654321	654328	16	8

• 실제 저장 구조 (HashMap 내부)
  • HashTable은 내부적으로 배열 + 연결 리스트(혹은 트리) 구조로 되어 있습니다.
  • 같은 인덱스(버킷)에 여러 값이 들어가면 LinkedList 또는 TreeNode 로 연결됩니다.
  • Java 8 이상에서는 같은 버킷에 8개 이상 충돌이 나면 Red-Black Tree 로 자동 변환됩니다.

검색 과정 (contains / add 시 중복 판단)

1. key의 hashCode() 계산

• 객체 고유의 해시값(정수)을 얻습니다.

2. 해시 함수 → 버킷 인덱스 계산

• (table.length - 1) & hash 로 실제 저장할 버킷 번호를 구합니다.
  • (즉, “배열의 몇 번째 칸에 들어갈지”)

3. 해당 인덱스의 버킷 안에서

• 버킷이 비어 있다면?
  • 해당 위치에 바로 새 엔트리를 추가하고 끝! ✅
• 버킷이 이미 차 있다면?
  • 그 안에 있는 노드들(Entry) 과 비교를 시작합니다.

4. 비교 순서

• 1. 먼저 hash 값이 같은지 확인
     → 다르면 아예 다른 버킷 값이므로 비교 중단
• 2. hash가 같다면
     → equals() 로 실제로 같은 객체인지 비교
     → equals() 결과가 true면 “이미 존재”로 판단
     → 추가 안 함
     → false면 다른 객체이므로 새 노드로 연결 (LinkedList나 Tree 구조에 붙임)

5. 시간 복잡도

연산	평균	최악	설명
add()	O(1)	O(log n) 또는 O(n)	해시 충돌 적으면 빠름
contains()	O(1)	O(log n) 또는 O(n)	버킷 인덱스 직접 접근
remove()	O(1)	O(log n) 또는 O(n)	동일 원리
size()	O(1)	O(1)	단순 필드 값 반환

어떻게 평균 O(1)일까?

• HashTable의 내부 구현을 보면 보입니다.

table = [ Entry[0], Entry[1], Entry[2], ... Entry[15] ] // 길이 16

• 위에서 언급한 버킷 인덱스가 결국엔 Java에서 배열의 인덱스로 쓰이니까 바로 O(1)로 가져올 수 있습니다.

• 최악 복잡도 설명

  • 버킷 인덱스 가 같을 경우 내부적으로 리스트 혹은 트리 구조로 저장하고 있어 최악의 경우 가장 마지막 요소를 탐색할 경우 O(n) (Java 8 이후 8개 미만에 적용) 혹은 O(log n) (Java 8이후 8개 이상에 적용)

예시

table[7] → Entry("철수") → Entry("지영") ...

• 인덱스 7로 계산 -> 바로 7번 인덱스 접근 -> 내부 연결리스트 혹은 Red-Black Tree

6. Set의 구현체들 특징

구분	내부 구조	중복 판단 방식	정렬 / 순서	성능 특징	주요 특징 / 사용 시점
HashSet	HashTable (HashMap 기반)	hashCode() → 동일 시 equals() 비교	❌ 순서 없음	평균 O(1) (삽입/검색 빠름)	가장 기본적인 Set, 중복 없이 빠른 접근이 필요할 때
TreeSet	Red-Black Tree (이진 탐색 트리)	compareTo() 결과로 중복 여부 판단	✅ 자동 정렬 (오름차순 기본)	검색 O(log n), 삽입/삭제 느림	정렬된 Set 필요할 때 (Comparable 구현 필수)
LinkedHashSet	HashTable + LinkedList	hashCode() + equals()	✅ 입력 순서 유지	O(1) (HashSet과 유사)	입력 순서를 유지하면서 중복 방지 필요할 때

HashTable

hashCode() ↓
┌───────────────────────┐
│ (table.length - 1) & hash │ → 버킷 인덱스 계산
└───────────────────────┘
             ↓
        [7번 버킷]
             ↓
 ┌──────────────────────────────────┐
 │ Entry1(hash=123, key="철수") → Entry2(hash=123, key="민수") │
 └──────────────────────────────────┘
             ↓
 equals() 비교로 중복 여부 판단

// HashMap.java 내부 클래스
static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;      // key의 해시값 (미리 계산해 저장)
   final K key;         // key 객체
   V value;             // value 객체 (HashSet에서는 더미 객체 PRESENT)
   Node<K,V> next;      // 다음 Entry (같은 버킷 내 연결 리스트)
   
   Node(int hash, K key, V value, Node<K,V> next) {
       this.hash = hash;
       this.key = key;
       this.value = value;
       this.next = next;
   }

   public final K getKey()   { return key; }
   public final V getValue() { return value; }
}

• Entry 구현체인 Node Class는 내부적으로
  • Hash 값 + Key를 가진다.
  • 따라서 중복 검사할 때
    • hash 같은지 비교 == 로 해결
    • equals() 메소드는 현제 index에 저장된 Entry 객체 내부에 있는 key객체와 새로 들어온 key 객체 비교한다.

LinkedHashSet

• LinkedHashSet은 내부적으로 LinkedHashMap 을 사용

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    public LinkedHashSet() {
        super(new LinkedHashMap<>());
    }
}

• LinkedHashMap.Entry 구조
  • 이중 연결리스트 형태로 구성 (이전, 이후 Entry)

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 이전, 다음 Entry를 가리킴 (이중 연결 리스트)
}

• 동등성(중복) 비교는 “항상 같은 버킷(같은 인덱스)” 안에서만 동작
  • hashCode → index 계산으로 도착한 그 버킷 체인(또는 트리) 내부에서만 hash→equals() 순서로 확인
  • 인덱스가 다른 엔트리끼리는 절대 비교하지 않습니다.
• LinkedHashSet/LinkedHashMap의 before/after는 “전역 순서 리스트”
  • 버킷 인덱스와 무관하게, 모든 엔트리를 하나의 이중 연결리스트로 엮어 “입력 순서(또는 접근 순서)”를 유지
  • 새 엔트리가 들어올 때마다 (중복이 아니라면) 그 엔트리를 리스트의 맨 뒤에 연결하도록
    before/after 포인터를 항상 갱신

• 예시 : A -> B -> C 넣는다고 할때
  • 각 다른 index를 가지는 HashTable에 Entry가 들어감
  • 하지만 before / after는 항상 갱신해서 입력 순서 유지됨

HashTable (버킷)
 ├─ [1] → A → (충돌 시) …
 ├─ [4] → B → …
 ├─ [7] → C → …

전역 순서 리스트 (이중 연결)
head ⇄ A ⇄ B ⇄ C ⇄ tail

TreeSet

• Hash를 사용하지 않고 compareTo() 또는 Comparator를 활용한 Red-Black Tree 기반 정렬 트리
• 각 노드가 Key의 대소 관계에 따라 자동 정렬되어 저장됨
• 데이터 추가 시 루트부터 탐색하여 compareTo() 결과로 판단
  • 음수 → 왼쪽
  • 양수 → 오른쪽
  • 0 → 중복으로 판단하여 추가하지 않음
• 검색도 동일한 원리로 동작하며, 탐색 범위를 O(log n)으로 줄임
  (즉, 이진 탐색 + 균형 트리 구조로 빠르게 검색 가능)

💡 정리하자면,
TreeSet은 compareTo()로 정렬과 중복 판단을 동시에 수행하는 정렬형 Set

• 삭제 : 삭제할 노드를 찾은 뒤 Red-Black Tree의 회전 규칙에 따라 균형을 유지합니다.
  • 균형을 맞추는 부분은 HashSet보다 조금 느리지만 정렬 상태는 항상 최신화

마무리

• Set을 단순히 중복만 제거해주는 구조라고만 생각했었지만, 정리하다 보니 예전에 배웠던 개념이 떠올랐습니다.
• 이번 정리를 통해 저를 포함한 이 글을 읽는 분들 모두, 앞으로는 Set을 단순한 “중복 제거용”이 아닌 “성능 향상을 고려한 컬렉션”으로 바라볼 수 있게 되길 바랍니다.
• 출처 : GPT 굿~!