컬랙션 검색, 병렬처리, 동기화

이진 트리(binary tree) 구조

검색을 위해서는 우선 정렬이 되어 있어야 하는데, 이때 정렬을 위해 이진트리구조를 이용합니다.

이진 트리 구조에 대한 자세한 내용은 생략하도록 하겠습니다.

 

TreeSet

이진트리 기반 Set 컬렉션입니다.

value와 왼쪽노드, 오른쪽노드로 구성됩니다.

import java.util.NavigableSet;
import java.util.TreeSet;

public class TreeSetEx {

	public static void main(String[] args) {
		TreeSet<Integer> scores = new TreeSet<Integer>();
		scores.add(new Integer(97));
		scores.add(new Integer(78));
		scores.add(new Integer(75));
		scores.add(new Integer(80));
		scores.add(new Integer(95));
		
		System.out.println("Min:"+scores.first());
		System.out.println("Max:"+scores.last());
		System.out.println("95점 아래:"+scores.lower(new Integer(95)));
		System.out.println("95점 위:"+scores.higher(new Integer(95)));
		System.out.println("95점 이거나 바로 아래:"+scores.floor(new Integer(95)));
		System.out.println("95점 이거나 바로 위:"+scores.ceiling(new Integer(95)));
		
		NavigableSet<Integer> descendingSet = scores.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 + " ");
		}
		System.out.println();
		
		while(!scores.isEmpty()) {
			//제일 낮은 객체를 꺼내어 컬렉션에서 제거
			System.out.println("("+scores.pollFirst()+") 남은 객체수:"+scores.size());
		}
	}

}

 

영단어를 정렬하고 범위를 검색하는 예제

import java.util.NavigableSet;
import java.util.TreeSet;

public class TreeSetEnglish {

	public static void main(String[] args) {
		TreeSet<String> treeSet = new TreeSet<String>();
		treeSet.add("banana");
		treeSet.add("apple");
		treeSet.add("book");
		treeSet.add("console");
		treeSet.add("problems");
		treeSet.add("task");
		treeSet.add("server");
		treeSet.add("result");
		treeSet.add("cherry");
		treeSet.add("base");
		
		System.out.println("b에서 c사이 단어 검색");
		
		NavigableSet<String> rangeSet = treeSet.subSet("b", true, "c", true);
		for(String word : rangeSet) {
			System.out.println(word);
		}
		
	}

}

 

TreeMap

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

다만 value 값이 Map entry가 저장되어 있는 것이 다릅니다.

import java.util.Map;
import java.util.NavigableMap;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapEx {

	public static void main(String[] args) {
		TreeMap<Integer, String> scores = new TreeMap<Integer, String>();
		scores.put(new Integer(77), "홍길동");
		scores.put(new Integer(88), "고길동");
		scores.put(new Integer(97), "김길동");
		scores.put(new Integer(85), "이길동");
		scores.put(new Integer(90), "박길동");
		
		Map.Entry<Integer, String> entry = null;
		entry = scores.firstEntry();
		System.out.println("가장 낮은 점수: "+entry.getKey()+"-"+entry.getValue());
		
		entry = scores.lastEntry();
		System.out.println("가장 높은 점수: "+entry.getKey()+"-"+entry.getValue());
		
		entry = scores.lowerEntry(new Integer(90));
		System.out.println("90점 아래 점수: "+entry.getKey()+"-"+entry.getValue());
		
		entry = scores.higherEntry(new Integer(90));
		System.out.println("90점 위 점수: "+entry.getKey()+"-"+entry.getValue());
		
		entry = scores.floorEntry(new Integer(90));
		System.out.println("90이거나 바로 아래 점수: "+entry.getKey()+"-"+entry.getValue());
		
		entry = scores.ceilingEntry(new Integer(90));
		System.out.println("90점 이거나 바로 위 점수: "+entry.getKey()+"-"+entry.getValue());
		
		System.out.println("------------");
		NavigableMap<Integer,String> descendingMap = scores.descendingMap();
		Set<Map.Entry<Integer,String>> descendingEntrySet = descendingMap.entrySet();
		for(Map.Entry<Integer, String> mEntry : descendingEntrySet) {
			System.out.print(mEntry.getKey() + "-" + mEntry.getValue() + " ");
		}
		System.out.println();
		System.out.println("------------");
		NavigableMap<Integer,String> ascendingMap = descendingMap.descendingMap();
		Set<Map.Entry<Integer,String>> ascendingEntrySet = ascendingMap.entrySet();
		for(Map.Entry<Integer, String> mEntry : ascendingEntrySet) {
			System.out.print(mEntry.getKey() + "-" + mEntry.getValue() + " ");
		}
		System.out.println();
		System.out.println("------------");
		
		while(!scores.isEmpty()) {
			entry = scores.pollFirstEntry();	//낮은 값부터 하나씩 선택 후 컬렉션에서 제거
			System.out.println(entry.getKey() + "-" + entry.getValue());
			System.out.println("남은 객체 수: "+scores.size());
		}
		
	}

}

 

