[Java] 컬렉션 프레임워크 - 검색 기능을 강화시킨 컬렉션

컬렉션 프레임 워크는 여러 절로 구성되어 있습니다.

Intro

List 컬렉션

Set 컬렉션

Map 컬렉션

검색 기능을 강화시킨 컬렉션

LIFO와 FIFO 컬렉션

동기화 & 병렬처리를 위한 컬렉션

---

5. 검색기능을 강화시킨 컬렉션

 컬렉션 프레임워크는 검색 기능을 강화시킨 TreeSet과 TreeMap을 제공하고 있습니다.

 이 컬렉션들은 이진 트리(binary tree)를 이용해서 계층적 구조(Tree 구조)를 가지면서 객체를 저장합니다.

 5.1 TreeSet

  TreeSet은 이진 트리를 기반으로한 Set 컬렉션입니다.

  하나의 노드는 노드 값인 value와 왼쪽과 오른쪽 자식 노드를 참조하기 위한 두 개의 변수로 구성됩니다.

  TreeSet에 객체를 저장하면 자동으로 정렬되는데 부모값과 비교해서 낮은 것은 왼쪽 노드에, 높은 것은 오른쪽 노드에 저장합니다.

 

 

 

  TreeSet을 생성하기 위해서는 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 됩니다.

TreeSet<E> treeSet = new TreeSet<E>();
 
 
 

  Set 인터페이스 타입 변수에 대입해도 되지만 TreeSet 클래스 타입으로 대입한 이유는 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위해서입니다. 다음은 TreeSet이 가지고 있는 검색 관련 메소드들입니다.

  다음 예제는 점수를 무작위로 저장하고 특정 점수를 찾는 방법을 보여줍니다.

  * TreeSetExam1.java

 
package set;
 
import java.util.TreeSet;
 
public class TreeSetExam1 {
 
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<Integer>();
 
        for (int i = 0; i < 5; i++) {
            treeSet.add(new Integer((int) Math.round(Math.random() * 50 + 50)));
        }
 
        Integer score = null;
 
        score = treeSet.first();
        System.out.println("가장 낮은 점수: " + score);
 
        score = treeSet.last();
        System.out.println("가장 높은 점수: " + score);
 
        score = treeSet.lower(new Integer(90));
        System.out.println("90점 아래 점수: " + score);
 
        score = treeSet.higher(new Integer(90));
        System.out.println("90점 위 점수: " + score);
 
    }
 
}
 

  다음은 TreeSet이 가지고 있는 정렬과 관련된 메소드들입니다.

  descendingSet() 메소드는 내림차순으로 정렬된 NavigableSet 객체를 리턴하는데 NavigableSet은 TreeSet과 마찬가지로 first(), last(), lower() 등의 메소드를 제공하고, 정렬 순서를 바꾸는 descendingSet()을 제공합니다.

  오름차순으로 정렬하고 싶다면 descendingSet() 메소드를 두 번 호출하면 됩니다.

  * TreeSetExam2.java

 

 
package set;
 
import java.util.NavigableSet;
import java.util.TreeSet;
 
public class TreeSetExam2 {
 
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<Integer>();
 
        for (int i = 0; i < 5; i++) {
            treeSet.add(new Integer((int) Math.round(Math.random() * 70 + 30)));
        }
 
        NavigableSet<Integer> descendingSet = treeSet.descendingSet();
 
        for (Integer score : descendingSet) {
            System.out.print(score + " ");
        }
        System.out.println();
 
        NavigableSet<Integer> ascendingSet = descendingSet.descendingSet();
        for (Integer score : ascendingSet) {
            System.out.print(score + " ");
        }
    }
 
}
 

  다음은 TreeSet이 가지고 있는 범위 검색과 관련된 메소드들입니다.

  다음은 영어 단어를 TreeSet에 저장한 후 알파벳 c ~ f 사이의 단어를 검색해보는 예제입니다.

  * TreeSetExam3.java

 
package set;
 
import java.util.NavigableSet;
import java.util.TreeSet;
 
