04-01. Set

Q. Set이란 무엇이며, 자바가 제공하는 Set 자료 구조는 어떠한 것이 있나요?

Set은 중복을 허용하지 않고 순서가 없는 데이터의 집합을 의미하는 자료 구조입니다.

자바는 java.util.Set 인터페이스를 통해 Set 자료 구조를 제공합니다.

이는 java.util.Collection 인터페이스를 상속하며, Set에 특화된 몇 가지 메소드를 추가로 정의합니다.

자바에서 제공하는 주요 Set 구현체는

HashMap을 사용하여 데이터를 저장하는 HashSet,

연결 리스트까지 함께 사용하는 LinkedHashSet,

트리를 기반으로 하는 TreeSet 이 있습니다.

Q. 구현체의 내부 동작 방식과 주요 성능 특성에 대해 조금 더 자세히 설명해 주시겠어요?

먼저 HashSet은 내부적으로 HashMap을 사용하여 데이터를 저장합니다.

Set에 요소를 추가하면, 해당 요소는 HashMap의 '키(Key)'로 저장되고, '값(Value)'으로는 Object 클래스의 PRESENT라는 더미 객체(dummy object)를 사용합니다. 이 HashMap은 해시 함수를 통해 계산된 해시 코드(hash code)를 기반으로 배열의 인덱스를 찾아 요소를 저장하는 해시 테이블(Hash Table) 구조로 되어 있습니다.

이 해시 테이블 구조 덕분에 삽입, 삭제, 검색(Contains) 연산에서 평균적으로 O(1)의 시간 복잡도를 가집니다. 이는 요소의 위치를 해시 코드를 통해 즉시 찾을 수 있기 때문입니다.

다만, 해시 충돌(Hash Collision)이 잦아지거나 hashCode() 및 equals() 메소드가 제대로 구현되지 않았을 경우 최악의 경우 O(n)까지 성능이 저하될 수 있습니다. 요소의 저장 순서는 보장되지 않습니다.

다음으로 LinkedHashSet은 HashSet의 특징에 순서 유지 기능을 추가한 자료구조입니다.

내부적으로 LinkedHashMap을 사용하여 데이터를 저장합니다. LinkedHashMap은 해시 테이블과 더불어 이중 연결 리스트(doubly linked list)를 사용하여 키-값 쌍(여기서는 Set의 요소)의 삽입 순서 또는 접근 순서를 유지합니다.

즉, 각 요소는 해시 테이블 내의 위치뿐만 아니라 연결 리스트를 통해 이전/다음 요소와의 연결 정보도 가지고 있습니다.

HashSet과 마찬가지로 평균적으로 O(1)의 시간 복잡도를 가집니다. 하지만 요소를 저장하거나 삭제할 때 연결 리스트의 유지 보수 작업이 추가되므로, 순서를 유지할 필요가 없는 HashSet보다는 미세하게 느릴 수 있습니다. 가장 큰 특징은 요소가 삽입된 순서(insertion order)를 보장한다는 점입니다.

마지막으로 TreeSet은 내부적으로 이진 탐색 트리의 일종인 레드-블랙 트리(Red-Black Tree)를 사용하여 요소를 저장합니다. 레드-블랙 트리는 균형 잡힌 이진 탐색 트리로, 트리의 높이를 최소한으로 유지하여 검색, 삽입, 삭제 시 최악의 성능이 발생하지 않도록 보장합니다. 요소들은 이 트리의 규칙에 따라 항상 정렬된 상태로 저장됩니다.

트리의 높이에 비례하여 삽입, 삭제, 검색 연산에서 O(log n)의 시간 복잡도를 가집니다. HashSet이나 LinkedHashSet보다는 느리지만, 요소들을 항상 정렬된 상태로 유지하고 정렬된 순서로 순회(traverse)할 수 있다는 장점이 있습니다.

Q. Set을 사용할 때 메모리 사용량이나 성능을 최적화하기 위해 고려할 수 있는 점들은 무엇이 있을까요? 특히 HashSet의 초기 용량(initial capacity)과 로드 팩터(load factor) 같은 파라미터들이 성능에 어떤 영향을 미치는지 구체적으로 설명해 주시겠어요?

