우선 Set 인터페이스 구현체들에 대해 알아보기에 앞서, Set 인터페이스는 어떤 메서드들을 제공하는지 알아본다.
Set 인터페이스
Set 인터페이스는 Collection 인터페이스를 상속받으며, 중복된 요소를 허용하지 않는 자료구조를 나타내는 인터페이스이다.
Set의 주요 특징은 다음과 같다.
- 중복된 요소 허용X
- 요소의 저장 순서를 유지하지 않음 (HashSet, LinkedHashSet을 제외하고는 보장하지 않음)
- 순서와 관계없이 요소에 대한 접근 및 검색이 빠름
간단하게 Set 인터페이스를 구현하는 다양한 구현체들이 있다. 이들에 대해 하나씩 알아보도록 하자.
다양한 Set 인터페이스 구현체들
HashSet
HashSet 은 해시 테이블에서 데이터를 검색하는 방식으로 동작하고 내부적으로는 HashMap을 이용해서 구현되어 있다. 데이터를 저장할 때, 각 데이터의 해시 코드(Hash Code)를 계산하여 해당 코드에 대응하는 버킷(Bucket)에 저장한다. 따라서 검색 속도가 매우 빠르다.
HashMap과 HashTable의 동작방식
HashTable은 Key-Value 쌍으로 데이터를 저장하고 검색하기 위한 자료구조로, 내부적으로 배열을 사용하여 데이터를 저장한다. Key값을해시 함수를 사용하여 배열의 인덱스로 변환한 뒤, 해당 인덱스에 데이터를 저장한다.
만약 해시함수를 통해 다른 데이터가 동일한 인덱스를 가지면 충돌이 발생하는데, 이를해시 충돌이라고 한다. 해시 충돌을 해결하기 위해 여러 가지 충돌 해결 방법을 사용한다. 기본적으로는 연결리스트를 사용하여 데이터를 저장해서 해시 충돌을 피한다. 만약 같은 Key값을 가진 데이터가 이미 존재하는 경우, 연결리스트를 순회하면서 데이터를 검색합니다.
HashMap은 Thread-safe 하지 않고, HashTable은 Thread-safe하게 동작하기 위해 동기화된 메서드를 사용한다.
HashMap은 Thread-safe 하지 않고,HashTable은 Thread-safe하게 동작하기 위해 동기화된 메서드를 사용합니다. 그러나, Thread-safe하게 동작하기 위해synchronized키워드를 사용하는 것은 성능이 저하될 수 있으므로,ConcurrentHashMap이라을 이용해 더욱 효율적으로 동작할 수 있습니다.
HashSet 은 null 값을 저장할 수 있으며, 다른 클래스의 객체도 저장 가능하다. 그리고 저장된 객체가 HashSet 내에서 어떤 순서로 저장되는지는 보장되지 않습니다.
또한 HashSet은 Thread-safe하지 않으므로, 멀티스레드 환경에서 안전하게 사용하려면 동기화 처리를 해주어야 한다. 만약 동기화 처리를 하지 않으면, 여러 스레드에서 동시에 HashSet에 접근하여 데이터를 변경하려 할 때 의도치 않은 결과가 발생할 수 있습니다.
즉, HashSet 은 해시 테이블을 사용해서 요소를 저장하고, 추가 & 삭제 & 조회에 O(1)의 시간복잡도를 가집니다.
TreeSet
TreeSet은 이진 검색 트리를 사용하여 요소를 저장한다. 정확히는 Red-black Tree 를 통해 구현되어 있습니다.
Red-black Tree는 편향 이진트리의 단점을 보완하기 위한 트리로, 데이터의 삽입/삭제 시 좌우 균형을 맞춰주는 트리이다. 더 자세한 내용은 해당 포스팅을 참고하도록 하자.
이진 검색 트리는 모든 요소를 정렬된 상태로 유지하므로, TreeSet에 저장된 요소들은 항상 정렬된 상태로 유지됩니다. 그렇기 때문에 TreeSet은 null을 허용하지 않습니다.
이러한 특징으로 TreeSet은 정렬된 데이터를 저장하고 검색하는데 유용합니다. 또한 요소를 정렬된 순서로 저장하므로, 추가, 삭제, 조회에 O(log N)의 시간 복잡도를 가집니다.
LinkedHashSet
해시 테이블과 연결 리스트를 사용하여 요소를 저장합니다. 요소를 추가한 순서대로 저장하므로, 순서가 보장됩니다. 즉, HashSet 과 거의 동일하지만, 원소들의 삽입 순서를 보장합니다.
ConcurrentSkipListSet
ConcurrentSkipListSet 은 Skip List를 이용하여 요소를 저장하고 정렬합니다. Skip List는 이진 검색 트리와 유사한 자료구조로, 각 요소에 대해 랜덤한 레벨(level)을 부여하여 구성됩니다. 레벨은 높을수록 해당 요소의 검색에 걸리는 시간이 적어지며, 랜덤하게 부여되기 때문에 균등한 검색 성능을 보장합니다.
Skip List의 특성상 요소의 삽입, 삭제, 검색 시간이 O(logN) 으로 상대적으로 빠르다.
그리고 ConcurrentSkipListSet의 가장 중요한 특징으로 이 자료구조는 Thread-safe하게 구현되어 있어, 동시에 여러 스레드에서 사용할 수 있습니다.
ConcurrentSkipListSet은 Set 인터페이스의 메서드뿐만 아니라, NavigableSet 인터페이스의 메서드들도 구현하고 있어, 범위 검색(Range Search)이나 근접 요소 검색(Proximity Search) 등 다양한 기능을 수행할 수 있습니다.
Reference
https://velog.io/@jsj3282/HashMap-HashTable-HashSet-ConcurrentHashMap%EA%B3%BC-Thread-Safe#10-thread-safe--hashtable-vs-thread-unsafe--hashmmap
https://code-lab1.tistory.com/62
