[JAVA] Collection - Set (LinkedHashSet + HashSet)

이전 HashSet 포스팅 맨 아래에 적었던 것 처럼, HashSet은 정렬을 지원하지 않는다고 했는데 정렬이 되는 경우가 있었다. 그리고 왜 이렇게 되는 것인지에 대해 의문이 들었다. 그래서 이러한 궁금증에 알아볼 겸 오늘은 LinkedHashSet과 HashSet에 대해 알아보자! 

 

 

먼저 Set의 종류들에 대해 다시 한 번 살펴보자. 

 

HashSet

• 순서를 보장하지 않는다
• TreeSet보다 삽입, 삭제가 빠르다 (해시 테이블에 원소를 저장하여, 성능 면에서 가장 우수함) 
• 내부적으로 HashMap을 사용한다 

LinkedHashSet

• 입력된 순서를 보장한다 

TreeSet

• 이진 탐색 트리 (Red-Black Tree)를 기반으로 한다
• 따라서 값에 따라 순서가 결정된다 (오름차순 정렬)
• 데이터의 삽입 / 삭제에는 시간이 걸리지만 (HashSet보다 성능이 느림), 검색 / 정렬이 빠르다 

즉, 표로 간단하게 정리하면 다음과 같다. 

인터페이스	특징
HashSet	중복된 요소 저장 X, 순서 유지 X
LinkedHashSet	중복된 요소 저장X, 순서 유지 O
TreeSet	중복된 요소 저장 X, 순서 유지 X, 오름차순 정렬 O

 

 

---

그런데... HashSet이 왜 정렬(?)되는 것 처럼 보일까?

 

 

먼저 다음 경우를 살펴보자 

Set<Integer> set = new HashSet<>(Arrays.asList(1, 3, 6, 2, 4, 5));
        System.out.println(set); // [1, 2, 3, 4, 5, 6]

분명 HashSet은 정렬을 지원하지 않는다고 했는데, 정렬이 되고 있다...!

 

하지만 여기서 10 이상의 숫자를 넣어보자 

Set<Integer> set = new HashSet<>(Arrays.asList(1, 3, 6, 2, 4, 5, 10, 17));
        System.out.println(set); // [1, 17, 2, 3, 4, 5, 6, 10]

 

몇 번을 실행해도 위와 같은 순서로 나온다! 비록 위의 경우 정렬은 되지 않았지만, 랜덤 정렬이 아닌 것을 알 수 있다. 

 

그렇다면, 왜 17이 1의 오른편에 있을까? 

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
        }

이를 알기 위해서, HashSet의 add 메소드를 살펴보자.

 

HashSet은 내부적으로 HashMap으로 구현되어 있다.

final HashMap.Node<K,V>[] resize() {
    HashMap.Node<K,V>[] oldTab = table;
    /**
     * 생략
     * */
    
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    table = newTab;
    
    /**
     * 생략
     * */
    return newTab;
}

Key에는 저장하고 싶은 객체(데이터)를 저장하고, Value에는 dummy data를 넣어 둔다.

HashMap을 기본적으로 선언하면 디폴트 버킷 사이즈가 16이다. (DEAFULT_LOAD_FACTOR = 16) 

 

 

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

즉 16개의 Node<K, V>가 들어갈 수 있는 배열이 선언된 것이다.

key를 알맞은 버킷에 저장하기 위해 hashCode를 사용한다.
이 hashCode를 버킷 수로 나눈 나머지를 배열의 index로 사용한다.

 

그럼이제 HashMap의 put 메소드를 살펴보자!

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
	int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

아래 예시를 통해 더욱 쉽게 이해해보자. (16이상의 수 부터 16으로 나누는 이유는 버킷 수가 16이기 때문이다) 

	Set<Integer> set = new HashSet<>();
        set.add(6);
        set.add(5);
        set.add(9);
        set.add(3);
        set.add(17); // 17 % 16 = 1
        set.add(54); // 54 % 16 = 6
        set.add(23); // 23 % 16 = 7
        set.add(67); // 67 % 16 = 3
        set.add(7);
        set.add(16); // 16 % 16 = 0
        set.add(28); // 28 % 16 = 12
        
        System.out.println(set); // [16, 17, 3, 67, 5, 6, 54, 23, 7, 9, 28]

이미지 출처:https://velog.io/@ayoung0073/Java-HashSet%EA%B3%BC-LinkedHashSet-%EB%B9%84%EA%B5%90

이렇게 0~15까지는 정렬이 되는 것 '처럼' 보이지만, HashSet이 정렬된다는 것은 명백히 거짓이다!

HashSet은 정렬 되는 것이 아니라, 첫 번째 테이블 인덱스부터 순차적으로 탐색하면서 출력하는 것이다. 

 

그렇다면 LinkedHashSet의 경우에는 어떨까? 

 

LinkedHashSet

아래 경우를 비교해보자 

Set<String> set = new LinkedHashSet<String>(); // LinkedHashSet 선언
Set<String> set2 = new HashSet<String>(); // HashSet 선언

set.add("Hello2");
set.add("World3");
set.add("Hello1");
set.add("World4");

set2.add("Hello2");
set2.add("World3");
set2.add("Hello1");
set2.add("World4");

System.out.println(set); // [Hello2, World3, Hello1, World4]
System.out.println(set2); // [Hello1, World4, World3, Hello2]

HashSet과 달리, LinkedHashSet은 입력된 순서를 유지하고 있는 것을 볼 수 있다. 

 

위에서 했던 예제와 동일한 경우에도 입력 순서를 유지하고 있다.

Set<Integer> set = new HashSet<>(Arrays.asList(1, 3, 6, 2, 4, 5, 10, 17));
        System.out.println(set); // [1, 17, 2, 3, 4, 5, 6, 10]
        
Set<Integer> set2 = new LinkedHashSet<>(Arrays.asList(1, 3, 6, 2, 4, 5, 10, 17));
        System.out.println(set2); // [1, 3, 6, 2, 4, 5, 10, 17]

따라서 LinkedHashSet은 HashSet의 문제점인, 순서의 불명확성을 제거한 구현체라고 할 수 있다. 

 

---

[참고]

https://velog.io/@ayoung0073/Java-HashSet%EA%B3%BC-LinkedHashSet-%EB%B9%84%EA%B5%90

https://jwdeveloper.tistory.com/278