[Java] 컬렉션 프레임웍 (5) - HashSet, TreeSet

HashSet

HashSet과 TreeSet은 이름 그대로 Set인터페이스를 구현하였기 때문에 순서가 없고 중복을 허용하지 않는다.

일반적으로는 HashSet을 사용하는 것이 가장 일반적이다.

또한, 순서를 유지하려면 LinkedHashSet클래스를 사용하면 된다.

TreeSet은 범위 검색과 정렬에 유리한 컬렉션 클래스이다.

그렇기에 HashSet보다 데이터 추가나 삭제에 시간이 더 소요된다.

---

HashSet의 주요 메서드

 

생성자

int initialCapacity는 HashSet의 초기 용량을 지정해주는 것이다.

float loadFactor은 언제 HashSet의 용량을 두배 증가할지 지정해주는 것이다.

예를 들어 loadFactor에 0.8을 입력하면 HashSet의 용량이 80프로 차면 용량이 두배 증가하는 것이다.

 

추가, 삭제

add(Object o)는 추가 , remove(Object o)는 삭제 void clear()은 모두 삭제이다.

addAll(Collection c)는 합집합, removeAll(Collection c)는 차집합, retainAll(Collection c)는 교집합이다.

 

기타

contains(Object o)는 o라는 객체가 Set에 포함되어 있는지 확인한다.

boolean containsAll(Collection c)는 컬렉션에 담긴 여러 가지 객체가 모두 Set에 포함되어 있는지 확인한다.

Iterator은 컬렉션 접근 인터페이스로 가지고 있다.

[Java]컬렉션 프레임웍 (4) - 컬렉션 접근 인터페이스, Arrays, Comparator와 Comparable

 

isEmpty()는 비어있는지 확인한다. int size()는 저장되어있는 개수를 반환한다.

Object[] toArray()는 Set에 저장되어있는 객체를 객체 배열로 반환한다.

---

HashSet의 특징

HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 먼저 확인한다. (중복 X)

같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.

그렇기에 boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출한다.

예를 들어 Person이라는 객체를 add(Person)을 통해 저장을 한다면,

Person객체의 equals()와 hashCode()를 호출하는 것이다.

하지만 Person에는 equals()와 hashCode()가 없다.

그렇기에 모든 클래스의 최고 조상인 Object클래스의 equals()와 hashCode()를 호출하게 된다.

하지만, equals()와 hashCode()를 오버 라이딩하지 않으면 HashSet은 제대로 동작하지 않을 수도 있다.

그렇기에 equals()와 hashCode()가 오버 라이딩되어 있어야 한다.

이렇게 equals()는 iv를 비교하게 바꿔야 하며, hashCode는 return Object.hash()를 이용해서 변경해야 한다.

이해가 잘 되지 않는다면 더보기를 확인하면 좀 더 이해하기 편하다.

아래의 코드는 euqals()와 hashCode()를 오버라이딩 하지 않고, 객체를 추가하는 코드이다.

이렇게 Person이라는 객체를 HashSet에 두 번 추가하는데, 매개변수가 동일하게 추가한다.

그리고 HashSet을 출력하면 다음과 같다.

이렇게 abc는 중복을 허용하지 않기 때문에 제거가 되었지만, Person객체를 통해서 생성된 David:10은

중복이 제거되지 않고, 두 번 출력이 된 것이다.

이렇게 equals()와 hashCode()를 오버라이딩 하지 않으면 같은 매개변수의 객체를 계속 추가해도,

무엇을 비교해야 하는지 equals()와 hashCode()가 오버라이딩 되어있지 않기 때문에

오버라이딩을 해주어야 하는 것이다.

이렇게 class를 만들 때는 equals()와 hashCode()를 같이 오버라이딩 해주는게 일반적이다.

 

---

TreeSet

TreeSet은 이진 탐색 트리(binary search tree)로 구현되어 있으며, 범위 탐색과 정렬에 유리하다.

이진 트리 (binary tree)

이진 트리는 모든 노드가 최대 2개(0 ~ 2)의 하위 노드를 갖는다.

각 요소(node)가 나무(tree) 형태로 연결(LinkedList의 변형)되어 있어 TreeSet이다.

TreeNode의 클래스를 확인하면 저장하는 객체(element)와 오른쪽 왼쪽의 자식 노드들을 저장한다.

여기서 TreeSet은 이진 탐색 트리로 구현되어 있는데 이진 탐색 트리는 다음과 같다.

---

이진 탐색 트리 (binary search tree)

이진 탐색 트리는 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다.

이진 트리는 0 ~ 2개의 노드들을 가지고 있는 것을 이진 트리라고 하고,

그중에서도 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장하는 트리를 이진 탐색 트리라고 하는 것이다.

즉, 이진 트리의 한 종류인 것이다.

이진 트리에는 부모보다 큰 값이 오른쪽 작은 값이 왼쪽 이런 제약은 없다.

그냥 자식이 최대 2개이기만 하면 이진 트리이다.

이진 탐색 트리는 거기서 부모보다 작은 값 왼쪽, 큰 값은 오른쪽이라는 제약이 추가된 것이다.

이진 탐색 트리의 단점으로는 데이터가 많아질수록 추가, 삭제에 시간이 더 걸린다는 점이다.(비교 횟수 증가)

---

TreeSet의 주요 메서드

TreeSet의 메서드만 나열한 것이다.

( add(), size(), remove(), isEmpty() 등.. Collection 인터페이스의 메서드는 제외했다. )

 

 

TreeSet의 생성자 중 매개변수 타입이 Comparator가 있는 걸 확인할 수 있다.

TreeSet은 데이터가 저장될 때마다 앞의 데이터와 비교를 하면서 저장을 하는데,

그러한 비교 기준을 생성자 TreeSet(Comparator comp)를 통해 지정할 수 있다.