Java - HashSet, LinkedHashSet, TreeSet 차이

Set

이번 시간에는 Java Collection 중에서 Set에 대해서 알아보도록하겠다. Set은 Array와 비슷하게 배열이지만 중복을 허락하지 않는다는 특징이 있다. Set은 사실 Map을 사용해서 구현된 자료구조이다. Map은 Key 값을 중복되지 않게 관리하는 특징이 있다. Set은 이러한 Map의 특징을 사용해서 값을 넣을 때는 Map에 집어 넣고 Map의 Key 값만 사용함으로써 중복되지 않는 배열을 제공하는 것이다. Map의 Value 값에는 미리 지정된 하나의 객체를 저장한다. Set이 Map이나 Array처럼 새로운 구조가 아니라 Map을 사용한 파생된 자료구조라는 것이다. 그렇기 때문에 Java에서는 Set이라는 자료구조를 기본적으로 제공하지만 GoLang 같은 경우에는 Map을 사용해서 간단하게 직접 Set을 만들어서 써야한다. 

 

HashSet

먼저 가장 많이 사용되는 HashSet에 대해서 알아보도록하자. HashSet은 사실상 HashMap과 동일하게 작동하는데 단지 Key값만 Map에서 사용할 뿐이다. 이전 포스팅에서 다루었듯이 HashMap은 HashTable과 LinkedList를 사용해서 구현되어 있고 마찬가지로 HashSet도 동일한 구조로 구현되어 있다. 그렇기 때문에 순서를 보장하지 못한다는 특징이 있다. HashMap과 동일하게 순서를 보장하고 싶으면 다음으로 소개할 LinkedHashSet을 사용해야 한다.

 

LinkedHashSet

HashSet은 순서를 보장해주지 못하는데 LinkedHashSet을 사용하면 순서를 보장받을 수 있다. LinkedHashSet도 HashSet과 동일하게 내부적으로 LinkedHashMap을 사용하고 LinkedHashMap에서 Key 값만을 가져와서 사용하는 구조이다. 이전 포스팅에서 설명했듯이 LinkedHashSet은 HashSet과 동일하지만 추가적으로 순서를 저장하고 있는 LinkedList를 하나더 가지고 있다는 특징이 있다. 마찬가지로 LinkedHashSet에서는 순서를 저장하고 있는 LinkedList를 사용해서 순서를 보장해준다.

 

TreeSet

마지막으로 TreeSet인데 TreeSet도 위의 자료구조들과 동일하게 TreeMap을 내부적으로 사용한다. TreeSet은 자동으로 정렬이 이루어진다는 점에서 TreeMap과 동일하다. 차이점은 TreeMap에서 Key값 만을 사용한다는 점이다. 삽입, 삭제를 할 때마다 정렬이 이루어지기 때문에 가장 성능이 느리다. Set, Map이라고 하면 O(1)의 시간복잡도를 생각하지만 Tree를 사용하기 때문에 O(logn)의 성능을 가지고 있다. 

 

정리하자면 Set은 중복되지 않게 데이터를 관리할 수 있고 내부적으로 Map을 사용한다. 별다른 필요가 없다면 HashSet을 사용하면 되고 순서를 보장해야 한다면 LinkedHashSet을 사용하고 매번 정렬이 필요한 구조라면 TreeSet을 사용하면 된다. 성능은 기능 필요가 하나씩 들어갈 때마다 느려지기 때문에 HashSet이 가장 빠르다.