Set이란? HashSet, TreeSet, LinkedHashSet

이번 글의 목적은 Set에 대해 이해하고, HashSet과 TreeSet, LinkedHashSet이 있는데 이 기능은 무엇이 있고, 어느 상황에 사용하면 좋을지 생각해는 것이다. 

---

1. Set이란?

중복이 없는 element들을 저장하는 컬렉션.
더 형식적으로, set은 e1.equals(e2)같은 e1과 e2 의 한 쌍을 가지지 않는다.
이름에 함축되어 있듯이, 이 인터페이스는 수학적인 set abstraction을 모델화한다.

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/Set.html

또한, set을 이해하기 위해 다음 그림을 참고하면 좋다.

 

출처 : https://coding-factory.tistory.com/554

 

수학적으로 중복되지 않은 항목들이 모인 것을 set라고 한다.

 

간단하게 set의 특징에 대해 이야히가면,

 

1. Set은 중복 값을 삽입할 수 없고, 2. 특정한 순서를 가지고 있지 않다

 

지원 메소드 더보기 클릭!

Modifier and TypeMethod and Description

boolean	add(E e) Adds the specified element to this set if it is not already present (optional operation).
boolean	addAll(Collection<? extends E> c) Adds all of the elements in the specified collection to this set if they're not already present (optional operation).
void	clear() Removes all of the elements from this set (optional operation).
boolean	contains(Object o) Returns true if this set contains the specified element.
boolean	containsAll(Collection<?> c) Returns true if this set contains all of the elements of the specified collection.
boolean	equals(Object o) Compares the specified object with this set for equality.
int	hashCode() Returns the hash code value for this set.
boolean	isEmpty() Returns true if this set contains no elements.
Iterator<E>	iterator() Returns an iterator over the elements in this set.
boolean	remove(Object o) Removes the specified element from this set if it is present (optional operation).
boolean	removeAll(Collection<?> c) Removes from this set all of its elements that are contained in the specified collection (optional operation).
boolean	retainAll(Collection<?> c) Retains only the elements in this set that are contained in the specified collection (optional operation).
int	size() Returns the number of elements in this set (its cardinality).
default Spliterator<E>	spliterator() Creates a Spliterator over the elements in this set.
Object[]	toArray() Returns an array containing all of the elements in this set.
<T> T[]	toArray(T[] a) Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array.

https://docs.oracle.com/javase/8/docs/api/java/util/Set.html

 

이것을 설명하기 전에 전체 구조를 다시 한번 보고 가는게 좋겠다.

 

필자도 헷갈리니 그림의 힘을 빌리겠다.

출처 : https://www.geeksforgeeks.org/treeset-in-java-with-examples/

2. HashSet이란? / HashSet과 HashMap과 차이점 / 간단 확인

이 클래스는 해쉬 테이블(실제로 HashMap 인스턴스)에 의해 지원되는 set 인터페이스를 구현한다. 

이것은 set의 순회 순서를 보증하지 않는다. 특히, 순서가 여러번 상수로 남을 것이라는 보장이 없다. 이 클래스는 null element를 허용한다. 

...

이 구현체는 동기화되지 않는다는 점을 명심해라. 

만약 멀티 스레드가 동시발생적으로 hash set 에 접근하고, 적어도 스레드 중 하다가 set 을 수정한다면, 외부적으로 동기화 되야 한다. 

이것은 전형적으로 set을 자연스럽게 캡슐화하는 몇몇 객체를 동기화 함으로서 해결된다.

만약 그러한 객체가 없다면, set은 Collectyions.synchronizedSet 메소드를 이용하는 wrapped가 되야할거다.

...

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

 

흥미로운 점이 있는데 내부 구현 클래스에 HashMap이 있다는 것이다. (왜...?)

 

oracle에서 설명한 글 맨 첫번째 줄에 보면... hash table으로 지원된다고 하는데 실제로는 HashMap을 이용해 지원한다고 한다.

 

그리고 동기화를 하려면 친절하게 특정 메소드를 이용해 해당 객체를  Wrapp해서 하라고 한다. 

 

