자바 도전기 -17

이번에는 컬렉션 프레임웍을 공부한다

컬렉션 프레임웍

컬렉션 프레임웍이란, '데이터 군을 저장하는 클래스들을 표준화한 설계를 뜻한다. 컬렉션은 다수의 데이터, 즉 데이터 그룹을, 프레임웍은 표준화된 프로그래밍 방식을 의미한다.

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

인터페이스 List와 Set을 구현한 컬렉션 클래스들은 서로 많은 공통부분이 있어서, 공통된 부분을 다시 뽑아 Collection인터페이스를 정의할 수 있었지만 Map인터페이스는 이들과는 전혀 다른 형태로 컬랙션을 다루기 때문에 같은 상속계층도에 포함되지 못했다.

인터페이스	특징
List	순서가 있는 데이터의 집합, 데이터의 중복을 허용한다. 예) 대기자 명단 구현클래스 : ArrayList, LinkedList, Stack, Vector 등
Set	순서를 유지하지 않는 데이터의 집합, 데이터의 중복을 허용하지 않는다. 예) 양의 정수집합, 소수의 집합 구현클래스 : HashSet, TreeSet 등
Map	키(key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합 순서는 유지하지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다. 예) 우편번호, 지역번호(전화번호) 구현클래스 : HashMap, TreeMap, Hashtable, Properties 등

Vector나 Hashtable과 같은 기존의 컬렉션 크래스들은 호환을 위해, 설계를 변경해서 남겨두었지만 가능하면 사용하지 않는 것이 좋다. 그 대신 새로 추가된 ArrayList와 HashMap을 사용한다.

List인터페이스

List인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.

Set인터페이스

Set인터페이스는 중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용된다. Set인터페이스를 구현한 클래스로는 HashSet, TreeSet 등이 있다.

Map인터페이스

Map인터페이스는 키(key)와 값(value)을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용된다. 키는 중복될 수 없지만 값은 중복을 허용한다.
기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.
Map인터페이스를 구현한 클래스로는 Hashtable, HashMap, LinkedHashMap, SortedMap, TreeMap 등이 있다.

ArrayList

ArrayList는 컬렉션 프레임웍에서 가장 많이 사용되는 컬렉션 클래스일 것이다.
ArrayList는 List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.
ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다.
ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다.

import java.util.*;

public class VectorEx {
    public static void main(String[] args) {
        Vector v = new Vector(5); //용량이 5인 Vector 생성
        v.add("1");
        v.add("2");
        v.add("3");
        print(v);

        v.trimToSize();//빈 공간을 없앰(용량과 크기가 같아짐)
        System.out.println("===After trimToSize() ===");
        print(v);

        v.ensureCapacity(6);//용량을 6으로 지정
        System.out.println("===After ensureCapacity(6) ===");
        print(v);

        v.setSize(7);
        System.out.println("===After setSize(7) ===");
        print(v);

        v.clear();//v의 모든 요소를 삭제
        System.out.println("===After 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());
    }
}

LinkedList

배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간(접근시간, access time)이 가장 빠르다는 장점을 가지고 있지만 다음과 같은 단점도 가지고 있다

1. 크기를 변경할 수 없다

• 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야한다
• 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다

• 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
• 배열의 중간에서 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다

배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.
링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다

class Node{
	Node next;//다음 요소의 주소를 저장
    Object obj;// 데이터를 저장
}

링크드 리스트에서의 데이터 삭제는 간단하다. 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 된다.
단 하나의 참조만 변경하면 삭제가 이루어지는 것이다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.
새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.

링크드 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. 이 점을 보완한 것이 더블 링크드 리스트(이중 연결리스트, doubly linked list)이다.

더블 링크드 리스트는 단순히 링크드 리스트에 참조변수를 하나 더 추가하여 다음 추가에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.
더블 링크드 리스트는 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 더 많은 사용된다

class Node{
	Node next; //다음 요소의 주소를 저장
    Node previous; //이전 요소의 주소를 저장
    Object obj; //데이터를 저장
}

더블 링크드 리스트의 접근성을 보다 향상시킨 것이 '더블 써큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list)'인데, 단순히 더블 링크드 리스트이 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다.
마지막요소의 다음요소가 첫번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다.

1. 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다
2. 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다

배열의 경우 만일 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식을 계산함으로써 해결된다

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

LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야만 원하는 값을 얻을 수 있다.
LinkedList는 저장해야하는 데이터의 개수가 많아질수록 데이터를 읽어오는 시간, 즉 접근시간(access time)이 길어진다는 단점이 있다.

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠르다	느리다	순차적인 추가삭제는 더 빠름 비효율적인 메모리사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

Stack과 Queue

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어 있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다.
스택에는 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫 번째 데이터를 삭제하므로, ArrayList와 같은 배열기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다.
그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

Stack직접 구현하기

import java.util.*;

class MyStack extends Vector{
    public Object push(Object item){
        addElement(item);
        return item;
    }
    public Object pop(){
        Object obj = peek();//Stack에 저장된 마지막 요소를 읽어온다
        removeElementAt(size()-1);//배열의 index가 0부터 시작하므로 1을 빼준다
        return obj;
    }
    
