HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
📝
남득윤 학습 저장소/
자바 콜렉션
자바 콜렉션/
#️⃣
HashSet & TreeSet
#️⃣

HashSet & TreeSet

 

HashSet의 구현

 
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 기능을 제공할 수 있음 - 데코레이터 패턴
    • SynchronizedSet은 같은 Collections 클래스의 정적 클래스인 SynchronizedCollection 의 구현체임
    • SynchronizedCollection 는 내부적으로 Collection과 mutex의 필드를 가지면서 모든 collection api에 대한 기본 구현을 synchronized 키워드로 감싸는 api를 제공함
      •  
  • HashSet의 ierator 메소드는 fail-fast 한 iterator참조를 제공한다.
 
 

TreeSet의 구현

 
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 로 구현되어있음
 
 
TreeSet이
  • 관리하는 ordering은 compareTo 메소드에 의해 결정되며 항상 일정함
 
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();}
        }

		....
}
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!!!