Chapter 11 컬렉션 프레임웍(Collection Framework)

1. 컬렉션 프레임웍 (Collection Framework)

• 컬렉션: 여러 객체(데이터)를 모아 놓은 것
• 프레임워 = 라이브러리(기능) + 프로그래밍 방식
  • 프레임워크: 표준화, 정형화된 체계적인 프로그래밍 방식
• 컬렉션 프레임워크: 데이터 군을 저장하는 클래스들을 표준화한 설계
  • 컬렉션(다수의 객체)을 다루기 위해 표준화된 프로그래밍 방식
  • 컬렉션을 쉽고 편리하게 다룰 수 있는 다양한 클래스 제공

 

  1.1 컬렉션 프레임웍의 핵심 인터페이스

• List: 순서가 있는 데이터의 집합, 데이터 중복을 허용
• Set: 순서를 유지하지 않는 데이터의 집합, 중복 허용하지 않는다. ex) HashSet, TreeSet
• Map: 키 - key(중복 허용하지 않는다.)와 값-value(중복 허용)이 쌍으로 이루어진 데이터의집합
  • ex) ID-password Map.Entry인터페이스: Map내부의 인터페이스
  • 같은 key에 대해 여러 번 데이터를 저장하면 나중에 저장한 value가 들어간다.   
• Collection인터페이스(List와 Set의 조상)

 

  1.2 ArrayList - 순서 유지

• ArrayList는 기존의 Vector를 개선한 것으로 구현 원리와 기능적으로 동일
• Vector는 자체적으로 동기화 처리가 되어 있으나 ArrayList는 그렇지 않다.
• 둘 다 List 인터페이스를 구현하므로 저장 순서가 유지되고 중복을 허용
• ArrayList는 데이터의 저장 공간으로 "Object 배열"을 사용한다. (배열 기반)
• ArrayList 의 장단점
  • 장점: 배열은 구조가 간단하고 데이터를 읽는데 걸리는 시간이 짧다.
  • 단점: 크기를 변경 시, 효율성이 좋지 않다. (변경하려면 사이즈가 큰 새로운 Object 배열을 생성해서 기본 배열을 복사해야한다.)
  • 큰 배열을 생성하면 메모리를 낭비하게 되고 비순차적인 데이터의 추가하거나 삭제할 때 시간이 걸린다.

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class ArrayListEx1 {
	public static void main(String[] args) {
		ArrayList list1 = new ArrayList(10);
		list1.add(new Integer(5));
		list1.add(new Integer(4));
		list1.add(new Integer(2));
		list1.add(new Integer(0));
		list1.add(new Integer(1));
		list1.add(new Integer(3));
			
		ArrayList list2 = new ArrayList(list1.subList(1, 4));
		print(list1, list2);
		
		Collections.sort(list1);	// list1과 list2를 정렬
		Collections.sort(list2);	// Collection.sort(List 1)
		print(list1, list2);
	
		System.out.println("list1.containsAll(list2):" + list1.containsAll(list2));
		list2.add("B");
		list2.add("C");
	
		list2.add(3, "A");
		print(list1, list2);
		
		list2.add(3, "AA");
		print(list1, list2);
		// list1에서 list2와 겹치는 부분만 남기고 나머지는 삭제한다.
		System.out.println("list1.retainAll(list2):" + list1.retainAll(list2));
		
		print(list1, list2);
		// list2에서 list1에 포함된 객체들을 삭제한다. 
		for(int i = list2.size() - 1; i >= 0; --i) {
			if(list1.contains(list2.get(i))) 
				list2.remove(i);
		}
		print(list1, list2);
	}
	static void print(ArrayList list1, ArrayList list2) {
		System.out.println("list1:" + list1);
		System.out.println("list2:" + list2);
		System.out.println();
	}
}

  Note) 실행 결과

  - ArrayList는 List인터페이스를 구현하므로 순서를 유지한다.

  - Collections클래스의 sort메서드를 이용해서 ArrayList에 저장된 객체들을 정렬.

  - list1.retainAll(list2): list1에서 list2와 겹치는 부분을 빼고 모두 삭제한다.

  - list2에서 list1에 포함된 객체들이 있다면 삭제한다.

  

 - 벡터의 크기(size)와 용량(capacity)

    -> 크기: 실제로 저장된 객체의 개수

    -> 용량: 배열의 길이

 

  Ex) 