HashSet은 내부적으로 해시 테이블(배열)을 사용합니다. 초기 용량은 이 해시 테이블의 초기 크기를 의미합니다.

만약 예상되는 요소의 개수보다 너무 작은 초기 용량을 설정하면, Set에 요소가 계속 추가되면서 내부적으로 배열의 크기를 늘리는 리사이징(resizing, 또는 재해싱) 작업이 빈번하게 발생합니다. 이 리사이징 과정은 기존 요소들을 새로운, 더 큰 배열에 재배치해야 하므로 상당한 성능 저하를 일으킬 수 있습니다. 반대로 너무 큰 초기 용량을 설정하면, 사용되지 않는 메모리 공간이 많아져 메모리 낭비가 발생할 수 있습니다.

따라서 Set에 저장될 예상되는 요소의 최대 개수를 미리 파악하여 적절한 초기 용량을 설정하는 것이 좋습니다.

예를 들어, 예상 개수 / (로드팩터 +1) 정도가 될 수 있지요. 여기서 로드 팩터는 해시 테이블이 얼마나 채워졌을 때 리사이징을 시작할지 결정하는 임계값으로 기본값은 0.75입니다.

로드팩터가 높으면 테이블을 더 많이 채울 수 있으므로 메모리 사용 효율은 높아지지만, 해시 충돌 가능성이 증가하여 각 버킷에 저장된 요소들의 연결 리스트(또는 트리) 길이가 길어집니다. 이는 삽입, 삭제, 검색 시 평균 O(1) 성능이 O(n)에 가까워지게 만들 수 있습니다.

반대로 낮으면 리사이징이 더 자주 발생하여 성능 저하가 올 수 있지만, 해시 충돌 가능성은 줄어들어 검색 성능은 좋아질 수 있습니다.

Q. 데이터를 Set 구현체로 사용하는 Collection에 넣으면 이상하게도 ordering을 보장하지 않는 특성을 가짐에도 여러번 반복적으로 데이터를 담은 뒤 관측했을때 순서를 보장하는 것처럼 보이는 경우가 있습니다. 왜 그런 것일까요?

Set 중에서도 특히 HashSet은 순서가 보장되지 않는다는 특성을 가집니다.

이는 내부적으로 HashMap을 사용하여 데이터를 해시 테이블에 저장하기 때문입니다. HashMap은 요소를 추가할 때 해당 요소의 hashCode() 값을 계산하고, 이 해시 값을 기반으로 해시 테이블(배열)의 특정 '버킷(bucket)'에 요소를 배치합니다.

여기서 핵심은 동일한 입력에 대해 해시 함수는 항상 동일한 해시 값을 반환한다는 점입니다.

또한, 해시 값을 배열의 인덱스로 매핑하는 방식(hash % capacity) 역시 동일한 조건에서는 일관된 결과를 냅니다.

그렇기 때문에, 만약 동일한 데이터를 동일한 순서로 HashSet에 여러 번 삽입하고, JVM(Java Virtual Machine)의 실행 환경(예: 해시 알고리즘, 초기 용량, 로드 팩터 등)에 큰 변화가 없다면, 각 요소의 해시 값 계산과 해시 테이블 내 버킷 배치가 매번 똑같은 방식으로 일어나게 됩니다.

이러한 일관된 배치 때문에 겉으로 보기에는 마치 순서가 보장되는 것처럼 '우연히' 일정한 출력 순서를 보일 수 있습니다. 특히 데이터의 크기가 작고, 해시 충돌이 거의 발생하지 않아 각 버킷에 하나의 요소만 저장되는 상황에서는, 내부 배열의 인덱스 순서대로 요소가 배치되면서 삽입 순서와 비슷하게 출력될 가능성이 더 높아지기도 합니다.

하지만 이는 순서가 '보장'되는 것이 아니라 우연에 의한 결과이며, JVM 재시작, 다른 환경에서의 실행, 데이터의 변경 또는 개수 증가 등으로 언제든지 순서가 바뀔 수 있습니다.