키로 정렬하고 범위 검색 예제

import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

public class TreeMapEnglish {

	public static void main(String[] args) {
		TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();
		treeMap.put("banana", 10);
		treeMap.put("apple", 60);
		treeMap.put("book", 40);
		treeMap.put("console", 50);
		treeMap.put("problems", 10);
		treeMap.put("task", 20);
		treeMap.put("server", 70);
		treeMap.put("result", 30);
		treeMap.put("cherry", 110);
		treeMap.put("base", 80);
		
		System.out.println("b에서 c사이 단어 검색");
		
		NavigableMap<String, Integer> rangeMap = treeMap.subMap("b", true, "c", true);
		for(Map.Entry<String, Integer> mEntry : rangeMap.entrySet()) {
			System.out.println(mEntry.getKey() + "-" + mEntry.getValue());
		}
		
	}

}

 

Comparable과 Comparator

TreeSet의 객체와 TreeMap의 키는 저장과 동시에 정렬되는데 숫자의 경우 값으로 정렬하고 문자인 경우 유니코드 순서로 정렬합니다.

Comparable 인터페이스를 구현하여 정렬하게 되는데, 사용자 정의 클래스들도 Comparable을 구현하면 정렬이 가능합니다.

Compatable에는 compareTo() 메소드가 정의 되어 있는데 이 메소드를 오버라이딩하여야 합니다.

만약 인수로 주어진 객체와 같으면 0을 리턴하고, 작으면 음수를 리턴하고, 크면 양수를 리턴하도록 compareTo() 메소드를 재정의 해야 합니다.

 

Person.java

public class Person implements Comparable<Person>{
	public String name;
	public int age;
	
	public Person(String name, int age) {
		this.name = name;
		this.age = age;
	}

	@Override
	public int compareTo(Person o) {
		if(age < o.age) {
			return -1;
		}else if(age == o.age) {
			return 0;
		}else {
			return 1;
		}
	}

}

ComparableEx.java

import java.util.Iterator;
import java.util.TreeSet;

public class ComparableEx {

	public static void main(String[] args) {
		TreeSet<Person> treeSet = new TreeSet<Person>();
		treeSet.add(new Person("홍길동", 40));
		treeSet.add(new Person("고길동", 50));
		treeSet.add(new Person("김길동", 31));
		
		Iterator<Person> iterator = treeSet.iterator();
		while(iterator.hasNext()) {
			Person person = iterator.next();
			System.out.println(person.name + ":" + person.age);
		}
		
	}

}

 

멀티 스레드 컬렉션 동기화

Vector와 Hashtable은 synchronized 메소드로 되어 있기 때문에 멀티 스레드에서 안전합니다.

Collections 패키지 에서는 List, Map, Set은 동기화된 객체로 래핑(변환)하는 메소드를 제공하고 있습니다.

• List<T> : synchronizedList(List<T> list)
• Map<K,V> : synchronizedMap(Map<K,V> m)
• Set<T> : synchronizedSet(Set<T> s)

List<T> list = Collections.synchronizedList(new ArrayList<T>());

 

병렬처리를 위한 컬렉션

자바는 멀티스레드에서 사용할 수 있는 컬렉션을 java.util.concurrent 패키지에 ConcurrentHashMap과 ConcurrentLinkedQueue를 제공하고 있습니다.