[DataStructure] LinkedHashSet (Java)

1. LinkedHashSet

Java11

Module java.base
Package java.util
Class LinkedHashSet<E>

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractSet<E>
            java.util.HashSet<E>
                java.util.LinkedHashSet<E>

Type Parameters:
E - the type of elements maintained by this set

All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, Set<E>

public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, Serializable

반복 순서를 예측할 수 있는 Set 인터페이스의 해시 테이블 및 연결 목록 구현. 이 구현은 모든 항목을 통해 실행되는 이중 연결 목록을 유지 관리한다는 점에서 HashSet과 다릅니다. 이 연결 목록은 요소가 집합에 삽입된 순서(삽입 순서)인 반복 순서를 정의합니다. 요소가 집합에 다시 삽입되더라도 삽입 순서는 영향을 받지 않습니다.

이 구현은 TreeSet과 관련된 비용 증가 없이 HashSet에서 제공하는 지정되지 않고 일반적으로 혼란스러운 순서에서 클라이언트를 보호합니다. 원본 집합의 구현에 관계없이 원본과 동일한 순서를 가진 집합의 복사본을 생성하는 데 사용할 수 있습니다.

  void foo(Set s) {
      Set copy = new LinkedHashSet(s);
      ...
  }

이 기술은 모듈이 입력 시 집합을 가져와 복사한 다음 나중에 복사본의 순서에 따라 순서가 결정되는 결과를 반환하는 경우에 특히 유용합니다. (고객은 일반적으로 제공된 것과 동일한 순서로 물건을 반품하는 것을 좋아합니다.)

이 클래스는 모든 선택적 Set 작업을 제공하고 null 요소를 허용합니다. HashSet과 마찬가지로 해시 함수가 버킷 간에 요소를 적절하게 분산한다고 가정하면 기본 작업(추가, 포함 및 제거)에 대해 일정한 시간 성능(O(1))을 제공합니다. 한 가지 예외를 제외하고 연결 목록을 유지 관리하는 추가 비용으로 인해 성능은 HashSet보다 약간 낮을 수 있습니다: LinkedHashSet에 대한 반복은 용량에 관계없이 Set의 크기에 비례하는 시간이 필요합니다. HashSet에 대한 반복은 용량에 비례하는 시간을 필요로 하는 더 많은 비용이 들 수 있습니다.

연결된 해시 집합에는 성능에 영향을 미치는 두 가지 매개변수가 있습니다. 초기 용량과 부하율입니다. HashSet과 같이 정확하게 정의됩니다. 그러나 이 클래스의 반복 시간은 용량의 영향을 받지 않기 때문에 초기 용량에 대해 지나치게 높은 값을 선택하는 데 따른 패널티는 HashSet보다 이 클래스에서 덜 심각합니다.

이 구현은 동기화되지 않습니다. 여러 스레드가 연결된 해시 집합에 동시에 액세스하고 스레드 중 하나 이상이 집합을 수정하는 경우 외부에서 동기화해야 합니다. 이것은 일반적으로 집합을 자연스럽게 캡슐화하는 일부 개체에서 동기화하여 수행됩니다. 그러한 개체가 없으면 Collections.synchronizedSet 메서드를 사용하여 집합을 "래핑"해야 합니다. 이는 세트에 대한 우발적인 동기화되지 않은 액세스를 방지하기 위해 생성 시 수행하는 것이 가장 좋습니다.

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

이 클래스의 반복자 메서드에 의해 반환된 반복자는 페일 패스트(fail-fast)입니다. 반복자가 생성된 후 언제든지 집합이 수정되면 반복자의 자체 제거 메서드를 통하지 않고 어떤 방식으로든 반복자는 ConcurrentModificationException을 throw합니다. 따라서 동시 수정에 직면하여 반복자는 미래의 불확실한 시간에 임의적이고 비결정적인 동작의 위험을 감수하기보다는 빠르고 깔끔하게 실패합니다.

iterator의 fail-fast 동작은 일반적으로 동기화되지 않은 동시 수정이 있는 경우 확실한 보장을 하는 것이 불가능하기 때문에 보장할 수 없습니다. Fail-fast iterator는 최선을 다해 ConcurrentModificationException을 발생시킵니다. 따라서 정확성을 위해 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다. 반복기의 빠른 실패 동작은 버그를 감지하는 데만 사용해야 합니다.

이 클래스는 Java Collections Framework의 멤버입니다.

Since:
1.4
See Also:
Object.hashCode(), Collection, Set, HashSet, TreeSet, Hashtable, Serialized Form