LinkedHashSet

LinkedHashSet<E>

Set<E> 인터페이스를 구현한 구현 클래스이다. (HashSet의 자식 클래스, HashSet의 모든 기능 사용 가능)

입력 순서와 출력 순서는 동일하다. (단, 중복을 허용하지 않는다.)

// x
Set<E> set = new LinkedHashSet<>();

// o
HashSet<E> set = new LinkedHashSet<>();

어떻게 순서를 유지할까?

아래 내용은 전부 해당 링크의 내용을 복사했다.

[Java] LinkedHashSet, 이건 멀까?ASH84

기본적으로 앞서 애기한 HashSet 을 상속 받도록 되어 있고, 모든 생성자에는 별도의 인스턴스를 만드는 것이 아니라 부모(super()) 생성자를 초기화하는 방식으로 되어 있다.* 총 4개의 생성자*를 가지고 있는데 모두 아래와 같다.

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

public LinkedHashSet() {
    super(16, .75f, true);
}


public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

// HashSet의 생성자
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

생성자를 보면 알겠지만, 모두 부모 생성자를 호출하고 있다. 즉, HashSet의 생성자를 호출하고 있는 것이다. 특히, HashSet의 생성자중 5번째 패키지내에서만 호출할수 있는 생성자를 호출하고 있다.

LinkedHashSet   =>   HashSet   =>   LinkedHashMap

*즉, LinkedHashSet은 부모인 HashSet을 만들고 그리고 내부적으로 LinkedHashMap을 만들고 있다. *

HashSet의 구현과는 다른데,** 이중 링크드리스트(Double Linked List)를 유지**한다. 이 링크드리스트는 Iteration의 순서를 정하는데, Iteration의 순서는 LinkedHashSet에 삽입된 순서이다. 만약 하나의 element가 재 삽입되더라도 영향을 받지 않는다. 하나의 element 가 재삽입 된다면 s.add(e) 이런식으로 호출이 되는데, s.contains(e)가 true를 리턴하도록 되어 잇다. **HashSet과의 차이점 ** 가장 큰 차이는 입력한 순서대로 나온다는 점이다.

LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<Integer>();

for(int i =10; i>0; i--)
   linkedHashSet.add(i);
    
    
linkedHashSet.add(3);
linkedHashSet.add(311);
System.out.println(linkedHashSet.toString());
//[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 311]

LinkedHashSet.add()   =>   HashSet.add()   =>   LinkedHashMap.put()   =>   HashMap.put()

3을 나중에 넣었는데 위에서 언급한대로 중복되는 것은 삽입이 되지 않는다. 그리고 311을 넣었을때 정렬되지 않은채 제일 마지막에 삽입했기 때문에 제일 뒤에 있는것을 확인 할 수가 있다. 재 삽입되는 경우, 내부 코드가 어떻게 돌아가는지 보자. s.ad(e)를 호출하게 되면 부모인 HashSet의 add()가 호출되고 내부적으로 LinkedHashMap을 거져서 HashMap의 put() 함수로 연결되는 것을 볼수가 있다.(GrepCode) 즉, HashMap의 put() 함수를 통해서 element가 삽입되기 때문에 자연스럽게 중복제거가 된다.

정렬

HashSet의 CHOATIC Ordering 해결법 위에서 본것 처럼 HashSet은 이상한 정렬을 가진다. 이것은 자바 공식 문서에서도 Choatic ordering 이라고 말하고 있을 정도인데, HashSet은 정렬이 이해할수가 없고, LinkedHashSet은 입력한 순서대로 들어간다. 그러나 정렬을 해야할 경우가 생기기 때문에 정렬을 하려면 다음과 같이** TreeSet을 써서 이전 Set을 copy하는 동시에 정렬하면 된다. **

Set<Integer> sortedLinkedHashSet = new TreeSet<Integer>(linkedHashSet);
System.out.println(sortedLinkedHashSet.toString());

Set<Integer> sortedHashSet = new TreeSet<Integer>(hashSet);
System.out.println(sortedHashSet.toString());

성능문제

** 성능은 HashSet 보다 약간 떨어질 수 있는데 링크드리스트를 유지하는데 비용이 든다고 한다. 한가지 예외로는 LinkedHashSet의 Iteration 은 capacity(capacity 와 size 는 다르다. HashMap 정리 참고)에 상관없이 Set의 사이즈에 비례하는 시간이 필요하다고 한다. ** LinkedHashSet은 두가지 요소에 대해서 성능에 영향을 받는다 initial capacity와 load factor 인데 이것들이 성능에 영향을 주는 이유는 내부적으로 HashMap을 사용하기 때문이다. 주의할 점은 Iteration 은 capacity에 영향을 받는것이 아니라는 점이다. 그렇기 때문에 매우 높은 initial capacity를 줄 필요는 없다. **동기화 ** 동기화는 LinkedHashSet이 기본적으로 제공하지 않기 때문에 다음과 같이 synchronizedSet() 함수를 이용하면 된다.

Set s = Collections.synchronizedSet(new LinkedHashSet(...));