<hide/>
package javaStudy;
import java.util.*;
public class VectorEx1 {
public static void main(String[] args) {
	Vector v = new Vector(5);
	v.add("1");
	v.add("2");
	v.add("3");
	print(v);
	
	v.trimToSize();		//빈공간을 없앤다.
	System.out.println("=== After trimToSize() ===");
	print(v);
	
	v.ensureCapacity(6);
	System.out.println("===After ensureCapacity(6)===");
	print(v);
	
	v.setSize(7);		//v의 사이즈가 7이 되도록한다. 
	System.out.println("===After setSize(7)===");
	print(v);
	
	v.clear();
	System.out.println("===Afte clear()===");
	print(v);
}
	public static void print(Vector v) {
		System.out.println(v);
		System.out.println("size : "+ v.size());
		System.out.println("capacity :" + v.capacity() );
	}
}

  Note) 실행 결과

  1) capacity가 5인 Vector인스턴스 v를 생성하고 3개의객체를 저장.

  2) v.trimToSize()를 호출하면 v의 빈 공간을 없애서 size와 capacity를 갖게 한다. 배열은 크기를 변경할 수 없다

    - 그러므로 새로운 배열을 생성해서 그 주소값을 v에 할당한다. 기존의 Vecotr인스턴스는 더 이상 사용할 수 없다.

    - 메모리에서 제거된다.

  3) v.ensureCapacity(6): v의 capacity가 최소한 6이 되도록 한다.

    - v의 capacity가 6이상이라면 아무 일 일어나지 않는다.

    - capacity가 3이므로 크기가 6인 배열을 생성해서 v의 내용을 복사했다.

    - 기존의 인스턴스를 재사용하지 않고 새로운 인스턴스를 생성한 것이다. 

  4) v.setSize(7)은 v의 size가 7이 되도록 한다. capacity가 6이므로 새로운 인스턴스를 생성해야한다. 

    - Vector는 capacity가 부족한 경우 기존의 크기보다 두 배 크기로 증가된다.  v의 capacity => 12

  5) v.clear()는 v의 모든 요소를 삭제한다. 

 

  Note) 실행 결과

  1) 삭제한 데이터의 아래에 있는 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.

  2) 데이터가 모두 한 칸씩 위로 이동하였으므로 마지막 데이터는 null로 변경한다.

  3) 데이터가 삭제되어 데이터의 개수가 줄었으므로 size의 값을 1감소시킨다.

 

  1.3 LinkedList - 배열의 단점을 보완

• 불연속적으로 존재하는 데이터를 연결한 구조이다.
• 각 요소를 노드(Node)라고 한다.
• 각 노드는 다음 요소에 대한 참조와 데이터로 구성된다.; 
• 데이터 개수가 많아질수록 접근 시간이 길어진다.
• 연결 리스트는 데이터 접근성이 나쁘다.
  • 더블리 링크드 리스트 - 이중 연결리스트(doubly linked list), 접근성 향상
  • 링크드 리스트에 참조 변수를 하나 더 추가하여 다음/이전 요소에 대한 참조 가능하다
  • 더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스트
  • 더블 링크드 리스트의 접근성을 보다 향상시킨다.

 

  Ex) 

<hide/>
package first;
import java.util.*;

public class TreeMapEx1 {
	public static void main(String[] args) {
		String[] data = {"A", "K", "A", "K", "D", "K", "A", "K", "K", "K", "Z", "D"};
		TreeMap map = new TreeMap();
		
		for(int i = 0; i < data.length; ++i) {
			if(map.containsKey(data[i])) {
				Integer value = (Integer)map.get(data[i]);
				map.put(data[i],value.intValue()+ 1 );
			}else {
				map.put(data[i], 1);
				
			}
			Iterator it = map.entrySet().iterator();
			
			System.out.println("=기본정렬=");
			while( it.hasNext() ){
				Map.Entry entry = (Map.Entry)it.next();
				int value = ((Integer)entry.getValue()).intValue();
				System.out.println(entry.getKey() + " : "  + printBar('*', value) + " " + value );
			}
			System.out.println();
			
			// map을 ArrayList로 변환한 다음에 Collections.sort()로 정렬
			Set set = map.entrySet();
			List list = new ArrayList(set);
			
			// static void sort(List list,  Comparator c)
			Collections.sort(list, new ValueComparator());
			
			it = list.iterator();
			
			System.out.println("=값의 크기가 큰 순서로 정렬=");
			while(it.hasNext()) {
				Map.Entry entry  = (Map.Entry) it.next();
				int value = ( (Integer)entry.getValue()).intValue();
				System.out.println(entry.getKey() + " : " + printBar( '#' , value) + " " + value);
				
			}
	
		}
	
	}
	static class ValueComparator implements Comparator {
		public int compare(Object o1, Object o2) {
			if(o1 instanceof Map.Entry && o2 instanceof Map.Entry) {
				Map.Entry e1 = (Map.Entry)o1;
				Map.Entry e2 = (Map.Entry)o2;
				
				int v1 = ((Integer)e1.getValue()).intValue();
				int v2 = ((Integer)e2.getValue()).intValue();
				return   v2- v1;		
			}
			return -1;
		}
	}	// static class ValueComparator implements Comparator
	
	public static String printBar(char ch, int value) {
		char [] bar = new char[value];
		for(int i = 0; i < bar.length; ++i) {
			bar[i] = ch;
		}
		return new String(bar);
	}
}

 

Note)

 

 

  Note) ArrayList와 LinkedList 비교 