여기서 잠시 다시 한번 HashMap과 HashTable의 차이점이 헷갈린다면 다음을 보면 된다. 

 

궁금하면 (500원) 더보기 클릭!

HashMap과 HashTable의 차이점

 

	HashMap	HashTable
1.	No method is synchronized.	Every method is synchronized.
2.	Multiple threads can operate simultaneously and hence hashmap’s object is not thread-safe.	At a time only one thread is allowed to operate the Hashtable’s object. Hence it is thread-safe.
3.	Threads are not required to wait and hence relatively performance is high.	It increases the waiting time of the thread and hence performance is low.
4.	Null is allowed for both key and value.	Null is not allowed for both key and value. Otherwise, we will get a null pointer exception.
5.	It is introduced in the 1.2 version.	It is introduced in the 1.0 version.
6.	It is non-legacy.	It is a legacy.

출처 : https://www.geeksforgeeks.org/differences-between-hashmap-and-hashtable-in-java/

 

필자 생각으로는 HashTable이 HashMap에 비해 오래걸리는 작업이라 HashMap을 사용한게 아닌가 짐작한다.

 

위 출처에서 글을 읽다 보면 fail-fast 라는 용어도 나오는데 용어 설명이 궁금하면 다음 더보기를 클릭하면 된다. 

 

정리가 잘 되어있으니 참고하면 좋다. (선배 개발자님 감사합니다...)

간단히 말하면 처리 과정에서 실패할 가능성이 보인다면 즉시 중지하고 상위 인터페이스에 보고하여 조기에 오류를 처리하는 동작 방식이다.

 

출처 : https://delf-lee.github.io/post/fail-fast/

 

어쨋든 확인 결과 HashMap이 실제로 있는 것을 확인할 수 있었다.

 

HashTable보다 속도면에서 빨라서 그런 것 같기도 하고... 누구 아는 사람 있으면 피드백을 환영한다!

 

 

HashSet도 내부적으로 코드를 보면 해당 용량에 따라서 HashMap을 생성하고 map을 반환하는것이다.

 

여기에 transient 가 분어 있는데 이것은 Serialize하는 과정에서 제외하고 싶은 경우 선언하는 키워드다.

간단 확인해보기

사실 구현을 해보려고 했는데

기존의 collection 들과 사용법이 매우 유사하며 예제로 너무 많았다.

 

아주 간단하게 돌려만 봤다.

HashSet.java

package me.whiteship.collection.tree;

import java.util.HashSet;
import java.util.Set;

public class HashSetTest {

    public static void main(String[] args) {
        Set<String> setTest = new HashSet<>();
        Set<String> addAllSet = new HashSet<>();

        //1. HashSet에 값 추가 - 존재여부 판단
        System.out.println("1. HashSet에 값 추가 - 존재여부 판단");
        setTest.add("test1");
        boolean isExist = setTest.contains("test1");
        System.out.println("isExist = " + isExist);
        System.out.println();


        //2. 제거 및 확인
        System.out.println("2. 제거 및 확인");
        setTest.remove("test1");
        boolean isEmpty = setTest.isEmpty();
        System.out.println("isEmpty = " + isEmpty);
        System.out.println();

        //3. set에 set더해 보리기
        setTest.add("test1");
        setTest.add("test2");
        setTest.add("test3");

        addAllSet.add("111");
        addAllSet.add("222");
        addAllSet.add("333");

        setTest.addAll(addAllSet);
        setTest.forEach(System.out::println);
        System.out.println();

        // 순회하기
        setTest.stream().iterator().forEachRemaining(s -> {
            System.out.println("순회중...");
            System.out.println(s.toString());
        });
    }
}

 

출력 결과 확인

1. HashSet에 값 추가 - 존재여부 판단
isExist = true

2. 제거 및 확인 isEmpty = true

111
test2
222
test3
333
test1

순회중...
111
순회중...
test2
순회중...
222
순회중...
test3
순회중...
333
순회중...
test1
Process finished with exit code 0

 

추천 참고 사이트 : https://coding-factory.tistory.com/554

 

이 외에도 비슷한 기능은 많다. 그냥 적절한 것을 골라서 사용하면 될 것 같다.

 

