자료구조 : Set

이번 포스팅에서는 자바의 컬렉션 프레임워크 중 하나인 Set에 대해서 알아보는 시간을 가져보도록 하겠습니다. 

 

우선 자료구조 Set은 뭘까요? 

 

음... 깊게 알고싶지 않다면 Set은 중복을 허용하지 않는 자료구조라고만 알고 계셔도 무방할 것 같습니다. 

 

하지만 이번 포스팅에선 좀 더 깊은 내용을 다룰 예정입니다. HashSet을 사용하면 Hash값을 가지고 값을 찾을텐데 어떻게 중복을 방지하는 것인지, TreeSet은 어떤 알고리즘으로 정렬을 지원하는지. 이런 내용에 대해서 다룹니다. 

 

들어가기 전에 말씀드리자면 자료구조 Set에 대한 전반적인 내용을 다루는 포스팅이기 때문에 사용방법에 대해서는 다루지 않습니다. 메서드에 대한 내용은 따로 알아보시는 것을 추천드립니다. 

 

Set

Set은 데이터를 비순차적으로 저장할 수 있는 자료구조입니다. 비순차적이기 때문에 데이터 삽입 순서대로 저장되지 않아서 특정한 순서를 기대할 수 없습니다. 

 

ArrayList와 마찬가지로 값의 수정이 가능하고 중복을 허용하지 않아서 같은 값을 삽입하면 마지막 삽입한 값 하나만 저장됩니다. 

 

Set 과 ArrayList는 닮은 구석이 많습니다. 그도 그럴것이 양쪽 다 AbstractCollection을 상속하고 있기 때문이죠

 

여기서 잠깐 Set과 List의 차이에 대해서 집고 넘어가도록 하겠습니다.

 

Set vs List

• List는 중복을 허용합니다. Set은 중복을 허용하지 않습니다. 
• List는 삽입에의한 순서를 보장합니다. Set은 보장하지 않습니다.
• Set은 List처럼 인덱스에 기반한 접근을 허용하지 않습니다. 

 

Set은 빠른 데이터 탐색이 필요할 때 주로 사용되는 자료구조입니다. 

 

Set은 인터페이스입니다. 자바는 이러한 인터페이스에서 다형성을 이용해 여러가지 구현체들을 구현해놓았습니다. 

 

대표적인 Set의 구현체로는 HashSet, TreeSet, LinkedHashSet 등이 있습니다. 하나씩 특징을 알아볼까요?

 

 

HashSet

HashSet은 자바 컬렉션 API들 중 가장 근본적인 자료구조 중 하나입니다. 

 

HashSet의 특징으로는

1. 유니크한 값을 저장할 수 있다.
2. 저장시 null을 허용한다.
3. 해시맵에 의해 구동됩니다.
4. 삽입순서를 유지하지 않습니다. 
5. thread-safe 하지 않습니다. 

 

이정도로 간추릴 수 있겠습니다. Hash 알고리즘을 사용한 자료구조이기 때문에 해시가 가지고 있는 특징들이 그대로 드러납니다. 

 

때문에 해시의 특징과 Set의 특징이 모두 두드러지게 나타납니다. 

 

그런데 여기서 살짝 의문이 들 수 있습니다. 

 

해시는 저장할 때 유일한 값을 가지는데... 중복은 허용하지 않는다? 이게 말이 되나?

 

그러니까 HashSet에 값을 넣는데 1이라는 값을 두번 넣게되면 해시의 특징대로면 1이라는 해시(주소)가 부여되고 그에 해당하는 bucket이 할당됩니다. 그리고 1이라는 값이 두번 들어오게 되면 각각은 다른 해시값을 가지고 다른 bucket에 부여됩니다. 

 

그런데 중복을 어떻게 허용하지 않을까요? 

 

 

HashSet이 어떻게 유니크함을 유지할까?

Set의 공식문서에는 다음과 같이 나와있습니다. 

 

해석해보면 다음과 같습니다.

 

"HashSet에 객체를 삽입할 때 삽입되는 객체는 그 객체의 해시코드 값을 이미 해당 값이 저장되어 있는지 아닌지 확인하는데에 사용합니다."

 

"각각의 해시코드 값들은 다양한 요소들이 들어있을 수 있는 특정한 bucket의 장소에 상응됩니다. 그렇기 때문에 계산된 해시값들은 모두 같습니다. 하지만, 두개의 객체의 해시코드는 같지 않습니다."

 

즉 두 값의 해시코드는 같지 않지만 그 값의 해시코드로 값이 저장되어있는지 아닌지 확인한 후에 저장되어있다면 값을 버리고 마지막 값을 저장한다는 의미인 것 같습니다. 

 

이러한 HashSet의 특징 때문에 equals 메서드로 두개의 객체를 비교할 수 있습니다. 

 

HashSet의 성능

HashSet의 성능은 크게 두가지 요인에 의해 결정됩니다. 바로 초기용량과 Load Factor입니다. 뭐 초기 용량은 그렇다 치는데 Load Factor는 뭘까요? 

 

Load Factor

Load Factor에 대한 내용은 HashSet 클래스를 직접 까보면 알 수 있습니다. HashSet의 클래스를 까보면 HashSet은 HashMap을 이용하는 것을 알 수 있습니다. 

 

 

왜 HashSet의 특징에서 HashMap에 의해 구동된다고 하는지 알 수 있습니다. 우리가 눈여겨 봐야 하는 것은 바로 이 부분이죠

 

HashSet의 기본 생성자는 단순히 HashMap을 생성하지만 Capacity와 Load Factor를 파라미터로 받는 생성자인 경우 HashMap에서 추가적인 지원을 받을 수 있습니다. 

 