• 순차적으로 데이터를 추가/삭제(마지막 데이터부터 역순으로 삭제) - ArrayList가 빠름(재배치할 필요 없어서)
•  중간 데이터를 추가/삭제 - LinkedList가 빠름 (각 요소간의 연결만 변경해주면 된다.)
• 처음에 데이터를 저장할 때는 ArrayList를 이용하다가 데이터 저장, 삭제 같은 작업을 할 때에는 LinkedList를 사용하는 것도 좋은 방법이다.
• ArrayList는 순차적인 추가,삭제(ex) 컬렉션의 맨 뒤에 추가, 삭제) 는더 빠르지만 비효율적인 메모리 사용이 단점이다 
  • 배열을 이용하므로 순차적인 추가,삭제가 빠르다. 
  • 배열의 크기가 바뀔 때, 메모리 할당이 발생하므로 비효율적이다. 

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class ArrayListLinkedListTest2 {
	public static void main(String[] args) {
		ArrayList al = new ArrayList(1000000);
		LinkedList ll = new LinkedList();
		add(al);
		add(ll);
		System.out.println("=접근시간 테스트=");
		System.out.println("ArrayList: " + access(al));
		System.out.println("LinkedList: " + access(ll));
	}
	public static void add(List list) {
		for(int i = 0; i < 100000; ++i) list.add(i+"");
	}
	public static long access(List list) {
		long start = System.currentTimeMillis();
		for(int i = 0;i < 10000; ++i) list.get(i);
		long end = System.currentTimeMillis();
		return end - start;	
	}
}

  Note) 실행 결과

  - 인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기

  - 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야 원하는 값 얻을 수 있다.

  - 두 클래스의 장점을 이용해서 두 클래스를 조합해서 사용할 수도 있다. 

 

 

  1.4 Stack과 Queue

• 스택(Stack): LIFO(Last In First Out)구조, 마지막에 저장된 것을 제일 먼저 꺼낸다. (후입 선출)
  • 수식 계산, 수식 괄호 검사, undo/redo, 뒤로/ 앞으로 (웹 브라우저)
  • boolean add():객체를 추가하고 성공하면 true반환, 부족하면 예외발생
  • Object push(): 저장(반환값 없음) 

• 큐(Queue) : FIFO(First In First Out)구조, 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다. 
• offer(): 큐의 데이터 저장

  

  - 큐의 변형 - Deque, PriorityQueue, BlockingQueue

    -> 덱(Deque): 양 끝에서 저장(offer)과 삭제 가능, stack과 queue의 결합

    -> 우선 순위가 높은 것부터 꺼냄(null 저장 불가)

      -> 힙(heap) 정렬

    -> 블라킹 큐(BlockingQueue): 비어있을 때 꺼내기와 가득 차 있을 때 넣기를 지정된 시간동안 지연시킨다. 

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class StackQueueEx {
	public static void main(String[] args) {
		Stack  st = new Stack();
		Queue q = new LinkedList();	// Queue인터페이스의 구현채안 LinkedList를 사용
		st.push("0");
		st.push("1");
		st.push("2");
		q.offer("0");
		q.offer("1");
		q.offer("2");
		
		System.out.println("= Stack =");
		while(!st.empty()){
			System.out.println(st.pop());
		}
		System.out.println("= Queue =");
		while( !q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

  Note) 실행 결과

  - 스택과 큐에 0, 1, 2를 같은 순서로 넣고 꺼내면 결과가 다르다.

  - 자바에서는 스택을 클래스로 구현하지만 큐는 인터페이스로 정의되어 있고 클래스는 없다.

 

  - 스택과 큐의 활용

    -> 스택: 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/ 앞으로

    -> 큐: 최근사용문서, 인쇄 작업 대기목록, 버퍼(buffer)

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class StackEx1 {
	public static Stack back = new Stack();
	public static Stack forward = new Stack();
	
    public static void main(String[] args) {
		goURL("1.네이트");
		goURL("2.야후");
		goURL("3.네이버");
		goURL("4.다음");
		
		printStatus();
		
		goBack();
		System.out.println("= '뒤로' 버튼을 누른 후 =");
		printStatus();
		
		goBack();
		System.out.println("= '뒤로' 버튼을 누른 후 =");
		printStatus();
		
		goForward();
		System.out.println("= '앞으로' 버튼을 누른 후 =");
		printStatus();
		
		goURL("codechobo.com");
		System.out.println("= 새로운 주소로 이동 후 =");
		printStatus();	
	}
	public static void printStatus() {
		System.out.println("back: " + back);
		System.out.println("forward: " + forward);
		System.out.println("현재 화면은 '" + back.peek() + "' 입니다.");
		System.out.println();	
	}
	public static void goURL(String url) {
		back.push(url);
		if(!forward.empty())
			forward.clear();
	}
	public static void goForward() {
		if(!forward.empty())
			back.push(forward.pop());
	}
	public static void goBack() {
		if(!back.empty())
			forward.push(back.pop());	
	}	
}

 

  Note) 실행결과

  - 웹 브라우저의 뒤로, 앞으로 기능을 구현한 예제이다.

  - 두 개의 스택을 이용해서 구현할 수 있다.

 

 

 

  Ex) 우선순위 큐(PriorityQueue)

