Collection Framework는 검색 기능을 강화시킨 TreeSet과 TreeMap을 제공하고있다.
이 컬렉션들은 이진 트리(binary tree)를 이용해서 계층적(tree) 구조를 가지면서 객체를 저장한다.
Collection Framework 자료
[JAVA 기본/java2] - [java2] #17 - Collection Framework(Set/List/Map), Iterator
[java2] #17 - Collection Framework(Set/List/Map), Iterator
컬렉션 프레임 워크 컬렉션 프레임 워크란 데이터를 저장하는 클래스들을 표준화 한 설계이며 아래 그림과 같이 데이터를 저장하는 구조에 따라 3가지 인터페이스로 구성된다. Set, List, Map은 데
yoonddo.tistory.com
이진 트리 구조 (binary tree)
여러개의 노드가 트리 형태로 연결된 구조로, 루트 노드라고 불리는 하나의 노드에서부터 시작해 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다. 첫번째로 저장되는 값은 루트 노드가 되고, 두번째 부터는 값의 크기를 비교해 트리를 만들며 내려간다. 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다.
-> 이진 트리가 범위 검색을 쉽게 할 수 있는 이유는 값들이 정렬되어 있어 그룹핑이 쉽기 때문이다
TreeSet
이진 트리를 기반으로한 Set 컬렉션이다. 객체를 저장하면 자동으로 정렬되는데 부모값과 비교해서 낮은 것은 왼쪽 자식 노드에, 높은 것은 오른쪽 자식 노드에 저장한다.
// 생성시 저장할 객체 타입을 파라미터로 표기하고,
// 기본 생성자를 호출하면 된다
TreeSet<E> treeSet = new TreeSet<E>();
리턴 타입 | 메서드 | 설명 |
E | first() | 제일 낮은(작은) 객체 리턴 |
last() | 제일 높은(큰) 객체 리턴 | |
lower(E e) | 주어진 객체보다 바로 아래(작은) 객체 리턴 / 주어진 객체보다 가장 가까운 미만 값 리턴 |
|
higher(E e) | 주어진 객체보다 바로 위 객체를 리턴 / 주어진 객체보다 가장 가까운 초과 값 리턴 |
|
floor(E e) | 주어진 객체와 동등한 객체가 있다면 리턴, 만약 없다면 주어진 객체의 바로 아래 객체를 리턴 |
|
ceiling(E e) | 주어진 객체와 동등한 객체가 있다면 리턴, 만약 없다면 주어진 객체의 바로 위 객체를 리턴 |
|
pollFirst() | 제일 낮은 객체를 꺼내오고 제거한다. | |
pollLast() | 제일 높은 객체를 꺼내오고 제거한다. |
사용 예제
TreeSet<Integer> num = new TreeSet<Integer>();
// set 값 넣기
num.add(10);
num.add(8);
num.add(9);
num.add(20);
num.add(45);
num.add(0);
int number = num.first();
System.out.println("제일 낮은 객체(숫자)를 리턴 : " + number);
System.out.println("---------------------------");
number = num.last();
System.out.println("제일 높은 객체(숫자)를 리턴 : " + number);
System.out.println("---------------------------");
number = num.lower(30);
System.out.println("30점보다 작은 점수 중 가장 가까운 수를 리턴 : " + number);
// 만약 가장 작은수를 lower로 넣으면 에러가 난다.
//number = num.lower(0);
//System.out.println("0점 보다 작은 값 있어? : " + number);
System.out.println("----------------------------");
number = num.higher(20);
System.out.println("20점보다 높은 점수 : " + number);
// 만약에 가장 높은 수를 higher에 넣으면 에러가 난다.
//number = num.higher(45);
//System.out.println("45점보다 높은 점수 있어? : " + number);
System.out.println("----------------------------");
number = num.floor(20);
System.out.println("20이랑 똑같은 수가 있으면 그거 가져오고, 아니면 바로 아래의 값 리턴 : " + number);
System.out.println("----------------------------");
number = num.ceiling(0);
System.out.println("0이랑 똑같은 수 있으면 그거 가져오고, 아니면 바로 위 값 리턴 : " + number);
System.out.println("----------------------------");
System.out.println("현재 num의 사이즈 : " + num.size());
number = num.pollFirst();
System.out.println("가장 높은 값을 읽고 제거.제거한 값 : " + number);
System.out.println("제거하고 난 뒤 num 사이즈 : " + num.size());
결과
정렬 메서드
리턴 타입 | 메서드 | 설명 |
Iterator<E> | descendingIterator() | 내림차순으로 정렬된 Iterator를 리턴 |
NavigableSet<E> | descendingSet() | 내림차순으로 정렬된 NavigableSet을 반환 |
사용 예제
TreeSet<Integer> num = new TreeSet<Integer>();
// set 값 넣기
num.add(10);
num.add(8);
num.add(9);
num.add(20);
num.add(45);
num.add(0);
// 내림차순으로 출력 1
Iterator<Integer> it = num.descendingIterator();
while(it.hasNext()) {
Integer ss = it.next();
System.out.println(ss);
}
System.out.println("-----------");
// 내림차순으로 출력 2
NavigableSet<Integer> ds = num.descendingSet();
it = ds.iterator();
while(it.hasNext()) {
Integer ss = it.next();
System.out.println(ss);
}
System.out.println("-----------");
// 올림차순은 내림차순을 두번 하면 된다.
ds = ds.descendingSet();
it = ds.iterator();
while(it.hasNext()) {
Integer ss = it.next();
System.out.println(ss);
}
System.out.println("-----------");
결과
범위 메서드
리턴 타입 | 메서드 | 설명 |
NavigableSet<E> | headSet( E toElement, boolean inclusive ) |
주어진 객체보다 낮은 객체들을 NavigableSet으로 리턴, 주어진 객체 포함 여부는 두 번째 매개값에 따라 달라진다. |
tailSet( E fromElement, boolean inclusive ) |
주어진 객체보다 높은 객체들을 NavigableSet으로 리턴, 주어진 객체 포함 여부는 두 번째 매개값에 따라 달라진다. |
사용 예제
TreeSet<Integer> ts = new TreeSet<Integer>();
ts.add(100);
ts.add(95);
ts.add(85);
ts.add(90);
ts.add(80);
// x < 90
// 90 보다 작은 객체 모두 리턴
SortedSet<Integer> a90 = ts.headSet(90);
Iterator<Integer> it = a90.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// x <= 90
// 90 도 포함해서 90보다 작은 객체들 모두 리턴
SortedSet<Integer> b90 = ts.headSet(90, true);
it = b90.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 < x
SortedSet<Integer> a85 = ts.tailSet(85);
it = a85.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 <= x
SortedSet<Integer> b85 = ts.tailSet(85,true);
it = b85.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 < x < 95
SortedSet<Integer> a8595 = ts.subSet(85, false, 95, false);
it = a8595.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
// 85 <= x <= 95
SortedSet<Integer> b8595 = ts.subSet(85, true, 95, true);
it = b8595.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println("\n--------------------------");
결과
TreeMap
TreeSet과의 차이점은 키와 값이 저장된 Map.Entry를 저장한다는 점이다.
TreeMap에 객체를 저장하면 자동으로 정렬되는데, 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에, 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장한다.
다음은 TreeMap이 가지고 있는 검색 관련 메소드들이다
검색 메서드
리턴 타입 | 메서드 | 설명 |
Map.Entry<K, V> | firstEntry() | 제일 낮은 Map.Entry를 리턴 |
lastEntry() | 제일 높은 Map.Entry를 리턴 | |
lowerEntry(K key) | 주어진 키보다 바로 아래 Map.Entry를 리턴 | |
higherEntry(K key) | 주어진 키보다 바로 위 Map.Entry를 리턴 | |
floorEntry(K key) | 주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 주어진 키 바로 아래 Map.Entry를 리턴 |
|
ceilingEntry(K key) | 주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 주어진 키 바로 위 Map.Entry를 리턴 |
|
pollFirstEntry() | 제일 낮은 Map.Entry를 꺼내오고 컬렉션에서 제거 | |
pollLastEntry() | 제일 높은 Map.Entry를 꺼내오고 컬렉션에서 제거 |
사용 예제
값 입력은 .put
new Integer(10) == int 10
// 키로 점수
// 값으로 이름
TreeMap<Integer, String> scores = new TreeMap<Integer, String>();
// TreeMap은 값 넣어줄때 put을 사용한다.
// 값은 중복될 수 있지만, 키는 중복되면 안된다.
scores.put(new Integer(87), "홍길동");
scores.put(new Integer(98), "이동수");
scores.put(new Integer(75), "박길순");
scores.put(new Integer(95), "신용권");
scores.put(new Integer(80), "김자바");
// firstEntry
// 제일 낮은 Map.Entry를 리턴
Entry<Integer, String> result1 = scores.firstEntry();
System.out.println("가장 낮은 점수 : " + result1.getKey() + "점\t\t학생명 : " + result1.getValue());
// lastEntry()
// 제일 높은 Map.Entry를 리턴
Entry<Integer, String> result2 = scores.lastEntry();
System.out.println("가장 높은 점수 : " + result2.getKey() + "점\t\t학생명 : " + result2.getValue());
// lowerEntry(K Key)
// 주어진 키보다 바로 아래 Map.Entry를 리턴
// x < 90
Entry<Integer, String> result3 = scores.lowerEntry(90);
System.out.println("90 보다 바로 아래 점수 : " + result3.getKey() + "점\t학생명 : " + result3.getValue());
// higherEntry(K Key)
// 주어진 키보다 바로 위 Map.Entry를 리턴
// x > 80
Entry<Integer, String> result4 = scores.higherEntry(80);
System.out.println("80보다 바로 위 점수 : " + result4.getKey() + "점\t학생명 : " + result4.getValue());
// floorEntry(K Key)
// 주어진 키와 동등한 키 있으면 해당 Map.Entry를 리턴, 없다면 바로 아래의 Map.Entry리턴
// x <= 90
Entry<Integer, String> result5 = scores.floorEntry(90);
System.out.println("x <= 90 : " + result5.getKey() + "점\t\t학생명 : " + result5.getValue());
// ceilingEntry(K Key)
// 주어진 키와 동등한 키 있으면 해당 Map.Entry리턴 없다면 바로 위 Map.Entry 리턴
// x >= 80
Entry<Integer, String> result6 = scores.ceilingEntry(90);
System.out.println("x >= 90 : " + result6.getKey() + "점\t\t학생명 : " + result6.getValue());
결과
정렬 메서드
리턴 타입 | 메서드 | 설명 |
NavigableSet<K> | descendingKeySet() | 내림차순으로 정렬된 NavigableSet을 리턴 |
NavigableMap<K, V> | descendingMap() | 내림차순으로 정렬된 Map.Entry의 NavigableMap을 리턴 |
사용 예제
TreeMap<Integer, String> scores = new TreeMap<Integer, String>();
scores.put(new Integer(87), "홍길동");
scores.put(new Integer(98), "이동수");
scores.put(new Integer(75), "박길순");
scores.put(new Integer(95), "신용권");
scores.put(new Integer(80), "김자바");
// 키값으로 내림차순해서 출력하는 코드 1
NavigableMap<Integer, String> deMap = scores.descendingMap();
Set<Map.Entry<Integer, String>> des = deMap.entrySet();
for (Entry<Integer, String> entry : des) {
System.out.println("학생 : " + entry.getValue() + "\t" + entry.getKey() + "점");
}
System.out.println();
// 키값으로 내림차순해서 출력하는 코드 2
NavigableSet<Integer> keyset = scores.descendingKeySet();
Iterator<Integer> it = keyset.iterator();
while (it.hasNext()) {
Integer key = it.next();
String value = scores.get(key);
System.out.println("학생 : " + value + "\t" + key + "점");
}
System.out.println();
// 키값으로 올림차순해서 출력하는 코드 1
// descendingMap() 을 두 번 사용하면 올림차순이 된다
deMap = deMap.descendingMap();
des = deMap.entrySet();
for (Entry<Integer, String> entry : des) {
System.out.println("학생 : " + entry.getValue() + "\t" + entry.getKey() + "점");
}
System.out.println();
결과
범위 검색 메서드
리턴 타입 | 메서드 | 설명 |
Navigable Map<K, V> |
headMap( K toKey, boolean inclusive ) |
주어진 키보다 낮은 Map.Entry들을 NavigableMap으로 리턴한다. 주어진 키의 Map.Entry 포함 여부는 두 번째 매개값에 따라 달라진다. |
tailMap( K tfromKey, boolean inclusive ) |
주어진 키보다 높은 Map.Entry들을 NavigableMap으로 리턴한다. 주어진 키의 Map.Entry 포함 여부는 두 번째 매개값에 따라 달라진다. |
|
subMap( K toKey, boolean inclusive, K fromKey, boolean inclusive ) |
시작과 끝으로 주어진 키 사이의 Map.Entry들을 NavigableMap 컬렉션으로 리턴한다. 시작과 끝 키의 Map.Entry 포함 여부는 두 번째 매개값에 따라 달라진다. |
실행 예제
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
public class TreeMapExample3 {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();
treeMap.put("apple", 10);
treeMap.put("forever", 60);
treeMap.put("description", 40);
treeMap.put("ever", 50);
treeMap.put("zoo", 10);
treeMap.put("base", 20);
treeMap.put("guess", 70);
treeMap.put("cherry", 30);
System.out.println("[c-f 사이의 단어 검색]");
NavigableMap<String, Integer> rangeMap = treeMap.subMap("c", true, "f", true);
for (Map.Entry<String, Integer> entry : rangeMap.entrySet()) {
System.out.println(entry.getKey() + "-" + entry.getValue() + "페이지");
}
}
}
결과
Comparable과 Comparator
1. Comparable
- TreeSet의 객체와 TreeMap의 키는 저장과 동시에 자동 오름차순 정렬된다
- 숫자타입일 경우 값으로, 문자열 타입일 경우 유니코드로 정렬 - TreeSet과 TreeMap은 정렬을 위해 java.lang.Comparable 구현 객체를 요구한다
(implements Comparable 하라는 뜻)
Integer, Double, String 모두 Comparable 인터페이스 구현하고 있다. - 사용자 정의 클래스도 Comparable을 구현한다면 자동 정렬이 가능하다.
Comparable에는 compareTo()메소드가 정의 되어 있기 때문에 사용자 정의 클래스에서는 이 메소드를
오버라이딩하여 다음과 같이 리턴 값을 만들어 내야 한다.
리턴 타입 | 메서드 | 설명 |
int | compareTo(T o) | 주어진 객체와 같으면 0 리턴 주어진 객체보다 작으면 음수 리턴 주어진 객체보다 크면 양수 리턴 |
사용 예제
package com.koreait.collectiontTest;
import java.util.Iterator;
import java.util.TreeSet;
public class TreeMapCompare {
public static void main(String[] args) {
// 트리로 달아줄 것이다 Person이라는 클래스를
TreeSet<Person1> treeSet = new TreeSet<Person1>();
// 트리에 노드로 달것이다 = 자료를 트리에 달아주기
treeSet.add(new Person1("홍길동", 45));
treeSet.add(new Person1("김자바", 25));
treeSet.add(new Person1("박지원", 31));
// 출력해보기
// index로 출력할 수 없기 때문에 Iterator사용
Iterator<Person1> it = treeSet.iterator();
while(it.hasNext()) {
Person1 p = it.next();
System.out.println(p.name + " : " + p.age);
}
System.out.println("--------------------------------");
// 트리는 저장과 동시에 자동 오름차순으로 정렬되는데
// 내림차순으로 하고 싶다면 Person 의 비교 혹은 리턴값을 반대로 바꾸면 된다
TreeSet<Person1> treeSet2 = new TreeSet<Person1>();
treeSet2.add(new Person1("홍길동", 45));
treeSet2.add(new Person1("김자바", 25));
treeSet2.add(new Person1("박지원", 31));
Iterator<Person1> it2 = treeSet2.iterator();
while(it2.hasNext()) {
Person1 p = it2.next();
System.out.println(p.name + " : " + p.age);
}
System.out.println("--------------------------------");
// 나이순으로 내림차순 정렬하고
// 나이가 같으면 이름으로 오름차순 정렬하기
TreeSet<Person2> treeSet3 = new TreeSet<Person2>();
treeSet3.add(new Person2("홍길동", 45));
treeSet3.add(new Person2("김자바", 25));
treeSet3.add(new Person2("박지원", 31));
treeSet3.add(new Person2("고길동", 45));
treeSet3.add(new Person2("이이것", 25));
treeSet3.add(new Person2("김둘리", 31));
Iterator<Person2> it3 = treeSet3.iterator();
while(it3.hasNext()) {
Person2 p = it3.next();
System.out.println(p.name + " : " + p.age);
}
System.out.println("--------------------------------");
}
}
class Person1 implements Comparable<Person1> {
public String name;
public int age;
public Person1(String name, int age) {
this.name = name;
this.age = age;
}
// 비교 기준을 정의하는 메소드
// 1. 비교자료1 < 비교자료 2 ==> 음수
// 2. 비교자료1 == 비교자료2 ==> 0
// 3. 비교자료1 > 비교자료 2 ==> 양수
// 저장된 나이와 새로 들어온 나이를 비교해서 트리 달기
@Override
public int compareTo(Person1 o) {
if(age < o.age) {
return -1;
} else if(age == o.age) {
return 0;
} else {
return 1;
}
}
}
class Person2 implements Comparable<Person2> {
public String name;
public int age;
public Person2(String name, int age) {
this.name = name;
this.age = age;
}
// 이름을 내림차순으로
@Override
public int compareTo(Person2 o) {
if(name.compareTo(o.name) > 0) {
return -1;
} else if(name.compareTo(o.name) == 0) {
return 0;
} else {
return 1;
}
}
}
class Person3 implements Comparable<Person3>{
public String name;
public int age;
public Person3(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person3 o) {
if(age < o.age) {
return 1;
} else if(age == o.age && name.compareTo(o.name) > 0) {
return 1;
} else if(age == o.age && name.compareTo(o.name) == 0) {
return 0;
} else {
return -1;
}
}
}
결과
2. Comparator 정렬자
- TreeSet의 객체와 TreeMap의 키가 Comparable을 구현하고 있지 않을 경우에는 저장하는 순간 ClassCastException이 발생한다.
- TreeSet 또는 TreeMap 생성자의 매개값으로 정렬자(Comparator)를 제공하면 Comparable 비구현 객체도
정렬시킬 수 있다.
TreeSet<E> treeSet = new TreeSet<E>( new AscendingComparator() );
TreeMap<K, V> treeMap = new TreeMap<K, V>( new DescendingComparator() );
Comparator 인터페이스 정의 메서드
리턴 타입 | 메서드 | 설명 |
int | compareTo(T o1, T o2) | o1과 o2가 동등하면 0 리턴 o1이 o2보다 앞에 오게 하려면 음수 리턴 o1이 o2보다 뒤에 오게 하려면 양수 리턴 |
사용 예제
정렬자를 사용해 내림차순, 올림차순으로 정렬
package com.koreait.collectiontTest;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
public class DescendingComparator {
public static void main(String[] args) {
// Fruit에 만들어 주지 않고
// 아예 따로 비교 클래스를 만드는 방법
TreeSet<Fruit> treeSet = new TreeSet(new DescendingComparator1());
treeSet.add(new Fruit("포도", 3000));
treeSet.add(new Fruit("수박", 10000));
treeSet.add(new Fruit("딸기", 6000));
treeSet.add(new Fruit("바나나", 4000));
treeSet.add(new Fruit("체리", 5000));
treeSet.add(new Fruit("수박", 7000));
// 가격을 내림차순으로 정렬
Iterator<Fruit> it = treeSet.iterator();
while(it.hasNext()) {
Fruit fruit = it.next();
System.out.println(fruit.name + "\t" + fruit.price);
}
System.out.println("-------------------------");
// 과일명으로 오름차순 정렬
TreeSet<Fruit> treeSet1 = new TreeSet(new DescendingComparator2());
treeSet1.add(new Fruit("포도", 3000));
treeSet1.add(new Fruit("수박", 10000));
treeSet1.add(new Fruit("딸기", 6000));
treeSet1.add(new Fruit("바나나", 4000));
treeSet1.add(new Fruit("체리", 5000));
// set계열이기때문에(이름기준) 중복은 달릴 수 없다.
// treeSet1.add(new Fruit("수박", 7000));
Iterator<Fruit> it2 = treeSet1.iterator();
while (it2.hasNext()) {
Fruit fruit1 = it2.next();
System.out.println(fruit1.name + "\t" + fruit1.price);
}
System.out.println("-------------------------");
// 익명 구현 객체로
TreeSet<Fruit> treeSet2 = new TreeSet<Fruit>(new Comparator<Fruit>() {
@Override
public int compare(Fruit o1, Fruit o2) {
// 근데 어차피 중복이 안들어가는데 이렇게 이중으로 하는게 의미가 있나..?
if(o1.price < o2.price) {
return -1;
} else if(o1.price == o2.price && o1.name.compareTo(o2.name) < 0) {
return 0;
} else if(o1.price == o2.price && o1.name.compareTo(o2.name) > 0) {
return 0;
} else {
return 1;
}
}
});
treeSet2.add(new Fruit("포도", 3000));
treeSet2.add(new Fruit("수박", 10000));
treeSet2.add(new Fruit("딸기", 6000));
treeSet2.add(new Fruit("바나나", 4000));
treeSet2.add(new Fruit("체리", 5000));
// set계열이기때문에 중복은 달릴 수 없다.
// treeSet1.add(new Fruit("수박", 7000));
Iterator<Fruit> it3 = treeSet2.iterator();
while (it3.hasNext()) {
Fruit fruit2 = it3.next();
System.out.println(fruit2.name + "\t" + fruit2.price);
}
System.out.println("-------------------------");
}
}
// DescendingComparator<비교 대상자>
class DescendingComparator1 implements Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
// 가격으로 내림차순
if (o1.price < o2.price) {
return 1;
} else if (o1.price == o2.price) {
return 0;
} else {
return -1;
}
}
}
class DescendingComparator2 implements Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
// 과일명 오름차순
if (o1.name.compareTo(o2.name) > 0) {
return 1;
} else if (o1.name.compareTo(o2.name) == 0) {
return 0;
} else {
return -1;
}
}
}
class Fruit {
String name;
int price;
public Fruit(String name, int price) {
this.name = name;
this.price = price;
}
}
결과
사진, 내용 참고 출처
'JAVA > JAVA2' 카테고리의 다른 글
[JAVA] JDBC : DB 연결하기 (1) | 2023.11.11 |
---|---|
[java2] #40 - Generic (제네릭) (0) | 2022.11.30 |
[java2] #38 - Templete Method (0) | 2022.11.24 |
[java2] #37 - extends, Override, super (0) | 2022.11.24 |
[java2] #36 - PrintWriter (Text File Write Test) (0) | 2022.11.23 |