JAVA/제네릭(Generic), 컬렉션(Collection Framework)

[컬렉션 프레임워크] Set

jiyoon0000 2025. 4. 10. 16:21
자바 컬렉션 프레임워크

자바의 컬렉션 프레임워크(Collection Framework)는 데이터를 효율적으로 저장,조회,관리하기 위한 자료구조 라이브러리 집합

분류(핵심 인터페이스) 중복 허용 순서 보장 주요 구현체
List O O(인덱스 기반) ArrayList, LinkedList
Set X -(구현체에 따라 다름) HashSet, TreeSet
Queue O O(입출력 순서) LinkedList, ArrayDeque
Map X(Key 기준) -(Key 순서 없음, 일부 정렬) HashMap, TreeMap

 

Set

 

* Set이란?

  • 자바 컬렉션 프레임워크에서 중복을 허용하지 않고, 순서를 보장하지 않는 집합형 자료구조(컬렉션)
  • 요소 간 순서보다 유일성(unique)이 중요

* Set의 주요 특징

특징 설명
중복 불가 동일한 객체는 한 번만 저장된 (equals() + hashCode() 기준)
순서 보장X 기본적으로 저장 순서를 유지하지 않음 (HashSet)
정렬된 Set 존재 TreeSet -> 정렬된 상태 유지(compareTo 기준)
검색 성능 우수 HashSet은 내부적으로 해시 테이블 사용 -> 빠른 탐색 O(1)
null 값 허용 HashSet은 null 한 개 저장 가능
인덱스 접근 불가 List처럼 get(index) 메서드 제공하지 않음

 

* Set이 유용한 경우

  • 데이터의 유일성 보장이 필요한 경우
  • 중복 제거가 필요한 상황 -> 리스트에서 중복을 제거하고 싶을 때
  • 빠른 탐색이 필요한 경우 -> 특정 값의 존재 여부 판단(contains)

* Set 인터페이스 주요 메서드