<hide/>
package javaStudy;
import java.util.*;
public class PriorityQueueEx {
	public static void main(String[] args) {
		Queue pq = new PriorityQueue();
		pq.offer(3);	// pq.offer(new Integer(3)); 오토 박싱
		pq.offer(1);
		pq.offer(5);
		pq.offer(2);
		pq.offer(4);
		System.out.println(pq);	//pq의 내부 배열을 출력
		Object obj = null;
		// PriorityQueue에 저장된 요소를 하나씩 꺼낸다.
		while(( obj = pq.poll())!=null )
			System.out.println(obj);
	}
}

  Note) 실행 결과

  - 저장한 순서와 관계없이 우선순위가 높은 것 부터꺼내게 된다. 

  - null은 저장 불가 (NullPointerException 발생)

  - PriorityQueue는 저장공간으로 "배열"을 이용하고 각 요소를  "힙(heap)" 자료구조 형태로 저장한다.

  - 숫자가 작을수록 우선 순위가 높기 때문에 1이 가장 먼저 출력된다. 

  - 참조변수 pq를 출력하면 저장한 순서와 다르게 저장된다.

  - 힙이라는 자료구조의 형태로 저장되었기 때문이다. (가장 큰 값이나 작은 값은 빠르게 찾을 수 있다.)

 

 

  Ex) Deque (Double-Ended Queue)

• Deque(Double Ended Queue)는 양쪽 끝에 추가/삭제 가능하다. pollFirst(), pollLast(), peekFirst(), peekLast()
• ArrayDeque와 LinkedList가 있다.
• Stack + Queue => Deque 

 

 

  1.5  Iterator,  Listlterator,  Enumeration

  - 컬렉션에 저장된 데이터에 접근하는데 사용되는 인터페이스

  - Enumeration은 Listlterator의 구버전

  - Listlterator는 lterator의 기능을 향상시킨 것이다.

  - Iterator 

    -> 컬렉션에 저장된 요소들은 읽어오는 방법을 표준화한 것

    -> 컬렉션에 iterator()를 호출해서 Iterator를 구현한 객체를 얻어서 사용한다.

     -> Iterator는 일회용이다. 필요하면 새로 얻어와서 사용해야한다.

  - ListIterator - Iterate의 기능을 확장(상속)

  -> 단방향 -> 양방향

  -> List 인터페이스에 정의된다.

  - Map인터페이스를 구현한 클래스는 키, 값을 쌍으로 저장하기 때문에 iterator()를 직접 호출할 수 없고 

    -> keySet()아니 entrySet() 메서드를 통해 키/ 값을 따로 Set의 형태로 얻은 다음에 iterator()를 호출할 수 있다.

 

 

   Note) iterator의 메서드

  - boolean hasNext(): 읽어올 요소가 있으면 true 아니면 false 반환 

  - Object next(): 다음 요소를 읽어온다.

  - void remove(): next()로 읽어온 요소를 삭제한다.

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class IteratorEx1 {
	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");
		Iterator it = list.iterator();
		while(it.hasNext()) {
			Object obj = it.next();
			System.out.println(obj);
		}
	}	
}

  Note) 실행결과

  - List클래스들은 저장순서를 유지하기 때문에 Iterator를 이용해서 읽어온 결과 역시 저장 순서와 동일하다.

  - 하지만, Set클래스들은 각 요소간의 순서가 유지되지 않는다.

  - 그렇기 때문에 Iterator를 이용해서 저장된 요소들을 읽어와도 처음에 저장된 순서와 같지 않다. 

 

 

  Ex) ListIterator의 사용방법

<hide/>
package javaStudy;
import java.util.*;
public class ListIteratorEx1 {
	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		list.add("1");
		list.add("2");
		list.add("3");
		list.add("4");
		list.add("5");
		
