[JAVA] 컬렉션 프레임워크(2) 집합 Set | HashSet, TreeSet

집합(Set) 인터페이스

선형 구조로 저장되어 순서 정보가 저장되는 리스트와 비선형 구조인 집합은 달리 집합은 순서가 없어 인덱스 사용이 불가하다. 대신 객체 대상으로 반복자(Iterator)를 제공하여 조회할 수 있다. 집합은 데이터를 중복해서 저장할 수 없으며 널 값은 저장 가능하다.

값을 추가하거나 삭제할 때 해당 요소가 집합 내에 있는지 확인한 후 작업이 이뤄지기 때문에 속도가 리스트에 비해 느리다.

 

 

HashSet

HashSet은 객체를 저장하기 전 객체의 hashCode() 메서드를 호출하여 해시 코드를 얻은 다음 저장되어 있는 객체들의 해시 코드와 비교하여 중복을 피한다. 문자열을 저장하는 경우 같은 문자열을 갖는 String 객체는 동일한 객체로 간주되고 다른 문자열을 갖는 String 객체는 다른 객체로 간주되는데, 그 이유는 String 클래스가 hashColde()와 equals() 메서드를 재정의하여 같은 문자열의 경우 hashCode() 리턴값은 같게 equals() 리턴값은 true가 나오도록 했기 때문이다.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{

* 저장공간보다 값이 추가로 들어오면 가변적으로 공간을 늘리는데 이때 약 두배로 늘린다. 과부하가 발생할 수 있음으로 초기에 저장 용량을 정해주는것이 좋다.

* 생성 시 기본 capacity는 16, load factor은 0.75이다.

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

 

집합 생성

HashSet<Integer> set = new HashSet<>();
HashSet<Integer> set = new HashSet<Integer>();
HashSet<Integer> set = new HashSet<Integer>(10); // 초기 용량
HashSet<Integer> set = new HashSet<Integer>(10, 0.7f); // capacity, load factor 지정
HashSet<Integer> set = new HashSet<Integer>(Arrays.asList(1, 2, 3));

요소 추가

set.add(1);

요소 삭제

set.remove(1);
set.clear();

크기 구하기

int size = set.size();

반복자 순회

Iterator iter = set.iterator();
while(iter.hasNext()) {
    System.out.print(iter.next());
}

검색

boolean isContains = set.contains(1);

 

 

TreeSet

이진탐색트리 중 레드-블랙 트리(Red-Black Tree)로 구현되어 있다. 이진탐색트리의 경우 트리 높이가 h일때 수행 시간이 O(logh)로 높이만큼 시간이 걸린다. 트리가 한쪽으로 치우쳐저 높이가 높아지는 것을 방지하기 위해 데이터가 잘 분산되도록 한 것이 레드-블랙 트리이다. 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞춘다.

 

https://coding-factory.tistory.com/555

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{

** NavigableSet

NavigableSet은 SortedSet 인터페이스를 확장한 인터페이스이다.

트리를 이용하여 정렬된 상태를 저장하기 때문에 주어진 타겟을 위주로 다양한 연산이 가능하다

set.ceiling(1); // n 이상 중 최솟값
set.floor(1); // n 이하 중 최댓값
set.higher(3); // n 초과 중 최솟값
set.lower(3); // n 미만 중 최댓값

역방향 Iterator를 반환하는 descendingIterator() 메서드를 제공한다.

for (Iterator<Integer> iter = set.descendingIterator(); iter.hasNext(); ) {
  System.out.println(iter.next());
}

또한 descendingSet() 메서드를 이용하여 역순으로 정렬된 새로운 Set을 얻을 수 있다.

NavigableSet<Integer> descendSet = set.descendingSet();

 

** SortedXX, NavigableXX 트리 구조를 이용하는 다른 컬렉션(TreeMap)도 동일한 메서드를 갖는다.

 

집합 생성

TreeSet<Integer> set = new TreeSet<Integer>();
TreeSet<Integer> set = new TreeSet<>();
TreeSet<Integer> set = new TreeSet<Integer>(set);
TreeSet<Integer> set = new TreeSet<Integer>(Arrays.asList(1,2,3));

요소 추가

set.add(1);

요소 삭제

set.remove(1);
set.clear();

크기 구하기

int size = set.size();

전체 조회

Iterator iter = set.iterator();
while(iter.hasNext()) {
    System.out.println(iter.next());
}

특정 값 조회

set.first(); // 최솟값 출력
set.last(); // 최댓값 출력
set.higer(3); // 3보다 큰 데이터 중 최솟값 출력, 없으면 null
set.lower(3); // 3보다 작은 데이터 중 최댓값 출력, 없으면 null