    public Object peek(){
        int len = size();
        
        if(len==0){
            throw new EmptyStackException();
        }
        return elementAt(len-1);
    }
    
    public boolean empty(){
        return size() == 0;
    }
    
    public int search(Object o){
        int i = lastIndexOf(o);//끝에서부터 객체를 찾는다
        //반환값은 저장된 위치(배열의 index)이다.
        if(i>=0){//객체를 찾은 경우
            return size() - i;//Stack은 맨 위에 저장된 객체의 index를 1로 정의하기 때문에 계산을 통해서 구한다
        }
        return -1;
    }
}

스택과 큐의 활용

스택의 활용 예 - 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
큐의 활용 예 - 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)

PriorityQueue

Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다는 특징이 있다. null은 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다.
PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 '힙(heap)'이라는 자료구조의 형태로 저장한다.

import java.util.*;

public class PriorityQueueEx {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();
        pq.offer(3);
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);
        System.out.println(pq);

        Object obj = null;

        while((obj=pq.poll())!=null){
            System.out.println(obj);//1 2 3 4 5
        }
    }
}

우선순위는 숫자가 작을수록 높은 것이므로 1이 가장 먼저 출력된 것이다.

Deque(Double-Ended Queue)

Queue의 변형으로, 한 쪽 끝으로만 추가/삭제할 수 없는 Queue와 달리, Deque(덱, 또는 디큐라고 읽음)은 양쪽 끝에 추가/삭제가 가능하다.

Iterator, ListIterator, Enumeration

Iterator, ListIterator, Enumeration은 모두 컬렉션에 저장된 요소에 접근하는데 사용되는 인터페이스이다.

Iterator

컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator인터페이스를 정의한다.
iterator()는 Collection인터페이스에 정의된 메서드이므로 Collection인터페이스의 자손인 List와 Set에도 포함되어 있다. 그래서 List나 Set인터페이스를 구현하는 컬렉션은 iterator()가 각 컬렉션의 특징에 알맞게 작성되어 있다.

메서드	설명
boolean hasNext( )	읽어 올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환한다
Object next( )	다음 요소를 읽어 온다. next( )를 호출하기 전에 hasNext( )를 호출해서 읽어 올 요소가 있는지 확인하는 것이 안전하다
void remove( )	next( )로 읽어 온 요소를 삭제한다. next( )를 호출한 다음에 remove( )를 호출해야한다(선택적 기능)

List클래스들은 저장순서를 유지하기 때문에 Iterator를 이용해서 읽어 온 결과 역시 저장 순서와 동일하지만 Set클래스들은 각 요소간의 순서가 유지 되지 않기 때문에 Iterator를 이용해서 저장된 요소들을 읽어와도 처음에 저장된 순서와 같지 않다.

ListIterator와 Enumeration

Enumeration은 컬렉션 프레임웍이 만들어지기 이전에 사용하던 것으로 Iterator의 구버전이라고 생각하면 된다.
ListIterator는 Iterator를 상속받아서 기능을 추가한 것으로, 컬렉션의 요소에 접근할 때 Iterator는 단방향으로만 이동할 수 있는 데 반해 ListIterator는 양방향으로의 이동이 가능하다.