		ListIterator it = list.listIterator();
		while(it.hasNext()) {
			System.out.print(it.next());	// 순방향으로 진행하면서 읽어온다.
		}
		System.out.println();
		while(it.hasPrevious()) {
			System.out.print(it.previous());	// 역방향으로 진행하며 읽어온다.
		}
		System.out.println();	
	}
}

  Note) 실행결과

  - Iterator는 단방향으로만 이동하기 때문에 컬렉션의 마지막 요소에 다다르면 더 이상 사용할 수 없다.

  - ListIterator는 양방향으로만 이동하기 때문에 각 요소간의 이동이 자유롭다.

  - 이동하기 전에 hasNext()나 hasPrevious()를 호출해서 이동 가능한지 확인해야한다.

  

 

  1.6 Arrays 

  - 끝에 's'가 붙으면 static 메서드 제공  ex) Objects

  - 배열을 다루기 편리한 메서드(static) 제공

  1) 배열의 출력 - toString()

  2) 다차원 배열의 비교와 출력 - deepToString() - 다차원, equals() - 1차원, deepEquals() - 다차원

  3) 배열의 복사 - copyOf(), copyOfRange()

  4) 배열 채우기

    -> fill() - 배열의 모든 요소를 지정된 값으로 채운다.

    -> setAll() - 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다.

  5) 배열을 List 로 변환 - asList(Object ... a)

  6) 배열의 정렬과 검색 - sort(), binarySearch()

    -> binarySearch() 이진 탐색: 배열이 정렬된 상태에서만 올바른 결과를 반환한다.

    -> linearSearch() 순차 검색: 배열의 첫 번째 요소부터 하나씩 검색

 

  7) 배열의 비교와 출력 - equals(), toString() - 일차원 배열에만 사용 가능, deepToString() - 다차원 배열

 

  8) 배열을 List로 변환 - asList(Object ... a)

    - asList()는 배열을 List에 담아서 반환한다. (asList()가 반환한 List크기를 변경할 수 없다.)

      -> 추가 또는 삭제가 불가능하다.  

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class ArrayEx {
	public static void main(String[] args) {
		int []  arr= {0, 1, 2, 3, 4};
		int [][] arr2D = {  {11, 12, 13} , {21, 22, 23}};

		System.out.println("arr = " + Arrays.toString(arr));
		System.out.println("arr2D = " + Arrays.deepToString(arr2D));
		
		int []  arr2 = Arrays.copyOf(arr, arr.length); 
		int []  arr3 = Arrays.copyOf(arr, 3); 
		int []  arr4 = Arrays.copyOf(arr, 7); 
		int []  arr5 = Arrays.copyOfRange(arr, 2, 4); 
		int []  arr6 = Arrays.copyOfRange(arr, 0, 7); 
		
		System.out.println("arr2 = " + Arrays.toString(arr2));
		System.out.println("arr3 = " + Arrays.toString(arr3));
		System.out.println("arr4 = " + Arrays.toString(arr4));
		System.out.println("arr5 = " + Arrays.toString(arr5));
		System.out.println("arr6 = " + Arrays.toString(arr6));
		
		int [] arr7 = new int[5];
		Arrays.fill(arr7, 9);
		System.out.println("arr7 = " + Arrays.toString(arr7));
		
		Arrays.setAll(arr7 , i -> (int) ( Math.random() * 6) + 1);
		System.out.println("arr7 = " + Arrays.toString(arr7));
		
		for(int i : arr7) {
			char[] graph = new char[i];
			Arrays.fill(graph, '*');
			System.out.println(new String(graph) + i);
		}
		
		String [][] str2D = new String[][] { {"aaa", "bbb"}, {"AAA", "BBB"}};
		String [][] str2D2 = new String[][] { {"aaa", "bbb"}, {"AAA", "BBB"}};
		
		System.out.println(Arrays.equals(str2D, str2D2));	// false
		System.out.println(Arrays.deepEquals(str2D, str2D2));	// true
		
		char [] chArr = {'A', 'D', 'C', 'B', 'E'};
		
		System.out.println("chArr =" + Arrays.toString(chArr));
		System.out.println("index of B =" + Arrays.binarySearch(chArr, 'B'));
		System.out.println("= After sorting =");
		Arrays.sort(chArr);
		System.out.println("chArr =" + Arrays.toString(chArr));
		System.out.println("index of B =" + Arrays.binarySearch(chArr, 'B'));
	}
}

  Note) 실행결과

 

  1.7 Comparator와 Comparable

  - 객체를 정렬하는데 필요한 메서드를 정의한 인터페이스(정렬 기준을 제공한다.)

    -> Comparator: 기본 정렬 기준을 구현하는데 사용

    -> Comparable: 기본 정렬 기준외에 다른 기준으로 정렬하고자할 때 사용한다.

  - compare() -> 반환값: int 음수/ 0/ 양수

  - compareTo() -> 비교하는 값보다 작으면 음수 / 0 / 크면 양수 

  - 인터페이스 Comparable을 구현한 클래스는 기본적으로 오름차순으로 정렬되어 있다.

  - 다른 기준으로 정렬하려면 Comparator를 구현해서 정렬 기준을 제공할 수 있다. 

 

  ex) Student는 Comparable<Student>를 상속받고, compareTo를 오버라이드 하면

    -> Collections.sort()를 통해 정렬할 수 있다.