Q. HashSet과 TreeSet을 비교했을 때, 어떤 상황에서 TreeSet을 굳이 사용할 필요가 없을까요?

HashSet은 내부적으로 해시 테이블을 사용하여 평균적으로 O(1)이라는 매우 빠른 시간 복잡도로 삽입, 삭제, 검색을 수행합니다.

반면에 TreeSet은 내부적으로 레드-블랙 트리라는 균형 이진 탐색 트리를 사용하여 데이터를 정렬된 상태로 유지하며, 이 때문에 삽입, 삭제, 검색 연산에서 O(log n)의 시간 복잡도를 가집니다.

이러한 성능 차이와 TreeSet이 데이터를 정렬 상태로 유지하는 데 드는 추가적인 연산 비용(오버헤드) 때문에 다음과 같은 상황에서는 TreeSet을 사용할 필요가 없습니다.

1. 데이터의 중복 제거 또는 존재 여부 확인이 주 목적이고, 요소의 순서나 정렬이 전혀 중요하지 않을 때

   • 예를 들어, 웹사이트 방문자의 고유 IP 주소를 빠르게 식별하거나, 이미 처리된 데이터의 중복 여부만 확인하면 되는 상황에서는 HashSet이 훨씬 효율적입니다. TreeSet을 사용하면 불필요한 정렬 작업으로 인해 성능 손실만 발생합니다.

2. 대량의 데이터를 빠르게 저장하거나 조회해야 하지만, 정렬된 순서로 데이터를 꺼낼 필요가 없을 때

   • HashSet은 해싱 덕분에 대용량 데이터 처리에서도 뛰어난 평균 성능을 보입니다. 정렬 기능이 필요 없다면, TreeSet의 O(log n) 성능은 HashSet의 O(1)에 비해 상대적으로 느릴 수 있습니다.

요약하자면, 데이터를 정렬된 상태로 유지할 필요가 없고 오로지 중복 제거와 빠른 접근(삽입/삭제/검색)이 핵심 요구사항일 때는 HashSet이 훨씬 더 적절하고 효율적인 선택이며, TreeSet을 사용하는 것은 불필요한 리소스 낭비가 될 수 있습니다.

Q. TreeSet의 레드-블랙 트리가 뭔가요?

TreeSet은 내부적으로 레드-블랙 트리(Red-Black Tree) 라는 자료구조를 사용하여 요소를 저장하고 관리합니다.

레드-블랙 트리는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree) 의 한 종류입니다.

일반적인 이진 탐색 트리는 데이터가 삽입되는 순서에 따라 트리가 한쪽으로 치우쳐질 수 있으며, 이 경우 검색, 삽입, 삭제의 최악 시간 복잡도가 O(n)까지 저하될 수 있습니다.

레드-블랙 트리는 이러한 문제점을 해결하기 위해 각 노드에 '빨간색(Red)' 또는 '검은색(Black)' 속성을 부여하고, 특정 규칙들을 따르도록 강제하여 트리의 균형을 항상 일정 수준 이상으로 유지합니다. 이 균형 유지 덕분에 어떤 경우에든 삽입, 삭제, 검색 연산의 시간 복잡도를 O(log n)으로 보장할 수 있습니다.

레드-블랙 트리의 주요 5가지 규칙은 다음과 같습니다.

1. 모든 노드는 빨간색이거나 검은색이다.

2. 루트 노드는 검은색이다.

3. 모든 리프 노드(NIL 노드 또는 자식이 없는 노드)는 검은색이다. (실제로 데이터는 없지만 트리의 끝을 나타내는 가상의 노드를 의미)

4. 빨간색 노드의 자식은 모두 검은색이다. (즉, 빨간색 노드는 연속으로 나타날 수 없다.)

5. 어떤 노드로부터 그 자손 리프 노드까지 이르는 모든 경로에는 동일한 개수의 검은색 노드가 있다. (이를 Black Depth라고 부르며, 트리의 균형을 유지하는 핵심 규칙입니다.)