stream도 사용도 하는 것 같고, List와 유사하게 add도 있고, remove도 있고, 순회 기능도 있고...

 

필요한것을 잘 찾아서 사용하면 될 것 같다. 다만 조심해야 하는 것이 반환값이 있는지 없는지가 좀 팁이 될 수 있을거라 생각한다. 

 

예를 들어, 위에서 add에 성공하면 true를 반환하고, 실패시에는 false를 반환한다. 

 

이렇듯이 사용법에 유의하면 될 것 같다.

3. TreeSet이란?

TreeMap에 기반한 NaviagableSet의 구현체.

성분들이 생성자가 사용되는것에 따라 natural ordering을 사용하거나, set 생성 시간에 제공됨 Comparator에 정렬된다.

이 구현체는 기본적인 작업(add, remove, 그리고 contains)에 보장된 log(n) 시간 비용을 제공한다.
(복잡도가 log(n)로 보증이 되면 쌉꿀!)

...

이 구현체는 동기화되지 않는다는 점을 명심해라.

이를 위해서는 외부에서 동기화가 되어야 한다.
...

출처 : https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

 

Map이고, Set이고 찾아봤을 때 NavigableXXX하는 것들이 많다. (SortedSet, SortedMap등등도 마찬가지...)

 

이것에 대해서는 나중에 좀 더 알아보도록 하겠다.

 

우선 이것도 재미있는 점은 TreeMap에 기반을 두었다는 점이다. 

 

처음으로 알아본 HashSet도 마찬가지로 내부적으로 HashMap으로 구성되어 있다. 흥미롭군!

 

지원 생성자 및 메소드 더보기 클릭

constructor and description

 

TreeSet() Constructs a new, empty tree set, sorted according to the natural ordering of its elements.

TreeSet(Collection<? extends E> c) Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.

TreeSet(Comparator<? super E> comparator) Constructs a new, empty tree set, sorted according to the specified comparator.

TreeSet(SortedSet<E> s) Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

Modifier and TypeMethod and Description

boolean	add(E e) Adds the specified element to this set if it is not already present.
boolean	addAll(Collection<? extends E> c) Adds all of the elements in the specified collection to this set.
E	ceiling(E e) Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
void	clear() Removes all of the elements from this set.
Object	clone() Returns a shallow copy of this TreeSet instance.
Comparator<? super E>	comparator() Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
boolean	contains(Object o) Returns true if this set contains the specified element.
Iterator<E>	descendingIterator() Returns an iterator over the elements in this set in descending order.
NavigableSet<E>	descendingSet() Returns a reverse order view of the elements contained in this set.
E	first() Returns the first (lowest) element currently in this set.
E	floor(E e) Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
SortedSet<E>	headSet(E toElement) Returns a view of the portion of this set whose elements are strictly less than toElement.
NavigableSet<E>	headSet(E toElement, boolean inclusive) Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
E	higher(E e) Returns the least element in this set strictly greater than the given element, or null if there is no such element.
boolean	isEmpty() Returns true if this set contains no elements.
Iterator<E>	iterator() Returns an iterator over the elements in this set in ascending order.
E	last() Returns the last (highest) element currently in this set.
E	lower(E e) Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
E	pollFirst() Retrieves and removes the first (lowest) element, or returns null if this set is empty.
E	pollLast() Retrieves and removes the last (highest) element, or returns null if this set is empty.
boolean	remove(Object o) Removes the specified element from this set if it is present.
int	size() Returns the number of elements in this set (its cardinality).
NavigableSet<E>	subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) Returns a view of the portion of this set whose elements range from fromElement to toElement.
SortedSet<E>	subSet(E fromElement, E toElement) Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet<E>	tailSet(E fromElement) Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
NavigableSet<E>	tailSet(E fromElement, boolean inclusive) Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

출처 : method summary in https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html

 

TreeSet은 기본적으로 Red-Black Tree같은 self-balancing 이진 탐색 트리의 구현체이다. 

 

그러므로 add, remove, search같은 기능은 log(N)의 복잡도를 가진다. 

 