간단하게 설명하자면

 

저장된 element의 수 = 저장용량 X Load Factor 입니다.

 

즉, 저장용량이 고정되어 있을 때 element를 증가시키면 load factor도 커지겠죠. 커지다가 0.75에 도달하게 되면 저장용량을 약 두배로 늘립니다. 이때 저장용량을 늘리는 과정이 애플리케이션에 부하를 많이 주게 됩니다. 

 

그래서 저장될 데이터의 수가 대충 짐작이 가능하다면 처음에 객체를 생성할 때 저장용량을 데이터 수에 맞게 설정해주면 좋습니다. 

 

Load Factor는 0.75값이 가장 이상적인 값이라고 가이드에 나와있습니다. 

 

물론 개발하려는 애플리케이션의 목적에 따라 값을 수정할 수 있지만 대부분의 상황에선 기본값을 쓰는게 좋다고 합니다. 

 

아무튼 Load Factor에 대해 대충 알아봤습니다. 

 

HashSet의 성능은 기본적으로 O(1)이지만 가장 최악의 상황에는 O(n)까지 늘어날 수 있습니다. 

 

 

TreeSet

TreeSet은 Set 인터페이스에서 정렬을 담당하는 클래스입니다. 

 

TreeSet의 특징

• TreeSet은 유니크한 값을 저장합니다.
• 삽입에의한 순서를 보장하지 않습니다.
• 기본 생성자로 TreeSet을 생성하면 오름차순으로 정렬됩니다. (물론 reverseOrder() 라는 메서드를 이용해 내림차순으로 역정렬할 수 있습니다.)
• tread-safe 하지 않습니다. 

 

TreeSet의 객체들은 수학적으로 보장된 순서대로 오름차순으로 정렬됩니다. 여기서 수학적으로 보장된 순서란 0 1 2 3 4 이런 식의 순서를 의미하고 문자들은 아스키코드로 변환된 수를 오름차순으로 정렬합니다. 

 

TreeSet과 이진 트리

TreeSet은 균형잡힌 이진 탐색 트리 즉, 레드 블랙 트리로 데이터를 저장합니다. 

 

이진 탐색 트리, 레드 블랙 트리에 대해서는 아래의 링크에 자세히 설명되어있습니다.

 

https://coding-review.tistory.com/286

자료구조 : Tree

 

TreeSet은 자바7이전에는 빈 TreeSet에 null을 저장하는 것이 가능했습니다. 하지만 그렇게 하게 되면 수많은 버그들이 고려되기 때문에 TreeSet은 자바8부터 null을 저장하는 것이 불가능해졌습니다. 

 

TreeSet은 이진 탐색 트리로 값을 정렬하고 저장하지만 null이 들어오게 되면 이진 탐색 트리에 조건에 맞는 저장방식을 사용할 수 없기 때문입니다. 

 

 

TreeSet의 성능

TreeSet의 성능은 HashSet은 O(1)에서 최대 O(n)이었던 것과 다르게 O(log n)을 따릅니다. 시간 복잡도에서 O(log n)은 성능이 좋은 축에 속합니다. 따라서 값을 오름차순 혹은 내림차순으로 정렬해야 하거나 값의 중복을 피하고 싶다면 TreeSet을 사용하는 것이 좋은 선택이 될 수 있습니다.

 

참고로 성능상으로는 오름차순이 내림차순보다 성능상 이점이 더 많습니다. 내림차순이 필요한게 아니라면 굳이 내림차순을 사용할 필요는 없겠네요

 

 

LinkedHashSet

LinkedHashSet은 HashSet의 자식클래스입니다. 그러므로 HashSet의 특징을 그대로 따르고 있습니다. 중복을 허용하지 않는다거나 Hash를 사용한다거나 하는 특징들 말이죠

 

하지만 LinkedHashSet의 특징은 단순합니다. 

 

바로 삽입되는 순서를 보장하지 않던 HashSet의 단점을 보완하기위해 나온 클래스입니다. 

 

TreeSet에서 복잡하게 삽입된 순서를 정렬하고 할 것 없이 LinkedHashSet을 사용하면 삽입된 순서를 깔끔하게 보장할 수 있습니다. 

 

하지만 그렇기 때문에 HashSet보다는 성능적으로 좀 뒤쳐지는 것이 사실입니다. 하지만 정말 미미한 수준이고 시간 복잡도는 HashSet과 마찬가지로 O(1)입니다. 

 

사실 LinkedHashSet은 HashSet과 동일하고 순서만 보장해주기 때문에 더 말할 것이 없습니다. 

 

 

 

여기까지 Set 자료구조에 대해서 알아봤습니다. 그리고 그 구현체들, 구현체들의 특징에 대해서 알아봤죠.

 

이번 공부는 구글링 했을 때 결과가 만족스럽지 못해서 공식문서를 직접 다 뒤져보면서 찾아봤기 때문에 더 힘들면서 더 보람차고 뿌듯하네요. 

 

이런식으로 공부하는 것이 더 머릿속에 남긴 하겠지만서도 너무 힘들어서 또 할 수 있을까싶네요. 

 

긴 글 읽어주셔서 감사합니다. 오늘도 즐거운 하루 되세요!

 

 

출처

https://www.baeldung.com/java-hashset

=> HashSet 공식문서

 

https://www.baeldung.com/java-set-vs-list

=> Set vs List 공식문서

 

https://www.baeldung.com/java-tree-set

=> TreeSet 공식문서

 

https://www.baeldung.com/java-linkedhashset

=> LinkedHashSet 공식문서