Enumeration : Iterator의 구버전
ListIterator : Iterator의 양방향 조회기능추가(List를 구현한 경우만 사용가능)

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();
    }
}

Iterator는 단방향으로만 이동하기 때문에 컬렉션의 마지막 요소에 다다르면 더 이상 사용할 수 없지만, ListIterator는 양방향으로 이동하기 때문에 각 요소간의 이동이 자유롭다.
다만 이동하기 전에 반드시 hasNext( )나 hasPrevious( )를 호출해서 이동할 수 있는지 확인해야 한다.

Arrays

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

copyOf( )는 배열 전체를, copyOfRange( )는 배열의 일부를 복사해서 새로운 배열을 만들어 반환한다.
copyOfRange( )에 지정된 범위의 끝은 포함되지 않는다.

int[] arr = {0,1,2,3,4};
int[] arr2 = Arrays.copyOf(arr, arr.length);//arr2=[0,1,2,3,4]
int[] arr3 = Arrays.copyOf(arr, 3);//arr3=[0,1,2]
int[] arr4 = Arrays.copyOf(arr, 7);//arr4 = [0,1,2,3,4,0,0]
int[] arr5 = Arrays.copyOfRange(arr, 2, 4);//arr5 = [2,3]<-4는 불포함
int[] arr6 = Arrays.copyOfRange(arr, 0, 7);//arr6 = [0,1,2,3,4,0,0]

배열 채우기 - fill( ), setAll( )

fill( )은 배열의 모든 요소를 지정된 값으로 채운다. setAll( )은 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다.
이 메서드를 호출할 때는 함수형 인터페이스를 구현한 객체를 매개변수로 지정하던가 아니면 람다식을 지정해야한다.

int[] arr = new int[5];
Arrays.fill(arr,9);//arr=[9,9,9,9,9]
Arrays.setAll(arr, () -> (int) (Math.random()*5)+1);//arr=[1,5,2,1,1]

setAll( )메서드는 람다식이 반환한 임의의 정수로 배열을 채운다.

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

sort( )는 배열을 정렬할 때, 그리고 배열에 저장된 요소를 검색할 때는 binarySearch( )를 사용한다.
binarySearch( )는 배열에서 지정된 값이 저장된 위치(index)를 찾아서 반환하는데, 반드시 배열이 정렬된 상태이어야 오라른 결과를 얻는다.
그리고 만일 검색한 값과 일치하는 요소들이 여러 개 있다면, 이 중에서 어던 것의 위치가 반환될지는 알 수 없다.

int[] arr = {3,2,0,1,4};
int idx = Arrays.binarySearch(arr, 2);//잘못된 결과

Arrays.sort(arr);//배열 arr을 정렬
System.out.println(Arrays.toString(arr));//[0,1,2,3,4]
int idx = Arrays.binarySearch(arr, 2);/idx=2

배열의 첫 번째 요소부터 순서대로 하나씩 검색하는 것을 '순차 검색(linear search)'이라고 하는데, 이 검색 방법은 배열이 정렬되어 있을 필요는 없지만 배열의 요소를 하나씩 비교하기 때문에 시간이 많이 걸린다.
이진 검색(binary search)은 배열의 검색할 범위를 반복적으로 절반씩 줄여가면서 검색하기 때문에 검색속도가 상당히 빠르다.
단, 배열이 정렬 되어 있는 경우에만 사용할 수 있다는 단점이 있다.

배열의 비교와 출력 -equals( ), toString( )

toString( )배열의 모든 요솔르 문자열로 편하게 출력할 수 있다.
toString( )은 일차원 배열에만 사용할 수 있으므로, 다차원 배열에는 deepToString( )을 사용해야 한다. deepToString( )은 배열의 모든 요소를 재귀적으로 접근해서 문자열을 구성하므로 2차원뿐만 아니라 3차원 이상의 배열에도 동작한다.

int[] arr = {0,1,2,3,4};
int[][] arr2D = {{11,22},{33,44}};
System.out.println(Arrays.toString(arr));//[0,1,2,3,4]
System.out.println(Arrays.deepToString(arr2D));//[[11,12],[21,22]]