<hide/>
@Override
public int compareTo(Student o){
	return this.no - o.no; 	// 오름차순 정렬
}

 

  1.8 HashSet

  - Set 인터페이스를 구현한 가장 대표적인 컬렉션이다.

  - HashSet은 내부적으로 HashMap을 사용해서 만들어졌다. 

  - HashSet은 중복된 요소를 저장하지 않는다. 

  - 중복 제거하는 동시에 순서를 유지하려면 HashSet 대신 LinkedHashSet을 사용해야 한다. (넣는 순서대로 나온다.)

 

  - hashCode()의 조건

  1) 실행 중인 애플리케이션 내의 동일한 객체에 대해 여러 번 hashCode()를 호출해도 동일한 int 값을 반환해야한다.

    하지만, 실행 시마다 동일한 int 값을 반환할 필요는 없다.

  2) equals메서드를 이용한 비교에 의해서 true를 얻은 두 객체에 대해 각각 hashCode를 호출해서 얻은 결과는 같아야 한다.

  3) equals메서드를 호출했을 때, false를 반환하는 두 객체는 hashCode호출에 대해 같은 int값을 반환하는 경우가 있어도 괜찮지만, 해싱을 사용하는 컬렉션의 성능을 향상시키기 위해서는 다른 int 값을 반환하는 것이 좋다. 

 

  1.9 TreeSet  - 정렬

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

  - Set 인터페이스를 구현했기 때문에 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하고 순서를 유지하지 않는다. 

  Ex)  이진 검색 트리에 7, 4, 9, 1, 5의 순서로 값을 저장한다고 가정한다.

    - 첫 번째로 저장되는 값 7 = 루트

    - 두 번째도 값은 트리의 루트부터 시작해서 값을 비교하면서 내려간다.

    -  결과를 보면 왼쪽이 가장 작은 값, 오른쪽이 가장 큰 값이 된다. 

 

    - 이진 검색 트리 (binary search tree)

    1) 모든 트리는 최대 두 개의 자식노드를 가질 수 있다.

    2) 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야한다.

    3) 노드의 추가, 삭제에 시간이 걸린다. (순차적으로 저장하지 않기 때문)

    4) 검색(범위 검색)과 정렬에 유리한다.

    5) 중복된 값을 저장하지 못한다.

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class TreeSetEx1 {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		String from = "b";
		String to = "d";
		set.add("abc");		 set.add("alien");		set.add("bat");
		set.add("car");		 set.add("Car");		set.add("disc");
		set.add("dance");	 set.add("dZZZZ");		set.add("dzzzz");
		set.add("elephant"); set.add("elevator");	set.add("fan");
		set.add("flower");
		System.out.println(set);
		System.out.println("range search : from " + from +" to: " + to );
		System.out.println("result1 " + set.subSet(from, to) );
		System.out.println("result2 " + set.subSet(from, to + "zzz"));
	}
}

  Note) 실행결과

  - subSet을 이용해서 범위검색을 할 때 시작 범위는 포함되지만 끝 범위는 포함되지 않으므로 

  - result1에는 c로 시작하는 단어까지만 검색 결과에 포함한다. 

  - 'zzz'를 붙이면 dzzz 다음에 오는 단어는 없기 때문에 d로 시작하는 모든 단어가 포함된다.

  - 대문자가 소문자에 우선하므로 abc보다 Car가 앞에 있다.

  - 문자열의 경우 정렬순서는 문자의 코드값이 기준이 된다. 

     -> 오름차순의 경우: 코드값이 작은순서 -> 큰 순서  (공백 -> 숫자 -> 대문자 -> 소문자)

     -> 내림차순의 경우: 위와 반대.

 

  Note) Map의 차이점 

    - hashMap: 키 값만 중복되지 않도록 넣는다

    - LinkedHashMap: 넣는 순서대로

    - TreeMap: 정렬

 

  1.10 HashMap과 Hashtable

  - 둘의 관계는 ArrayList와 Vector의 관계와 같다.

  -  Hashtable 보다는 HashMap을 권장

    -> HashMap은 Entry라는 내부 클래스 정의하고 다시 Entry 타입의 배열을 선언한다.

    -> 키와 값은 관련된 값이므로 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 "데이터 무결성" 면에서 바람직

  - 키(key): 컬렉션 내의 키 중에서 유일해야한다. / 값(value): 키와 달리 데이터의 중복을 허용한다.

 

  Ex) 

