Set
Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조. 어떤 요소도 같은Set내에 두 번 이상 나타날 수 없다.Set은 수학적 집합 개념을 구현한 것으로 순서를 보장하지 않고 특정 요소가 집합에 있는지 여부를 확인하는데 최적화.Set인터페이스는HashSet,LinkedHashSet,TreeSet등 다양한 구현 클래스를 가지고 있고 각 클래스는Set인터페이스를 구현한다.
HashSet
- 해시 자료 구조를 사용해 특정 순서 없이 저장
O(1)의 시간 복잡도- 데이터의 유일성만 중요하고, 순서가 중요하지 않는 경우 적합
hashCode(),equals()를 모두 사용
LinkedHashSet
- HashSet에 연결 리스트를 추가해 요소들의 순서 보장 즉 순서대로 조회 시 요소들이 추가된 순서대로 반환
O(1)의 시간 복잡도- 데이터의 유일성과 삽입 순서를 유지할때 적합
- 연결 링크를 유지해
HashSet보다 무거움.
TreeSet
TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용- 요소들은 정렬 순서로 저장
O(log n)의 시간복잡도- 데이터들을 정렬된 순서로 유지하며 집합의 특성을 유지하는 경우 사용 ex) 3,2,1 순서로 입력 → 1,2,3 출력
트리 구조
- 부모 노드와 자식 노드로 구성
- 가장 높은 조상은
루트(root) - 왼쪽 자손은 더 작은값, 오른쪽 자손은 더 큰 값 → 이진 탐색 트리
- 이진 탐색 트리 계산의 핵심은 한번에 절반을 날린다는 점
- 트리의 균형이 깨진 최악의 경우
O(n)의 성능이 나오는데, 동적으로 균형을 다시 맞추는 해결 방안이 있다. - 균형을 맞추는 AVL 트리, 레드-블랙 트리 같은 다양한 알고리즘이 존재한다.
- 따라서 최악의 경우에도
O(log n)의 성능 제공
이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점이다.
public class JavaSetMain {
public static void main(String[] args) {
run(new HashSet<String>()); //입력 순서 보장 안함 O(1)
run(new LinkedHashSet<String>()); //입력 순서 보장 O(1)
run(new TreeSet<String>()); //데이터 값을 기준으로 정렬 O(log N)
}
private static void run(Set<String> set) {
System.out.println("set = " + set.getClass());
set.add("C");
set.add("B");
set.add("A");
set.add("D");
set.add("1");
set.add("2");
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) { //다음 데이터 확인
System.out.print(iterator.next() + " "); //다음 데이터 반환
}
System.out.println();
}
}
//출력결과
set = class java.util.HashSet
A 1 B 2 C D
set = class java.util.LinkedHashSet
C B A D 1 2
set = class java.util.TreeSet
1 2 A B C D HashSet, LinkedHashSet, TreeSet 모두 Set 인터페이스를 구현하기 때문에 구현체를 변경하면서 실행할 수 있다.
iterator() → 컬렉션 반복 출력
HashSet 과 최적화
통계적으로 입력한 데이터 수가 배열의 크기를 75% 정도 넘어가면 해시 인덱스가 자주 충돌한다. 따라서 성능이 떨어진다.
자바의 HashSet은 데이터의 양이 배열의 크기 75%를 넘어가면 배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다. 해시 인덱스를 다시 적용하는데 시간이 걸리지만 해시 충돌이 줄어든다.
HashSet의 기본 크기 → 16
실무에서는
Set이 필요한 경우HashSet을 가장 많이 사용한다. 그리고 입력 순서 유지, 값 정렬의 필요에 따라서LinkedHashSet,TreeSet을 선택하자.
···