메서드 설명
add(E e) 지정된 요소를 세트에 추가한다(이미 존재하는 경우 추가하지 않음
addAll(Collection<? extends E> c) 지정된 컬렉션의 모든 요소를 세트에 추가한다
contains(Object o) 세트가 지정된 요소를 포함하고 있는지 여부를 반환한다
containsAll(Collection<?> c) 세트가 지정된 컬렉션의 모든 요소를 포함하고 있는지
여부를 반환한다
remove(Object o) 지정된 요소를 세트에서 제거한다
removeAll(Collection<?> c) 지정된 컬렉션에 포함된 요소를 세트에서 모두 제거한다
retainAll(Collection<?> c) 지정된 컬렉션에 포함된 요소만을 유지하고 나머지 요소는 세트에서 제거한다
clear() 세트에서 모든 요소를 제거한다
size() 세트에 있는 요소의 수를 반환한다
isEmpty() 세트가 비어 있는지 여부를 반환한다
iterator() 세트의 요소에 대한 반복자를 반환한다
toArray() 세트의 모든 요소를 배열로 반환한다
toArray(T[] a) 세트의 모든 요소를 지정된 배열로 반환한다
Set의 주요 구현체
- HashSet
- LinkedHashSet
- TreeSet

1. HashSet

* 기본 개념

  • 자바의 Set 구현체 중 가장 기본이자 가장 많이 사용됨
  • 내부적으로 해시 테이블(HashMap) 기반으로 동작
  • 중복을 허용하지 않고, 저장 순서를 보장하지 않음

* 저장 원리

  1. 저장할 객체의 hashCode() 값으로 버킷 인덱스 계산
  2. 해당 버킷에서 equals()로 중복 여부 확인
  3. 중복이 아니면 저장

* 주요 특징

  • 내부 구조 : HashMap을 기반으로 구현(HashSet<E> -> HashMap<E, Object> 사용)
  • 순서 보장 : X
  • 중복 : X(동일 객체 저장안됨)
  • 탐색 속도 : O(1), 해시 충돌 시 O(n)
  • null 허용 : 1개 허용 가능

* 주의점

  • equals()와 hashCode()를 올바르게 오버라이딩하지 않으면 중복 제거가 안됨
  • 해시 충돌이 많아지면 성능 저하 가능

* 사용 용도

  • 빠른 중복 제거가 필요할 때
  • 요소의 순서가 중요하지 않은 경우

2. LinkedHashSet

* 기본 개념

  • HashSet의 기능 + 입력 순서를 유지
  • 내부적으로는 HashMap + 이중 연결 리스트(Doubly Linked List) 구조

* 저장 원리

  • HashSet과 동일하게 해시를 기반으로 저장하며, 요소가 추가된 순서를 리스트로 기억해 출력 시 유지

* 주요 특징

  • 내부 구조 : 해시 테이블 + 이중 연결 리스트
  • 순서 보장 : O
  • 중복 : X
  • 탐색 속도 : 평균 O(1)
  • null 허용 : 1개 가능

* 주의점

  • 순서를 저장하기 위한 연결 리스트 구조로 인해 HashSet보다 약간의 메모리 오버헤드 발생

* 사용 용도

  • 중복 제거 + 순서 유지가 동시에 필요한 경우
  • 입력 순서대로 중복 제거된 데이터 보여줄 때

3. TreeSet

* 기본 개념

  • 요소를 자동으로 정렬하면서 저장하는 Set
  • 내부적으로 레드-블랙 트리(Red-Black Tree)라는 정렬된 이진 탐색 트리 사용

* 저장 원리

  • 삽입 시 compareTo() 또는 Comparator를 통해 정렬 기준에 따라 위치 결정
  • 정렬 기준에서 같다고 판단되면 중복으로 간주

* 주요 특징

  • 내부 구조 : 정렬된 이진 탐색 트리(레드-블랙 트리)
  • 정렬 : 오름차순 기본, 커스텀 가능
  • 순서 보장 : 정렬 순서 보장(입력 순서X)
  • 탐색 성능 : O(log n)
  • null 허용 : X(NPE 발생)

* 주의점

  • null 저장 불가(비교 불가 -> NPE 발생)
  • compareTo()와 equals() 기준이 다르면 중복 판단 오류 가능

* 사용 용도

  • 중복 제거 + 정렬이 동시에 필요한 경우
  • 순위, 범위조회, 자동 정렬된 출력 등

 

+ 트리 구조

* Tree 자료구조

  • Tree는 계층적인 데이터를 표현하는 자료구조
  • 루트(root) 노드에서 시작하여 자식 노드(child)를 가지며 확장됨
  • 사이클이 없는 방향성 있는 그래프의 일종

* 이진 트리(Binary Tree)

  • 각 노드가 최대 2개의 자식 노드를 가지는 트리
  • 왼쪽 자식 -> 부모 -> 오른쪽 자식 구조를 가지면 이진 탐색 트리(Binary Search Tree)

* 이진 탐색 트리의 특징

  • 정렬된 데이터 저장
  • 검색, 삽입, 삭제 -> 평균 O(log n)
    • 단 트리가 한쪽으로 치우치면 최악 O(n)

* TreeSet과의 관계

  • TreeSet은 내부적으로 레드-블랙 트리라는 이진 탐색 트리의 일종을 사용
  • 데이터를 자동으로 정렬된 상태로 저장하고 중복을 제거
  • 삽입/삭제/탐색 모두 O(log n) 보장

* 레드-블랙 트리(Red-Black Tree)

  • 정의
    • 이진 탐색 트리의 일종으로 스스로 균형을 유지하는 트리 구조
    • 자바의 TreeSet, TreeMap은 이 구조를 기반으로 구현됨
    • 삽입/삭제 후에도 균형을 유지해 성능 저하를 방지
  • 특징
    1. 각 노드는 빨간색 또는 검은색이다
    2. 루트 노드는 항상 검은색
    3. 연속된 빨간 노드는 존재하지 않는다(빨간색 노드의 자식은 항상 검은색)
    4. 모든 리프 노드(null)에서 루트까지의 검은 노드 수는 동일
    5. 삽입/삭제 규칙을 어기면 회전(rotate) 및 색 변경(recoloring)으로 균형 복구
  • 성능
    • 삽입/삭제 : O(log n)
    • 탐색 : O(log n)
    • 최악의 경우에도 성능이 보장됨

 

 

결론

Tree는 데이터를 계층적으로 정렬해서 효율적으로 검색, 삽입, 삭제할 수 있게 해주는 자료구조이며, TreeSet은 이를 활용해 중복 없이 자동 정렬된 Set을 구현한 것

자바가 제공하는 Set 최적화

1. 초기 용량 설정 가능

  • 내부 배열의 초기 크기를 지정 가능
  • 데이터를 미리 예측할 수 있다면 리사이징(재해싱) 오버헤드를 줄일 수 있음
Set<String> set = new HashSet<>(100);

2. 자동 리사이징(재해싱, Rehashing)

  • HashSet은 내부적으로 배열과 해시 버킷(체이닝 구조)을 사용
  • 기본 초기 용량은 16, 기본 로드 팩터는 0.75
  • 요소가 전체 용량의 75%를 초과하면 자동으로 크기를 2배 증가시키고, 모든 데이터를 재배치(Rehash)
  • ex. 초기용량 16 -> 요소가 12개 넘어가면 -> 크기 32로 자동 증가 + 재해싱

3. 로딩 팩터(Load Factor) 조정 가능

  • 로트 팩터 : 버킷이 꽉 찼다고 판단하는 기준 비율
  • 기본은 0.75f -> 성능과 메모리 효율의 타협점
  • 낮게 설정하면 충돌 줄어듦 -> 성능 증가, 대신 메모리 사용 증가
총정리
  • 자바 컬렉션 프레임워크 : 데이터를 효율적으로 다루기 위한 자료구조 집합
  • Set : 중복을 허용하지 않고, 순서보다 유일성 보장이 중요
    • 인덱스 접근 대신 contains, add, remove 등 메서드로 관리
  • 주요 구현체
    • HashSet : 가장 기본, 빠른 탐색, 순서 보장X
      • hashCode, equals가 핵심 -> 중복 판단 기준
    • LinkedHashSet : 입력 순서 유지 + 중복 제거
    • TreeSet : 자동 정렬 + 중복 제거(레드-블랙 트리 기반)
      • 이진 탐색 트리 기반으로 log n 성능을 보장하며 정렬된 Set 구현에 적합

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 9. 컬렉션 프레임워크 Set