HashSet & TreeSet

HashSet의 구현

• Hash Table (a HashMap instance)를 하나 가진 Set 인터페이스의 구현체임

• iteration에 대한 순서를 보장하지 않음

• nullelement를 가질 수 잇음

• element들이 bucket에 적절하게 나뉘어 있다면
• basic operations - add, remove, containsand size 에 O(1)의 퍼포머스를 제공함

• Iterate에 대한 시간 복잡도는 O(N+C) 임
• N : 전체 원소의 수
• C : bucket의 capacity
• Iterate가 중요하다면 capacity를 너무 크게 두거나 load factor를 너무 낮게 잡으면 안됨
 

• HashSet의 구현은 synchronized 되어 있지 않음
• synchronized 키워드를 직접 활용하거나
• Collections.synchronizedSet으로 생성단계에서 Set을 SynchronizedSet 으로 Warpping 하여 synchronization 기능을 제공할 수 있음 - 데코레이터 패턴

static class SynchronizedCollection<E> implements Collection<E>, Serializable {
    private static final longserialVersionUID= 3053995032091335093L;

    final Collection<E> c;  // Backing Collection
    final Object mutex;     // Object on which to synchronize

		public int size() {
            synchronized (mutex) {return c.size();}
        }

		....
}

• SynchronizedSet은 같은 Collections 클래스의 정적 클래스인 SynchronizedCollection 의 구현체임
• SynchronizedCollection 는 내부적으로 Collection과 mutex의 필드를 가지면서 모든 collection api에 대한 기본 구현을 synchronized 키워드로 감싸는 api를 제공함
 

• HashSet의 ierator 메소드는 fail-fast 한 iterator참조를 제공한다.

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

        hashSet.add(1);
        hashSet.add(2);

        Iterator<Integer> iterator = hashSet.iterator();
        iterator.forEachRemaining(x -> hashSet.add(-1));
    }


-> ConcurrentModificationException!!!

TreeSet의 구현

• navigable map (e.g. TreeMap)을 내부에 하나 가진 NaviagableSet의 구현체임
• NaviagableSet는 SortedSet의 확장된 인터페이스임

• 내부 elements들은 natural order (Comparable) 혹은 생성시 제공된 Comparator를 활용하여 정렬됨

• basic operation - add, remove and contains에 대한 log(n)의 시간복잡도를 보장함

• 순서 가 있기 때문에 from, to 와 같은 파라미터를 통해 부분집합을 제공하는 api를 가짐

• Red-Black Tree 로 구현되어있음

• 관리하는 ordering은 compareTo 메소드에 의해 결정되며 항상 일정함