[JAVA] 17. 컬렉션 프레임워크 (Comparator, Comparable, HashSet, TreeSet)

 

1️⃣ Comparator와 Comparable

이전에 Arrays.sort()를 호출하면 알아서 정렬됐었는데 이건 사실 Comparator클래스의 Comparable 의 구현에 의해 정렬되었던 것이다. 

Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있으며, Comparable 을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들, 주로 Integer와 같은 wrapper 클래스와 String, Date, File 과 같은 것들이며 기본적으로 오름차순, 즉  작은값에서부터 큰 값의 순으로 정렬되도록 구현되어 있다. 

-> 그래서 Comparable 을 구현한 클래스는 정렬이 가능하다는 것을 의미한다. 

 

 

compare()와 compareTo()는 선언 형태와 이름만 살짝 다를 뿐 두 객체를 비교한다는 기능을 목적으로 고안된 것이다. 

compareTo()의 반환값은 int이지만 실제로는 비교하는 두 객체가 같으면 0, 비교하는 값보다 작으면 음수, 크면 양수를 반환하도록 구현해야 한다. 

마찬가지로 compare()도 객체를 비교해서 음수, 0, 양수 중의 하나를 반환하도록 구현해야 한다.

 

Comparable : 기본 정렬 기준을 구현하는데 사용 
Comparator : 기본 정렬 기준 외에 다른 기준으로 정렬하고자 할 때 사용 

-> Comparable 을 구현한 클래스들이 기본적으로 오름차순으로 정렬되어 있지만, 내림차순으로 정렬한다던가 아니면 다른 기준에 의해서 정렬되도록 하고 싶을 때 Comparator를 구현해서 정렬기준을 제공할 수 있다. 

 

-> Arrays.sort()는 배열을 정렬할 때, Comparator를 지정해주지 않으면 저장하는 객체 에 구현된 내용에 따라 정렬된다. (주로 Comparable 을 구현한 클래스 객체다.)

 

-> String의 Comparable 구현은 문자열이 사전 순으로 정렬되도록 작성되어 있다. 문자열의 오름차순 정렬은 공백, 숫자, 대문자, 소문자의 순으로 정렬되는 것을 의미한다. 

 

-> CASE_INSENSTIVE_ORDER 를 이용하면 문자열을 대소문자 구분없이 정렬할 수 있다.

 

-> String의 기본 정렬을 반대로 (내림차순)으로 하는 방법은 String에 구현된 compareTo()의 결과에 -1을 곱하기만 하면 된다. 

 

 

 

2️⃣ HashSet

HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이다. Set인터페이스의 특징대로 HashSet은 순서를 유지하지 않고 중복된 요소를 저장하지 않는다. 

 

HashSet에 새로운 요소를 추가할 때는 add 메서드나 addAll메서드를 사용하는데 만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다. 

 

ArrayList와 같이 List 인터페이스를 구현한 컬렉션과 달리 HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다. 

 

-> 결과에서 알 수 있듯이 중복된 값들은 저장되지 않은 것을 확인할 수 있다.

add 메서드는 객체를 추가할 때 HashSet에 이미 같은 객체가 있다면 중복으로 간주하고, 저장하지 않는다. 

그리고 작업이 실패했다는 것을 의미하기 위해 false를 반환한다.

 

이때 1은 두번 출력되었는데, 둘다 1이지만 하나는 String인스턴스이고, 하나는 Integer인스턴스로 서로 다른 객체이므로 중복으로 간주하지 않는다. 

 

Set을 구현한 컬렉션 클래스는 List를 구현한 컬렉션 클래스와 달리 순서를 유지하지 않기 때문에 저장한 순서와 다를 수 있다. 

 

 

-> Math.random()을 사용해서 실행할 때 마다 결과가 다르고, HashSet의 성질을 이용해서 로또번호를 만드는 예제이다. 

번호를 크기순으로 정렬하기 위해서는 Collection 클래스의 sort(List list)를 사용한다. 

sort메서드는 인자로 List 인터페이스 타입을 필요로 하기 때문에 LinkedList클래스의 생성자 LinkedList를 이용해서 HashSet에 저장된 객체들을 LinkedList에 담아서 처리했다. 

 

->  HashSet의 add 메서드는 새로운 요소를 추가하기 전에 기존에 저장된 요소와 같은 것인지 판별하기 위해 추가하려는 요소의 equals()와 hashcode()를 호출하기 때문에 equals()와 hashCode()를 목적에 맞게 오버라이딩 해야한다. 

(여기서는 이름과 나이가 같으면 같은 객체로 인식할 것이다.) 

 

Person클래스에서 두 인스턴스의 name과 age가 같으면 true 를 반환하도록 equals()를 오버라이딩 한다. 

그리고 hashCode()는 String클래스의 hashCode()를 이용해서 구현했다. 

String클래스의 hashCode()는 잘 구현되어 있기 때문에 이를 활용하면 간단히 처리할 수 있다. 

 

-> 이 예제는 두 개의 HashSet에 저장된 객체들을 비교해서 합집합, 교집합, 차집합을 구하는 방법을 보여준다, 

근데 retainAll, addAll, removeAll 메서드를 활용하면 좀 더 쉽게 합집합, 교집합, 차집합을 구할 수 있긴하다. 

 

 

3️⃣ TreeSet

TreeSet은 이진 검색 트리 (binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다. 

이진 검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조이다. 

 

TreeSet역시 Set인터페이스로 구현했기 때문에 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않아도 된다.

 

이진 트리는 링크드리스트처럼 여러 개의 node가 서로 연결된 구조로 각 노드에 최대 2개의 노드를 연결할 수 있으며, 루트라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다. 

 

이진 검색 트리는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다. 

컴퓨터는 알아서 값을 비교하지 못하기 때문에 TreeSet에 저장되는 객체가 Comparable을 구현하던가 아니면 TreeSet에게 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 하다. 그렇지 않으면 TreeSet에 객체를 저장할 때 예외가 발생한다. 

 

TreeSet은 정렬된상태를 유지하기 때문에 단일 값 검색과 범위검색(예를 들면 3과 7사이의 범위에 있는 값을 검색)할 때 빠르다. 

저장된 값의 개수에 비례해서 검색 시간이 증가하기는 하지만 값의 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교 횟수가 3~4번만 증가할 정도로 검색 효율이 뛰어난 자료구조이다. 

 

근데 트리는 데이터를 순차적으로 저장하는 것이 아니라 저장 위치를 찾아서 저장해야하고, 삭제하는 경우 트리의 일부를 재구성해야하므로 링크드 리스트보다 데이터의 추가/삭제 시간은 더 걸린다. 대신 배열이나 링크드 리스트에 비해 검색과 정렬기능이 더 뛰어나다.

 

 

이진 검색 트리 (binary search tree)
- 모든 노드는 최대 두개의 자식노드를 가질 수 있다. 
- 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식 노드의 값은 부모노드의 값보다 커야 한다. 
- 노드의 추가 삭제에 시간이 걸린다. (순차적으로 저장하지 않으므로) 
- 검색(범위 검색)과 정렬에 유리하다.
- 중복된 값을 저장하지 못한다.