<hide/>
package javaStudy;
import java.util.*;
public class HashMapEx1 {
	public static void main(String[] args) {
		HashMap map = new HashMap();	// HashMap을 생성하고 데이터를 저장
		map.put("myId", "1234");
		map.put("asdf", "1111");
		map.put("asdf", "1234");
		Scanner s = new Scanner(System.in);	//화면으로부터 라인 단위로 입력받는다.
		
		while(true) {
			System.out.println("id와 password를 입력하세요");
			System.out.print("id: ");
			String id = s.nextLine().trim();
			System.out.print("password: ");
			String password = s.nextLine().trim();
			System.out.println();
			
			if(!map.containsKey(id) ) {
				System.out.println("입력하신 id는 존재하지 않습니다." + "다시 입력해주세요");
				continue;
			}
			if(!map.get(id).equals(password)) {
				System.out.println("비밀번호가 일치하지 않습니다. 다시 입력해주세요");
				
			}else {
				System.out.println("id와 비밀번호가 일치합니다.");
				break;
			}
		}
	}
}

  Note) 실행 결과

  - HashMap을 생성하고 ID와 비밀번호를 키와 값의 쌍으로 저장한 다음, ID를 키로 HashMap에서 검색해서 얻은 값을 입력된 비밀번호와 비교하는 예제이다.

  - 키는 중복을 허용하지 않는다.

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
public class HashMapEx3 {
	static HashMap phoneBook = new HashMap();
	public static void main(String[] args) {
		addPhoneNo("친구", "이자바", "010-111-1111");
		addPhoneNo("친구", "김자바", "010-222-2222");
		addPhoneNo("친구", "김자바", "010-333-3333");
		addPhoneNo("회사", "김대리", "010-444-4444");
		addPhoneNo("회사", "김대리", "010-555-5555");
		addPhoneNo("회사", "박대리", "010-666-6666");
		addPhoneNo("회사", "이과장", "010-777-7777");
		addPhoneNo("세탁", "010-888-8888");
		printList();
	}
	// 그룹에 전화번호를 추가하는 메서드
	static void addPhoneNo(String groupName, String name, String tel) {
		addGroup(groupName);
		HashMap group = (HashMap)phoneBook.get(groupName);
		group.put(tel, name);		// 이름은 중복될 수 있으니 전화번호를 key로 저장한다.
	}
	// 그룹을 추가하는 메서드
	static void addGroup(String groupName) {
		if(!phoneBook.containsKey(groupName)){
			phoneBook.put(groupName, new HashMap());
		}
	}
	static void addPhoneNo(String name, String tel) {
		addPhoneNo("기타", name, tel);
	}
	// 전화번호부 전체를 출력하는 메서드
	static void printList() {
		Set set = phoneBook.entrySet();
		Iterator it = set.iterator();
		while(it.hasNext()) {
			Map.Entry e = (Map.Entry)it.next();
			Set subSet = ((HashMap)e.getValue()).entrySet();
			Iterator subIt = subSet.iterator();
			System.out.println(" * " + e.getKey() + "[" + subSet.size() + "]" );
	
			while(subIt.hasNext()) {
				Map.Entry subE = (Map.Entry)subIt.next();
				String telNo = (String)subE.getKey();
				String name = (String)subE.getValue();
				System.out.println(name + " " + telNo);
			}
			System.out.println();
		}
	}
}

  Note) 실행결과

   - HashMap은 키와 값을 모두 Object타입으로 저장하기때문에 HashMap의 value로 HashMap을 다시 저장가능

     -> 하나의 키에 대해 다시 복수의 데이터를 저장 가능

  

   - 해싱과 해시함수

  Def) 해싱: 해시함수를 이용해서 데이터를 해시테이블레 저장하고 검색하는 기법  

    -> 저장되어 있는 곳을 알려주기 때문에 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

  1) 검색하고자 한느 값의 키로 해시함수를 호출한다.

  2) 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.

  3) 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

 

  - 배열의 인덱스가 n인 요소의 주소 = 배열의 시작 주소 + (type의 size) * n

 

  1.11 TreeMap

  - 이진 검색 트리의 형태로 key-value으로 이루어진 데이터를 저장한다. ("검색"과 "정렬"에 적합한 클래스)

    -> 정렬: Collentions.sort(list)

  - 검색에 대해서는 HashMap이 TreeMap보다 뛰어나다. 

 

  Ex)

<hide/>
package first;
import java.util.*;

public class TreeMapEx1 {
	public static void main(String[] args) {
		String[] data = {"A", "K", "A", "K", "D", "K", "A", "K", "K", "K", "Z", "D"};
		TreeMap map = new TreeMap();
		
		for(int i = 0; i < data.length; ++i) {
			if(map.containsKey(data[i])) {
				Integer value = (Integer)map.get(data[i]);
				map.put(data[i], new Integer(value.intValue()+ 1 ));
			}else {
				map.put(data[i], new Integer(1));
				
			}
			Iterator it = map.entrySet().iterator();
			
			System.out.println("=기본정렬=");
			while( it.hasNext() ){
				Map.Entry entry = (Map.Entry)it.next();
				int value = ((Integer)entry.getValue()).intValue();
				System.out.println(entry.getKey() + " : "  + printBar('*', value) + " " + value );
			}
			System.out.println();
			
			// map을 ArrayList로 변환한 다음에 Collections.sort()로 정렬
			Set set = map.entrySet();
			List list = new ArrayList(set);
			
			// static void sort(List list,  Comparator c)
			Collections.sort(list, new ValueComparator());
			
			it = list.iterator();
			
			System.out.println("=값의 크기가 큰 순서로 정렬=");
			while(it.hasNext()) {
				Map.Entry entry  = (Map.Entry) it.next();
				int value = ( (Integer)entry.getValue()).intValue();
				System.out.println(entry.getKey() + " : " + printBar( '#' , value) + " " + value);
				
			}
	
		}
	
	}
	static class ValueComparator implements Comparator {
		public int compare(Object o1, Object o2) {
			if(o1 instanceof Map.Entry && o2 instanceof Map.Entry) {
				Map.Entry e1 = (Map.Entry)o1;
				Map.Entry e2 = (Map.Entry)o2;
				
				int v1 = ((Integer)e1.getValue()).intValue();
				int v2 = ((Integer)e2.getValue()).intValue();
				return   v2- v1;		
			}
			return -1;
		}
	}	// static class ValueComparator implements Comparator
	
	public static String printBar(char ch, int value) {
		char [] bar = new char[value];
		for(int i = 0; i < bar.length; ++i) {
			bar[i] = ch;
		}
		return new String(bar);
	}
}

 

  Note) 실행결과

 

  1.12 Properties

  - Properties는 HashMap의 구버전인 HashTable을 상속 받아 구현한 것이다.

  - HashTable은 키와 값을 (Object, Object)의 형태로 저장한다.

  - Properties는 ( String, String )의 형태로 저장하는 단순화된 컬렉션이다.

  - 애플리케이션의 환경 설정과 관련된 속성을 저장하는데 사용된다.

   Ex)

