[Java] 32. Set

 

Set

#Java

자바가 제공하는 Set1 - HashSet, LinkedHashSet

자바의 Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나이다. Set 인터페이스는 중복을 허용하지 않는 유일한 요소의 집합을 나타낸다. 그러다보니, 특정 요소가 집합에 있는지 여부를 확인하는데 최적화되어 있다.

Set 인터페이스는 HashSet , LinkedHashSet , TreeSet 등의 여러 구현 클래스를 가지고 있으며, 각 클래스는 Set 인터페이스를 구현하며 각각의 특성을 가지고 있다.

주요 메서드

• add(E e) 지정된 요소를 세트에 추가한다(이미 존재하는 경우 추가하지 않음).
• addAll(Collection<? extends E> c) 지정된 컬렉션의 모든 요소를 세트에 추가한다.
• contains(Object o) 세트가 지정된 요소를 포함하고 있는지 여부를 반환한다.
• containsAll(Collection<?> c) 세트가 지정된 컬렉션의 모든 요소를 포함하고 있는지 여부를 반환한다.
• remove(Object o) 지정된 요소를 세트에서 제거한다.
• removeAll(Collection<?> c) 지정된 컬렉션에 포함된 요소를 세트에서 모두 제거한다.
• retainAll(Collection<?> c) 지정된 컬렉션에 포함된 요소만을 유지하고 나머지 요소는 세트에서 제거한다.
• clear() 세트에서 모든 요소를 제거한다.
• size() 세트에 있는 요소의 수를 반환한다.
• isEmpty() 세트가 비어 있는지 여부를 반환한다.
• iterator() 세트의 요소에 대한 반복자를 반환한다.
• toArray() 세트의 모든 요소를 배열로 반환한다.
• toArray(T[] a) 세트의 모든 요소를 지정된 배열로 반환한다.

HashSet

• 구현: 해시 자료 구조를 사용해서 요소를 저장한다.
• 순서: 요소들은 특정한 순서 없이 저장된다. 즉, 요소를 추가한 순서를 보장하지 않는다.
• 시간 복잡도: HashSet 의 주요 연산(추가, 삭제, 검색)은 평균적으로 O(1) 시간 복잡도를 가진다.
• 용도: 데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우에 적합하다.

앞서 우리가 구현한 MyHashSet 이 바로 HashSet 이다.

LinkedHashSet

• 구현: LinkedHashSet 은 HashSet 에 연결 리스트를 추가해서 요소들의 순서를 유지한다.
• 순서: 요소들은 추가된 순서대로 유지된다. 즉, 순서대로 조회 시 요소들이 추가된 순서대로 반환된다.
• 시간 복잡도: LinkedHashSet도 HashSet 과 마찬가지로 주요 연산에 대해 평균 O(1) 시간 복잡도를 가진다.
• 용도: 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다.
• 참고: 연결 링크를 유지해야 하기 때문에 HashSet 보다는 조금 더 무겁다.

• LinkedHashSet 은 HashSet 에 연결 링크만 추가한 것이다.
• HashSet 에 LinkedList 를 합친 것으로 이해하면 된다.
• head(first) 부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회할 수 있다.
  • 그림과는 다르게 실제로는 양방향으로 연결되어 있다.

TreeSet

• 구현: TreeSet 은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.
  • 이진 탐색 트리에 대해서는 자료구조 카테고리 게시글을 참고하자. 레드-블랙트리는 이진 탐색 트리를 개선한 버전이다. 기본 개념은 비슷하다.
• 순서: 요소들은 정렬된 순서로 저장된다. 순서의 기준은 비교자(Comparator )로 변경할 수 있다. 비교자는 뒤에서 다룬다.
• 시간 복잡도: 주요 연산들은 O(log n) 의 시간 복잡도를 가진다. 따라서 HashSet 보다는 느리다.
• 용도: 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다. 예를 들어, 범위 검색이나 정렬된 데이터가 필요한 경우에 유용하다. 참고로 입력된 순서가 아니라 데이터 값의 순서이다. 예를 들어 3, 1, 2 를 순서대로 입력해도 1, 2, 3 순서로 출력된다.

이진 탐색 트리와 성능
이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은 O(log O(n)이다. 하지만 트리의 균형이 맞지 않으면 최악의 경우 O(n)의 성능이 나온다. 한쪽으로 치우친 경우를 생각해보자.

이진 탐색 트리 개선
트리의 균형을 동적으로 맞추기 위해 AVL 트리, 레드-블랙 트리 같은 다양한 알고리즘이 존재한다.
자바의 TreeSet 은 레드-블랙 트리를 사용해서 균형을 지속해서 유지한다. 따라서 최악의 경우에도 O(log<br> n) 의 성능을 제공한다.

이진 탐색 트리 - 순회
이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점이다.
따라서 정렬된 순서로 데이터를 차례로 조회할 수 있다. (중위 순회)

중위 순회에 관한 자세한 내용은 자료구조 카테고리의 글을 참조하자.

Set 인터페이스 구현체에 따른 순회

private static void run(Set<String> set) {
	System.out.println("set = " + set.getClass());
	set.add("C");
	set.add("B");
	set.add("A");
	set.add("1");
	set.add("2");

	Iterator<String> iterator = set.iterator();
	while (iterator.hasNext()) {
		System.out.print(iterator.next() + " ");
	}
	System.out.println();
}

• iterator() 를 호출하면 컬렉션을 반복해서 출력할 수 있다.
  • iterator.hasNext() : 다음 데이터가 있는지 확인한다.
  • iterator.next() : 다음 데이터를 반환한다.

위 메서드에 구현체를 바꿔가면서 실행해보자. 앞서 설명했던 구현체의 특징들이 실행 결과로 나타난 것을 확인할 수 있다.

set = class java.util.HashSet
A 1 B 2 C
set = class java.util.LinkedHashSet
C B A 1 2
set = class java.util.TreeSet
1 2 A B C

참고 - TreeSet의 정렬 기준
TreeSet 을 사용할 때 데이터를 정렬하려면 크다, 작다라는 기준이 필요하다. 1, 2, 3이나 "A", "B", "C" 같은 기본 데이터는 크다 작다라는 기준이 명확하기 때문에 정렬할 수 있다. 하지만 우리가 직접 만든 Member 와 같은 객체는 크다 작다는 기준을 어떻게 알 수 있을까? 이런 기준을 제공하려면 Comparable , Comparator 인터페이스를 구현해야 한다. 이 부분은 뒤에서 설명한다.

자바 Set 최적화

자바 HashSet과 최적화

• 자바의 HashSet 은 우리가 직접 구현한 내용과 거의 같지만 최적화를 추가로 진행한다.
  • 데이터의 양이 배열 크기의 75%를 넘어가면 배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다.
  • 해시 인덱스를 다시 적용하는 시간이 걸리지만, 결과적으로 해시 충돌 가능성이 줄어든다.
  • 자바 HashSet 의 기본 크기는 16 이다.
  • 이 과정을 재해싱(rehashing)이라 한다.

정리
실무에서는 Set 이 필요한 경우 HashSet 을 가장 많이 사용한다고 한다. 그리고 입력 순서 유지, 값 정렬의 필요에 따라서LinkedHashSet , TreeSet 을 선택하면 된다.

참고) 김영한의 실전 자바 - 중급 2편