equals( )는 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false를 반환한다. equals( )도 일차원 배열에만 사용가능하므로, 다차원 배열의 비교에는 deepEquals( )를 사용해야한다.

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

asList( )는 배열을 List에 담아서 반환한다. 매개변수의 타입이 가변인수라서 배열 생성없이 저장할 요소들만 나열하는 것도 가능하다.

List list = Arrays.asList(new Integer[]{1,2,3,4,5});//list=[1,2,3,4,5]
List list = Arrays.asList(1,2,3,4,5);//list=[1,2,3,4,5]
list.add(6);//UnsupportedOperationException 예외 발생

asList( )가 반환한 List의 크기를 변경할 수 없다는 것이다. 즉, 추가 또는 삭제가 불가능하다. 저장된 내용은 변경가능하다. 만일 크기를 변경할 수 있는 List가 필요하다면 다음과 같이 하면 된다.

List list = new ArrayList(Arrays.asList(1,2,3,4,5));

Comparator와 Comparable

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

public interface Comparator{
	int compare(Object o1, Object o2);
    boolean equals(Object obj);
}

public interface Comparable{
	public int compareTo(Object o);
}

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

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

HashSet

HashSet은 Set인터페이스를 구현한 가장 대표적인 컬렉션이며, Set인터페이스의 특징대로 HashSet은 중복된 요소를 저장하지 않는다.
HashSet에 새로운 요소를 추가할 때는 add메서드나 addAll메서드를 사용하는데, 만일 HashSet에 이미 저장되어 있는 요소와 중복된 요소를 추가하고자 한다면 이 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다.
ArrayList와 같이 List인터페이스를 구현한 컬렉션과 달리 HashSet은 저장순서를 유지하지 않으므로 저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야한다.

import java.util.*;

public class HashSetEx1 {
    public static void main(String[] args) {
        Object[] objArr = {"1",new Integer(1),"2","2","3","3","4","4","4"};
        Set set = new HashSet();

        for(int i=0;i<objArr.length;i++){
            set.add(objArr[i]);
        }

        System.out.println(set);//1,1,2,3,4
    }
}

결과에서 알 수 있듯이 중복된 값은 저장되지 않았다.
add메서드는 객체를 추가할 때 HashSet에 이미 같은 객체가 있으면 중복으로 간주하고 저장하지 않는다.
만일 중복을 제거하는 동시에 저장한 순서를 유지하고자 한다면 HashSet대신 LinkedHashSet을 사용해야 한다.

import java.util.*;

public class HashSetLotto {
    public static void main(String[] args) {
        Set set = new HashSet();

        for(int i=0;set.size()<6;i++){
            int num = (int)(Math.random()*45)+1;
            set.add(new Integer(num));
        }

        List list = new LinkedList(set);
        Collections.sort(list);
        System.out.println(list);
    }
}

import java.util.*;

public class HashSetEx4 {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        set.add(new String("abc"));
        set.add(new String("abc"));
        set.add(new Person2("David",10));
        set.add(new Person2("David",10));

        System.out.println(set);//[abc, David:10]
    }
}

class Person2{
    String name;
    int age;

    Person2(String name, int age){
        this.name = name;
        this.age = age;
    }

    public boolean equals(Object obj) {
        if(obj instanceof Person2){
            Person2 tmp = (Person2)obj;
            return name.equals(tmp.name) && age==tmp.age;
        }
        return false;
    }

    public int hashCode() {
        return (name+age).hashCode();
    }

    public String toString(){
        return name+":"+age;
    }
}

equals( )와 hashCode( )를 호출하기 때문에 equals( )와 hashCode( )을 목적에 맞게 오버라이딩해야 한다.

import java.util.*;