<hide/>
package javaStudy;
import java.util.*;
public class PropertiesEx1 {
	public static void main(String[] args) {
		Properties prop = new Properties();
        
        // prop에 키와 값을 저장한다.
		prop.setProperty("timeout", "30");
		prop.setProperty("language", "kr");
		prop.setProperty("size", "10");
		prop.setProperty("capacity", "10");
        
        // prop에 저장된 요소들을 Enumeration을 이용해서 출력한다.
		Enumeration e = prop.propertyNames();
		while(e.hasMoreElements()) {
			String element = (String)e.nextElement();
			System.out.println(element + "=" + prop.getProperty(element) );
		}
		System.out.println();
		prop.setProperty("size", "20");	// size 값을 20으로 변경한다.
		System.out.println("size = " + prop.getProperty("size"));
		System.out.println("capacity = " + prop.getProperty("capacity", "20"));
		System.out.println("loadfactor = " + prop.getProperty("loadFactor", "0.75"));
		System.out.println(prop);	//prop에 저장된 요소들을 출력한다.
		prop.list(System.out);		//prop에 저장된 요소들을 화면(System.out)에 출력한다.
	}
}

  Note) 실행 결과

  - setProperty: put()메서드를 호출한다. 기존에 같은 키로 저장된 값이 있으면 그 값을 Object로 반환 (아니면 null반환)

  - Property는 HashTable을 상속받아 구현한 것이라 Map의 특성상 저장 순서를 유지하지 않는다. 

    -> 예제의 결과와 출력된 순서가 저장순서와는 무관함,

 

 

  Ex) 시스템 속성 가져오기

<hide/>
package javaStudy;
import java.util.Properties;
public class PropertiesEx4 {
	public static void main(String[] args) {
		Properties sysProp = System.getProperties();
		System.out.println("java.version :" + sysProp.getProperty("java.version"));
		System.out.println("user.language : " + sysProp.getProperty("user.language"));
		sysProp.list(System.out);
	}
}

  Note) 실행 결과

  - System클래스의 getProperties()를 호출하면 시스템과 관련된 속성이 저장된 Properties를 가져온다.

  - 원하는 속성은 getProperty()를 이용해서 얻는다.

 

 

  1.13 Collections

  - Arrays가 배열과 관련된 메서드를 제공하듯 Collections는 컬렉션 관련된 메서드를 제공한다.

    -> fill(), copy(), sort(), binarySearch() 는 두 클래스에 모두 포함된다.

  - 컬렉션의 동기화: 멀티 쓰레드 프로그래밍에서는 하나의 객체를 여러쓰레드가 동기에 접근할 수 있기 때문에 

    -> 데이터의 일관성(consistency)를 유지하기 위해 공유되는 객체에 동기화(synchronization)가 필요하다.

  - 싱글톤 컬렉션 만들기: 단 하나의 객체만을 저장하는 컬렉션을 만든다.

    -> 매개 변수로 저장할 요소를 지정하면 해당 요소를 저장하는 컬렉션을 반환한다. 

    -> 반환된 컬렉션은 변경할 수 없다.

  - 한 종류의 객체만 저장하는 컬렉션 만들기 

    -> 한 종류의 객체를 저장하며 컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한하고 싶을 때 이용한다.

 

  Ex)

<hide/>
package javaStudy;
import java.util.*;
import static java.util.Collections.*;
public class CollectionsEx {
	public static void main(String[] args) {
		List list = new ArrayList();
		System.out.println(list);
		
		addAll(list, 1, 2, 3, 4 ,5 );
		System.out.println(list);
		
		rotate(list, 2);	// 오른쪽으로 두 칸씩 이동
		System.out.println(list);

		swap(list, 0,  2);	// 첫번째와 세번짼는 교환(swap)
		System.out.println(list);
		
		shuffle(list);		// 저장된 요소 위치를 임의로 변경
		System.out.println(list);
		
		sort(list, reverseOrder() );	//역순 정렬
		System.out.println(list);
		
		sort(list);		// 정렬
		System.out.println(list);
		
		int idx = binarySearch(list, 3);	// 3이 저장된 위치, 인덱스를 반환
		System.out.println("index of 3 = " + idx );
		
		System.out.println("max = " + max(list) );
		System.out.println("min = " + min(list) );
		System.out.println("index of 3 = " + idx );
		
		fill(list, 9);
		System.out.println("list = " + list);
		
		// list와 같은 크기의 새로운 list를 생성하고 2fhcodnsek. 단, 결과는 변경불가
		List newList = nCopies(list.size(), 2);
		System.out.println("newList = " + newList);
		
		System.out.println(disjoint(list, newList)); 	// 공통 요소가 없으면 true
		
		copy(list, newList);
		System.out.println("newList = " + newList);
		System.out.println("list = " + list);
		
		replaceAll(list , 2, 1);
		System.out.println("list = " + list);
		Enumeration e = enumeration(list);
		ArrayList list2 = list(e);
		
		System.out.println("list2 = " + list2);
		
	}
}

  Note) 실행결과