Chpt 11. 컬렉션 프레임워크 - 주제 4. Set 인터페이스와 구현 클래스들
1. Set 인터페이스의 메서드
메서드는 모두 Collection 인터페이스로부터 상속 받은 것들이다. 참고
2. 구현 클래스
핵심 구현 클래스는 노란색으로 강조돼 있다.
1) HashSet
[들어가기 앞서] 해싱 (Hashing)
해시 함수를 이용해 주어진 입력값들의 리턴값을 해시 테이블에 저장, 읽어오는 방식을 해싱이라고 한다. 해시 함수의 결과값은 index이고 이는 배열에 저장된다. 서로 다른 입력 값은 같은 해시 코드를 가질 수 있다. 따라서 해시 테이블은 배열과 LinkedList를 연결해 놓은 구조를 가진다.
Hash로 시작하는 컬렉션 클래스는 모두 이러한 형태로 데이터를 저장하고 있다.
해싱을 사용하면 많은 양의 데이터를 검색할 때 유리하다.
(1) 특징
중복을 허용하지 않기 때문에 add 또는 addAll과 같은 메서드로 중복 요소를 추가하려고 하면 false를 반환한다.
=> 중복을 쉽게 제거할 수 있다.
해싱
- 배열 + LinkedList의 데이터 구조
- 많은 양의 데이터를 검색할 때 유리하다.
[주의] HashSet에서 사용자 정의 타입으로 만든 요소를 추가(add 또는 addAll)할 때는 중복을 올바르게 판단하기 위해 equals와 hashCode (Objects.hash(iv들))를 반드시 오버라이딩 해야 한다.
| Set 구현 클래스 | HashSet | LinkedHashSet |
| 저장 순서 | X | O |
(2) 메서드 예제
참고
HashSetA.retainAll(HashSetB) - 교집합
HashSetA.addAll(HashSetB) - 합집합
HashSetA.removeAll(HashSetB) - 차집합
2) TreeSet
[들어가기 앞서] 이진 트리 & 이진 탐색 트리 (Binary search tree)
이진 트리는 부모 노드에서 최대 두 개의 자식 노드로 연결된 LinkedList의 변형된 구조이다. 최상단 노드를 루트라 하고 하나의 노드에서 제한 없이 확장해 나갈 수 있다.
이진 탐색 트리는 이진 트리에 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 값이 커지게 저장해야 한다는 조건을 추가한 것이다.
TreeSet은 이진 탐색 트리 형태로 데이터를 저장한 컬렉션 클래스이다. 그렇기 때문에 이진 탐색 트리 특징과 같은 특징을 갖는다.
(1) 장단점
(1) 최대 두 개의 자식 노드를 가질 수 있다.
(2) 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 값이 커진다.
(3) 중복 저장이 불가능하다.
(장) 범위 검색과 정렬에 유리하다.
(단) 반복해서 비교해야 하기 때문에 노드의 추가 또는 삭제에 많은 시간이 걸린다.
=> 트리 레벨 ↑ → 비교 횟수 ↑
[주의] boolean add(Object o) 호출 시
| 컬렉션 클래스 | HashSet | TreeSet |
| 중복 체크 메서드 | equals(), hashCode() 호출 | 저장된 객체가 Compareable 구현 아니면 Comparator를 생성자에 제공 |
(2) 메서드
참고
TreeSet(Comparator comp) // 비교 기준을 제공
(3) 예제
참고
트리 순회에는 전위, 후위, 중위(레벨) 순회(오름차순)가 있다.