[자바의 정석] ch11.9 ~ ch.11.11

TreeSet

- 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리

- 이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음

   각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)

 

LinkedList는 다음 요소 1개만 연결 

TreeNode는 2개의 노드 연결(Tree를 거꾸로 놓은것과 닮아서 Tree라 함)

 

이진 탐색 트리(binary search tree)

- 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장 

- 데이터가 많아질 수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가)

 

 

위의 예시에서 만약 5를 추가한다고 하면 

1. 7과 5를 비교

2. 4와 5를 비교

총 두번을 비교했는데 데이터가 많아질 수록 비교 횟수가 증가할 것임 

TreeSet - 데이터 저장과정 boolean add(Object o)

위와 같이 비교횟수가 점차 늘어남을 확인할 수 있다. 

 

TreeSet - 주요 생성자와 메서드 

 

TreeSet 예제

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

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

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

//            set.add(num);
//        }

        System.out.println(set);
    }
}

class Test implements Comparable {
    @Override
    public int compareTo(Object o) {
        return 1;
    }
}

class TestComp implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        return -1;
    }
}

TreeSet의 add를 할 때 비교 기준이 있어야 하므로 Test에 Comparable을 implements 하든지

TreeSet 생성자로 Comparator을 구현한 인스턴스를 추가하든지 해야한다. 

 

[알아두면 좋아요] 트리 순회(tree traversal)

- 이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

- 전위, 중위 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다.

TreeSet

장점  

1. 정렬

2. 범위검색

단점 

트리가 커질수록 추가, 삭제 시간이 많이 걸림

 

HashMap과 Hashtable - 순서x, 중복(키x, 값o)

- Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장

- HashMap(동기화x)은 Hashtable(동기화o)의 신버전

 

 

HashMap의 키(key)와 값(value)

- 해싱(hashing)기법으로 데이터를 저장. 데이터가 많아도 검색이 빠르다.

- Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장

 

해싱(hashing) 

- 해시함수(hash function)로 해시테이블(hash table)에 데이터를 저장, 검색 

- 해시테이블은 배열과 링크드 리스트가 조합된 형태 

해싱을 사용하는 클래스: Hashtable, HashMap, HashSet => hash code를 사용함 

해시 테이블 = 배열 + 링크드 리스트 

 

해시 테이블은 컬렉션 프레임웍이 도입되면서 HashMap으로 대체되었으나 이전 소스와의 호환성 문제로 남겨 두고 있다.

가능하면 Hashtable 대신 HashMap을 사용하도록 하자 

 

해싱(hashing)

 

해시맵 메서드 

예제 1

import java.util.HashMap;
import java.util.Scanner;

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

 

Map은 값은 중복을 허용하지만 키는 중복을 허용하지 않아서 {asdf : 1111} -> {asdf : 1234} 로 덮였다.

 

예제2

import java.util.*;

public class HashMapEx2 {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("정의진", 100);
        map.put("신민규", 90);
        map.put("고병서", 80);
        map.put("전창하", 70);

        Set set = map.entrySet(); // key, value 모두 가져오고 싶을 때 
        Iterator it = set.iterator(); // Collection에 저장되어 있는 요소들 순회할 때 쓰임 

        while(it.hasNext()){
            Map.Entry e = (Map.Entry) it.next();
            System.out.println("이름 : " + e.getKey()
                                    + ", 점수 : " + e.getValue());
        }

        set = map.keySet();
        System.out.println("참가자 명단 : " + set);

        Collection values = map.values();
        it = values.iterator();

        int total = 0;

        while(it.hasNext()){
            Integer i = (Integer) it.next();
            total += i.intValue();
        }

        System.out.println("총점 : " + total);
        System.out.println("평균 : " + (float)total/set.size());
        System.out.println("최고점수 : " + Collections.max(values));
        System.out.println("최저점수 : " + Collections.min(values));

    }
}

예제3 

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class HashMapEx3 {
    public static void main(String[] args) {
        String[] data = {"A", "K", "A", "K", "D", "K", "A", "K", "K", "K", "Z", "D"};

        HashMap map = new HashMap();

        for (int i = 0; i < data.length; i++) {
            if(map.containsKey(data[i])){
                int value = (int) map.get(data[i]);
                map.put(data[i], value + 1);
            } else {
                map.put(data[i], 1);
            } // 처음이면 1, 존재하면 기존 값 + 1

        }

        Iterator it = map.entrySet().iterator();

        while(it.hasNext()){
            Map.Entry entry = (Map.Entry) it.next();
            int value = ((int) entry.getValue());
            System.out.println(entry.getKey() + " : " + value);
        }
    }
}

 

TreeMap

이진 검색 트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장한다.

검색과 정렬에 적합한 컬렉션 클래스이다. 

 

검색에 관한한 대부분의 경우는 HashMap이 더 뛰어나므로 HashMap을 사용하는 것이 좋고

범위 검색이나 정렬이 필요할 때는 TreeMap이 유용하다.

 

위의 HashMap 예제 3번에서 

HashMap을 TreeMap으로 바꾸면 

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapEx {
    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])){
                int value = (int) map.get(data[i]);
                map.put(data[i], value + 1);
            } else {
                map.put(data[i], 1);
            } // 처음이면 1, 존재하면 기존 값 + 1

        }

        Iterator it = map.entrySet().iterator();

        while(it.hasNext()){
            Map.Entry entry = (Map.Entry) it.next();
            int value = ((int) entry.getValue());
            System.out.println(entry.getKey() + " : " + value);
        }
    }
}

key가 String 이므로 알파벳 순으로 정렬된 것을 알 수 있다(정렬에 유용)