public class HashSetEx5 {
    public static void main(String[] args) {
        HashSet setA = new HashSet();
        HashSet setB = new HashSet();
        HashSet setHab = new HashSet();
        HashSet setKyo = new HashSet();
        HashSet setCha = new HashSet();

        setA.add("1");
        setA.add("2");
        setA.add("3");
        setA.add("4");
        setA.add("5");

        System.out.println("A = "+setA);

        setB.add("4");
        setB.add("5");
        setB.add("6");
        setB.add("7");
        setB.add("8");
        System.out.println("B = "+setB);

        Iterator it = setB.iterator();
        while(it.hasNext()){
            Object tmp = it.next();
            if(setA.contains(tmp)){
                setKyo.add(tmp);
            }
        }
        it=setA.iterator();
        while(it.hasNext()){
            Object tmp = it.next();
            if(!setB.contains(tmp)){
                setCha.add(tmp);
            }
        }
        it=setA.iterator();
        while(it.hasNext()){
            setHab.add(it.next());
        }
        it=setB.iterator();
        while(it.hasNext()){
            setHab.add(it.next());
        }

        System.out.println("A ∩ B = "+setKyo);
        System.out.println("A ∪ B = "+setHab);
        System.out.println("A - B = "+setCha);
    }
}

TreeSet

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.
이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조이다.
Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.
이진 트리(binary tree)는 링크드리스트처럼 여러 개의 노드(node)가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 '루트(root)'라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다.
위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하며 위의 노드를 부모 노드, 아래의 노드를 자식 노드라 한다.
하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다.

class TreeNode{
	TreeNode left;//왼쪽 자식노드
    Object element;//객체를 저장하기 위한 참조변수
    TreeNode right;//오른쪽 자식노드
}

이진 트리의 노드를 코드로 표현하면 다음과 같다.
이진 검색 트리(binary search tree)는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진트리이다.

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

import java.util.*;

public class TreeSetLotto {
    public static void main(String[] args) {
        Set set = new TreeSet();

        for(int i=0;set.size()<6;i++){
            int num = (int)(Math.random()*45)+1;
            set.add(num);
        }

        System.out.println(set);
    }
}

TreeSet은 저장할 때 이미 정렬하기 때문에 읽어올 때 따로 정렬할 필요가 없다

HashMap과 Hashtable

HashMap은 Map을 구현했으므로 앞에서 살펴본 Map의 특징, 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다.
해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉, (Object, Object)의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String을 대문자 또는 소문자로 통일해서 사용하곤 한다

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

키는 저장한 값을 찾는데 사용되는 것이기 때문에 컬렉션 내에서 유일(unique)해야 한다.
즉, HashMap에 저장된 데이터를 하나의 키로 검색했을 때 결과가 단 하나이어야 함을 뜻한다.

import java.util.*;

public class HashMapEx1 {
    public static void main(String[] args) {
        HashMap map = new 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.println("id :");
            String id = s.nextLine().trim();

            System.out.println("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;
            }
        }
    }
}

처음의 "asdf"의 값은 "1111"이었지만 "1234"로 덮었기 때문에 asdf는 1111일 때 오류가 나고 1234일 때 성공한 것이다

해싱과 해시함수

해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다.
해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다
해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable 등이 있다
해싱에서 사용하는 자료구조는 다음과 같이 배열과 링크드 리스트의 조합으로 되어 있다.
저장할 데이터의 키는 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다.

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

TreeMap

TreeMap은 이름에서 알 수 있듯이 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.
검색과 정렬에 적합한 컬렉션 클래스이다.
대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 다만, 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용하는 것이 좋다

Properties

Properties는 HashMap의 구버전인 Hashtable을 상속받아 구현한 것으로, Hashtable은 키와 값을 (Object, Object)의 형태로 저장하는데 비해 Properties는 (String, String)의 형태ㅐ로 저장하는 보다 단순화된 컬렉션클래스이다.
주로 애플리케이션의 환경설정과 관련된 속성(property)을 저장하는데 사용되며 데이터를 파일로부터 읽고 쓰는 기능을 제공한다.

import java.util.*;

public class PropertiesEx1 {
    public static void main(String[] args) {
        Properties prop = new Properties();

        //prop에 키와 값(key, value)을 저장한다
        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();
        System.out.println("size="+prop.get("size"));
        System.out.println("capacity="+prop.getProperty("capacity","20"));
        System.out.println("loadfactor="+prop.getProperty("loadfactor","0.75"));

        System.out.println(prop);
        prop.list(System.out);
    }
}

getProperty( )는 Properties에 저장된 값을 읽어오는 일을 하는데, 만일 읽어오려는 키가 존재하지 않으면 지정된 기본값을 반환한다