public class TreeSetExam3 {
 
    public static void main(String[] args) {
        TreeSet<String> words = new TreeSet<String>();
 
        words.add("apple");
        words.add("banana");
        words.add("china");
        words.add("cypher");
        words.add("description");
        words.add("ever");
        words.add("guess");
        words.add("cherry");
 
        System.out.println("[c~f 사이의 단어 검색]");
        NavigableSet<String> rangeSet = words.subSet("c", true, "f", true);
 
        for (String word : rangeSet) {
            System.out.println(word);
        }
    }
 
}
 

 5.2 TreeMap

  TreeMap은 이진 트리를 기반으로 한 Map 컬렉션입니다.

  TreeSet과 차이점은 키와 값이 저장된 Map.Entry를 저장한다는 점입니다.

  TreeMap에 객체를 저장하면 자동으로 정렬되는데, 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 노드에, 키 값이 높은 것은 오른쪽 노드에 Map.Entry에 저장합니다.

 

  TreeMap을 생성하기 위해서는 키로 저장할 객체 타입과 값으로 저장할 객체 타입을 타입 파라미터로 주고 기본 생성자를 호출하면 됩니다. 

  Map 인터페이스 타입 변수에 대입해도 되지만, TreeMap 클래스 타입으로 대입한 이유는 특정 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위해서입니다. 다음은 TreeMap이 가지고 있는 검색 관련 메소드입니다.

  다음 예제는 점수를 키로, 이름을 값으로 해서 무작위로 저장하고 특정 Map.Entry를 찾는 방법을 보여줍니다.

  * TreeMapExam1.java

package set;
 
import java.util.Map;
import java.util.TreeMap;
 
public class TreeMapExam1 {
 
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
 
        treeMap.put(new Integer(90), "Jack");
        treeMap.put(new Integer(77), "Mike");
        treeMap.put(new Integer(82), "Jolie");
        treeMap.put(new Integer(93), "Sminoph");
        treeMap.put(new Integer(67), "Neil");
        treeMap.put(new Integer(55), "Max");
 
        Map.Entry<Integer, String> entry = null;
 
        entry = treeMap.firstEntry();
        System.out.println("가장 낮은 점수: " + entry.getKey() + "-" + entry.getValue());
 
        entry = treeMap.lastEntry();
        System.out.println("가장 높은 점수: " + entry.getKey() + "-" + entry.getValue());
 
        entry = treeMap.lowerEntry(new Integer(95));
        System.out.println("95점 아래 점수: " + entry.getKey() + "-" + entry.getValue());
 
        while (!treeMap.isEmpty()) {
            entry = treeMap.pollFirstEntry();
 
            System.out.println(entry.getKey() + "-" + entry.getValue() + " (남은 객체 수: " + treeMap.size() + ")");
        }
    }
 
}
 
 

  * TreeMapExam2.java

 
package set;
 
import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;
 
public class TreeMapExam2 {
 
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
 
        treeMap.put(new Integer(100), "Jolie");
        treeMap.put(new Integer(95), "SAN E");
        treeMap.put(new Integer(81), "ZICO");
        treeMap.put(new Integer(79), "MICRODOT");
        treeMap.put(new Integer(71), "BASICK");
        treeMap.put(new Integer(67), "MINO");
        treeMap.put(new Integer(52), "Black Nut");
 
        NavigableMap<Integer, String> descendingMap = treeMap.descendingMap();
        Set<Map.Entry<Integer, String>> descendingEntrySet = descendingMap.entrySet();
 
        for (Map.Entry<Integer, String> entry : descendingEntrySet) {
            System.out.print(entry.getKey() + "-" + entry.getValue() + " ");
        }
        System.out.println();
 
        NavigableMap<Integer, String> ascendingMap = descendingMap.descendingMap();
        Set<Map.Entry<Integer, String>> ascendingEntrySet = ascendingMap.entrySet();
 