그래서 위 3개의 작업을 수행하거나 큰 정렬 데이터를 저장하기 위해 사용하기에 가장 효율적인 데이터 구조로 여겨진다.

 

그리고 이 친구도 동기화가 지원되지 않아서 이를 위해서는 외부에서 해야 한다는데 이것은 다음 코드를 보면 바로 이해가 된다.

TreeSet ts = new TreeSet(); 
Set syncSet = Collections.synchronziedSet(ts); 

HashSet에서도 동일한 내용이 나왔었다.

 

이것이 바로 외부에서 동기화 한거다.

 

이에 대한 내용은 oracle 의 TreeSet에 대한 설명에서 다 찾아볼 수 있다.

 

친절하게 Collections.synchronizedSet method를 사용하라고 설명해준다.

 

트리에 대해서는 다음에 정리해서 첨부하겠다. (24시간이 모자라 오우예)

 

출처 : https://www.geeksforgeeks.org/treeset-in-java-with-examples/

 

4. LinkedHashSet

갑자기 들은 뇌피셜인데, LinkedHashSet, LinkedHashMap같은게 결국에는 순서 보장 때문에 생겨난게 아닌가 하는 생각이 든다.

 

하여간 위 친구에 대해 찾아봤는데 두개의 동일해 보이지만 다른 검색 결과를 확인할 수 있었다.

 

 

직접 읽어본 결과 큰 차이는 없지만, LinkedHashSet의 경우에 JDK 1.8 이상부터는 Spliterator라는 메소드가 추가되었다.

 

고로, 위 그림에서 두번째 사이트를 참고했다.

 

HashTable과 예측가능한 순회 순서를 가진 Set 인터페이스의 linked list구현체.

이 구현체는 entry 전부를 훑는 이중 연결 리스트를 유지하는 HashSet과는 다르다.

이 linked list는 순회 순서를 정의하고, set 안에 삽입된 순서다. 

삽입 순서는 만약 원소가 set에 다시 삽입된다면 영향을 받지 않는다는 것을 명심해라.
(사실 순서 보장 기능을 다 알고있지...)

출처 : https://docs.oracle.com/javase/10/docs/api/java/util/LinkedHashSet.html

 

자바를 공부하니 무언가 계속 내용들이 중복되는듯한 느낌이 든다. 

 

특히, linked 이 단어(아휴 지겹네...)의 경우 순서보장이 큰 관건이다. 

5. HashSet vs LinkedHashSet

Property	HashSet	LinkedHashSet
Data structure	It uses a Hashtable to store the elements.	It uses a HashTable and doubly linked list to store and maintain the insertion order of the elements.
Technique to store the elements	Hashing	Hashing
Insertion Order	It does not provide any insertion order. We can not predict the order of elements.	It provides an insertion order; we can predict the order of elements.
Null elements	It allows only one null element.	It also allows only one null element.
Memory	It requires less memory.	It requires more memory than HashSet.
Performance	It provides slightly faster performance than LinkedHashSet	It provides low performance than HashSet
Synchronized	Non-synchronized	Non-synchronized
Complexity for the insertion, removal, retrieval operations	O (1)	O (1)
Declaration	HashSet obj = new HashSet();	LinkedHashSet obj = new LinkedHashSet();
Extends	AbstractSet class	HashSet class
Implements	Set interface	Set interface
Initial Capacity	16	16
Package	java.util	Java.util

When to use HashSet and LinkedHashSet

삽입 순서를 유지하고 싶으면, LinkedHashSet이 유용할 것이다. 하지만 삽입 순서가 우리의 우선순위가 아니라면, HashSet이 유용하고 향상된 성능을 제공할것이다!

 

출처 : https://www.javatpoint.com/hashset-vs-linkedhashset-in-java

---

사실 구현체들은 너무 기능이 다 비슷비슷해서 필자는 너무 재미가 없다!

 

필자가 정리하는 내용들은 대부분 그냥 있는 것들을 추합해서 혹시모를 읽는 이를 위한것이 아닌 나 자신을 위한것이라 라 좀 부족할 수 있다. 양해바랍니다. 꾸벅스