java.util.Set(1) HashSet

이번에는 Set에 대해 간단히 정리하려 합니다.

 

 

먼저 Set의 자료구조를 살펴보면 다음과 같습니다.

 

1. Set에 들어오는 값(Key)의 중복을 허용하지 않는다.

2. 저장 순서를 유지하지 않는다.(물론 구현체에 따라 순서대로 뽑을 순 있다.)

 

Set을 구현한 구현체는 HashSet, TreeSet, LinkedHashSet, ConcurrentSkipListSet 등 다양하게 있으나 주로 사용하는 자료구조인 HashSet부터 정리해보려 합니다.

 

 

HashSet 클래스는 해시 알고리즘을 사용하기에 검색속도가 매우 빠르며 (O(1) 또는 거의 근접) 합니다.

또한 해시를 사용하기 위해 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장합니다.

HashMap 관련 정리 : https://duooo-story.tistory.com/19?category=881766

private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public HashSet() {
    this.map = new HashMap();
}

public HashSet(int initialCapacity, float loadFactor) {
    this.map = new HashMap(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    this.map = new HashMap(initialCapacity);
}

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    this.map = new LinkedHashMap(initialCapacity, loadFactor);
}

기본적으로 HashSet을 생성할 때, HashMap을 생성할때 지원해주는 생성자를 같이 지원해주고 있습니다.

 

 

그외에 우리가 자주 사용하는 iterator(key List 반환), size( 사이즈 조회), add(추가), contains(포함여부 확인).. 등 결국 this.map ( HashMap)을 사용하기에 기존 포스팅을 했던 HashMap연산을 살펴보면 동작을 확인할 수 있습니다.

public Iterator<E> iterator() {
    return this.map.keySet().iterator();
}

public int size() {
    return this.map.size();
}

public boolean isEmpty() {
    return this.map.isEmpty();
}

public boolean contains(Object o) {
    return this.map.containsKey(o);
}

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

public boolean remove(Object o) {
    return this.map.remove(o) == PRESENT;
}

public void clear() {
    this.map.clear();
}

 

기존 HashMap과 동일하기에 중복된 key를 넣기않기 위해서 HashCode,Equals를 구현해줘야하며, 빠른 집합을 구현하는 경우 HashSet을 사용할 수 있습니다.

간단하게 Time Complexity(시간복잡도)를 확인해보면 다음과 같습니다.

Add	O(1)
Contains	O(1), 1에 수렴하나 HashCode가 겹칠경우, 그 사이즈만큼 확인
remove	O(1), 1에 수렴하나 HashCode가 겹칠경우, 그 사이즈만큼 확인