        for (Map.Entry<Integer, String> entry : ascendingEntrySet) {
            System.out.print(entry.getKey() + "-" + entry.getValue() + " ");
        }
    }
 
}
 

  다음은 TreeMap이 가지고 있는 범위 검색과 관련된 메소드들입니다.

 5.3 Comparable과 Comparator

  TreeSet의 객체와 TreeMap의 키는 저장과 동시에 자동 오름차순으로 정렬되는데, 숫자(Integer, Double) 타입일 경우에는 값으로 정렬하고, 문자열(String) 타입일 경우에는 유니코드로 정렬합니다.

  TreeSet과 TreeMap은 정렬을 위해 java.lang.Comparable을 구현한 객체를 요구하는데, Integer, Double, String은 모두 Comparable 인터페이스를 구현하고 있습니다. 

  사용자 정의 클래스도 Comparable을 구현한다면 자동 정렬이 가능합니다.

  Comparable에는 compareTo() 메소드가 정의되어 있기 때문에 사용자 정의 클래스에서는 이 메소드를 오버라이딩하여 다음과 같이 리턴 값을 만들어 내야 합니다.

  다음은 나이를 기준으로 Person 객체를 오름차순으로 정렬하기 위해 Comparable 인터페이스를 구현한 것입니다.

  * Person.java

 
package set;
 
public class Person implements Comparable<Person> {
 
    public String name;
    public int age;
 
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
 
    @Override
    public int compareTo(Person person) {
        if (age < person.age)
            return -1;
        else if (age == person.age)
            return 0;
        else
            return 1;
    }
 
}
 

 * ComparableExam.java

 
package set;
 
import java.util.Iterator;
import java.util.TreeSet;
 
public class ComparableExam {
 
    public static void main(String[] args) {
        TreeSet<Person> treeSet = new TreeSet<Person>();
 
        treeSet.add(new Person("Jackie", 44));
        treeSet.add(new Person("Jolie", 24));
        treeSet.add(new Person("Mike", 32));
 
        Iterator<Person> it = treeSet.iterator();
 
        while (it.hasNext()) {
            Person person = it.next();
            System.out.println(person.name + "-" + person.age);
        }
    }
 
}
 

  TreeSet의 객체와 TreeMap의 키가 Comparable을 구현하고 있지 않을 경우에는 저장하는 순간 ClassCastException이 발생합니다. 그렇다면 Comparable 비구현 객체를 정렬하는 방법은 없을까요? TreeSet 또는 TreeMap 생성자의 파라미터로 정렬자(Comparator)를 제공하면 Comparable 비구현 객체도 정렬시킬 수 있습니다.

  정렬자는 Comparator 인터페이스를 구현한 객체를 말하는데, Comparator 인터페이스에는 다음과 같이 메소드가 정의되어 있습니다.

 * DescendingComparator.java

 
package set;
 
import java.util.Comparator;
 
public class DescendingComparator implements Comparator<Fruit> {
 
    @Override
    public int compare(Fruit f1, Fruit f2) {
        if (f1.price < f2.price) return 1;
        else if (f1.price == f2.price) return 0;
        else return -1;
    }
    
}
 

 * Fruit.java

 
package set;
 
public class Fruit {
    public String name;
    public int price;
 
    public Fruit(String name, int price) {
        super();
        this.name = name;
        this.price = price;
    }
 
}
 

 * ComparatorExam.java

 
package set;
 
import java.util.Iterator;
import java.util.TreeSet;
 
public class ComparatorExam {
 
    public static void main(String[] args) {
        TreeSet<Fruit> treeSet = new TreeSet<Fruit>(new DescendingComparator());
 
        treeSet.add(new Fruit("Grape", 4000));
        treeSet.add(new Fruit("Apple", 10000));
        treeSet.add(new Fruit("Banana", 50000));
        treeSet.add(new Fruit("Pineapple", 2000));
 
        Iterator<Fruit> it = treeSet.iterator();
 
        while (it.hasNext()) {
            Fruit fruit = it.next();
            System.out.println(fruit.name + " : " + fruit.price);
        }
    }
 
}
 

  * 이 포스트은 서적 '이것이 자바다' 를 참고하여 작성한 포스트입니다.