데이터를 삽입하거나 삭제할 때, 이 5가지 규칙이 깨질 수 있습니다. 이때 레드-블랙 트리는 노드의 색깔을 변경(Recoloring) 하거나 트리 구조를 재조정(Restructuring) 하는 회전(Rotation) 작업을 통해 다시 균형을 맞춥니다.

특히 삽입 시에는 새 노드를 항상 빨간색으로 삽입한 후, 부모와 삼촌 노드의 색깔, 그리고 자신의 위치에 따라 적절한 재조정 작업을 수행하여 규칙을 만족시킵니다.

이러한 복잡하지만 정교한 규칙과 재조정 메커니즘 덕분에 TreeSet은 대용량의 데이터를 효율적으로 저장하면서도 항상 정렬된 상태를 유지할 수 있습니다.

Q. 멀티스레드 환경에서 Set 자료구조를 안전하게 사용하려면 어떤 방법을 적용할 수 있을까요? java.util.concurrent 패키지에서 제공하는 동시성 Set 구현체가 있다면 설명해주시고, 일반 Set을 동기화하는 방법과 비교하여 설명해 주시면 좋겠습니다.

멀티스레드 환경에서 Set 자료구조를 안전하게 사용하기 위한 방법은 크게 두 가지로 나눌 수 있습니다.

일반 Set을 동기화하는 방법과 java.util.concurrent 패키지의 동시성 Set을 사용하는 방법입니다.

일반 Set을 동기화하는 방법이란 java.util.Collections 유틸리티 클래스에서 제공하는 synchronizedSet() 정적 메소드를 사용하여 기존의 Set 객체를 래핑(wrap) 하는 것입니다.

Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());

이 메소드는 내부적으로 모든 Set 연산에 대해 하나의 전역 락(intrinsic lock)을 걸어 스레드 안전성을 확보합니다.

즉, 한 번에 하나의 스레드만이 Set의 메소드에 접근하여 연산을 수행할 수 있도록 보장합니다.

구현이 매우 간단하고, 기존의 Set 구현체를 그대로 활용할 수 있다는 점이 장점입니다만, 심각한 성능 병목 현상이 발생할 수 있습니다.

모든 연산이 동일한 전역 락에 의해 보호되기 때문에, 여러 스레드가 동시에 Set에 접근하려 할 때 락 경합(contention) 이 심해져 동시성이 크게 저하됩니다. 특히 읽기(read) 연산이 많을 때도 쓰기(write) 연산과 동일하게 락을 획득해야 하므로 비효율적입니다. '모든 것을 잠그는' 방식으로 인해 고성능이 요구되는 멀티스레드 환경에서는 적합하지 않습니다.

다음으로 java.util.concurrent 패키지에서는 Set 인터페이스를 직접적으로 구현하는 독립적인 클래스를 제공하지는 않지만, ConcurrentHashMap을 기반으로 한 스레드 안전한 Set을 생성하여 사용할 수 있습니다.

ConcurrentHashMap.newKeySet() 메소드를 사용하여 ConcurrentHashMap의 키 집합을 Set처럼 활용하는 방식입니다.

Set<String> concurrentSet = ConcurrentHashMap.newKeySet();

ConcurrentHashMap은 내부적으로 Collections.synchronizedSet()과 같은 전역 락을 사용하지 않습니다. 대신 세그먼트(Segment) 또는 노드(Node) 단위의 락 분할(Striped Locking) 메커니즘을 사용하며, Java 8 이후에서는 CAS(Compare-And-Swap) 연산과 같은 락 프리(lock-free) 알고리즘을 적극적으로 활용하여 동시성을 높입니다. 이를 통해 여러 스레드가 다른 부분에 동시에 접근하여 연산을 수행할 수 있습니다.

여러 스레드가 동시에 Set의 다른 부분에 접근할 수 있어 Collections.synchronizedSet()에 비해 훨씬 높은 처리량(throughput)을 제공하고 락 경합이 훨씬 적습니다.

만약 정렬된 Set이 멀티스레드 환경에서 필요하다면 ConcurrentSkipListSet을 사용할 수 있습니다. 이는 스킵 리스트(Skip List)라는 자료구조를 기반으로 하여 정렬된 상태를 유지하면서도 높은 동시성을 제공합니다.