자료구조(Java) - Collection Framework 2

 

이전 포스팅에 이어서 Map 인터페이스를 구현한 Collection Class들에 대해서 소개한다.

 

 

④ HashTable, HashMap, TreeMap

 

HashTable은 Map 인터페이스를 구현한 Key - Value 쌍을 저장할 수 있는 형태의 Collection Class 이다.

다른 Collection Class도 그러하지만, Map 형태의 자료에서는 Key 또는 Value에 Null 이 아닌 값만 저장할 수 있다. HashTable은 아직 설명하지 않았지만 HashMap과 매우 유사하다. 

 

마치 Vector가 ArrayList와 비슷한 형태를 띄듯이 HashTable과 HashMap의 관계도 비슷하다고 볼 수 있다.

HashTable은 Java 1.0 에서부터 지원되었던 Class로 HashMap과 달리 Thread-Safe(Synchronized) 방식을 사용해 성능적으로 영향이 있다.

요즘에는 거의 사용되지 않는 방식으로 기존 코드와의 호환성을 위해 남아있으므로 HashMap을 사용하도록 하자

 

HashMap은 Map 인터페이스를 구현한 Collection Class 중 가장 많이 사용되는 클래스로 이전 포스팅에서 설명한 Hash 알고리즘을 사용하여 요소를 Key - Value 형태로 저장한다.

Key - Value 형태라는 것은 기본적으로 Key는 중복될 수 없는 값이어야 한다. 그 Key에 대응하는 Value는 원시(Primitive) 타입이거나 Object 타입일 수 있어 다양한 Collection Class 구조를 Key에 대응시켜 저장할 수도 있다.

Key만 서로 중복되지 않으면 되기 때문에 Key가 다르다면 동일한 Value라고 하더라도 얼마든지 저장하는 것이 가능하다. 아래 코드를 통해 HashMap 사용법을 확인해보자.

package com.test;


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

public class ArrayListTest {
    public static void main(String[] args){
        Map<String, Integer> map = new HashMap<>();
        map.put("first", 10);
        map.put("second", 20);
        map.put("third", 30);
        map.put("fourth", 40);
        map.put("fifth", 50);

        // Key 값의 집합을 이용해 반복하여 출력해보기
        System.out.println("Key 집합 : " + map.keySet()); // Key 집합 : [third, fifth, fourth, first, second]
        for(String key : map.keySet()){
            System.out.println("Key : " + key + ", Value : " + map.get(key));
        }

        // Iterator 반복자를 이용해 출력해보기
        Iterator<String> keys = map.keySet().iterator();
        while(keys.hasNext()){
            String key = keys.next();
            System.out.println("Key : " + key + ", Value : " + map.get(key));
        }

        // EntrySet을 이용해 출력해보기
        // 밑에선 반복자 Iterator를 사용하지 않았는데, entrySet()도 Iterator를 쓸 수 있다.
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for(Map.Entry<String, Integer> entry : entries){
            System.out.println("Key : " + entry.getKey() + ", Value : " + entry.getValue());
        }
    }
}


// 각 출력방식의 결과는 동일(순서는 유지되지 않음)
Key : third, Value : 30
Key : fifth, Value : 50
Key : fourth, Value : 40
Key : first, Value : 10
Key : second, Value : 20

 

위와 같이 사용하여 Key - Value 쌍의 요소를 HashMap에 저장할 수 있다.

keySet() 메소드를 통해 Key들의 값만 결과를 얻어낼 수도 있으며, 위와 같이 여러 가지 방법으로 출력한 것을 확인할 수 있다. 위는 keySet의 Iterator 반복자를 사용하였고 아래는 entrySet이라는 객체를 사용하였다.(entrySet도 Iterator 반복자 객체를 사용할 수는 있다.)

 

entrySet은 Key / Value를 한 번에 뽑아서 반환하여 가져오는데, keySet은 Key 값만 반환하여 Value를 찾으려면 get() 메소드를 통해 Value를 반환하는 한 번의 과정을 더 거쳐야 한다. 일반적으로 entrySet의 성능이 더 좋은것으로 알려져 있다.

참고로 위의 결과에서 순서가 삽입된 순서를 유지하지 않고 있는데 삽입 순서가 유지되어야 한다면 LinkedHashMap Collection Class를 사용하면 된다.

 

 

TreeMap은 동일하게 키(Key) 값(Value) 쌍을 저장하는데 이진 검색 트리(Binary search Tree)의 형태로 저장하는 자료구조 방식이다.

TreeMap은 HashMap과 다르게 Natural Ordering 방식을 통해 순서를 유지하여 구현된다. 이는 HashMap과 달리 SortedMap을 상속하는 NavigableMap 인터페이스를 구현하였기 때문이다.

 

TreeMap은 이진 검색 트리 중에서도 성능이 매우 좋은 Red-Black Tree를 이용하여 구현하였다.

기본적으로 이진 검색 트리는 O(logn)의 시간 복잡도를 가지지만 TreeMap은 순서를 유지하는 과정이 필요하여 O(nlogn)의 시간복잡도를 갖는 형태로 자료구조를 사용할 수 있다. 이에 대한 설명은 아래에서 추가로 하고 우선 코드를 통해 사용방법을 알아본다.

 

package com.test;


import java.util.*;

public class ArrayListTest {
    public static void main(String[] args){
        Map<String, Integer> map = new TreeMap<>();
        map.put("first", 10);
        map.put("second", 20);
        map.put("third", 30);
        map.put("fourth", 40);
        map.put("fifth", 50);

        // Key 값의 집합을 이용해 반복하여 출력해보기
        System.out.println("Key 집합 : " + map.keySet()); Key 집합 : [fifth, first, fourth, second, third]
        for(String key : map.keySet()){
            System.out.println("Key : " + key + ", Value : " + map.get(key));
        }

        // Iterator 반복자를 이용해 출력해보기
        Iterator<String> keys = map.keySet().iterator();
        while(keys.hasNext()){
            String key = keys.next();
            System.out.println("Key : " + key + ", Value : " + map.get(key));
        }

        // EntrySet을 이용해 출력해보기
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for(Map.Entry<String, Integer> entry : entries){
            System.out.println("Key : " + entry.getKey() + ", Value : " + entry.getValue());
        }

        // 전달된 키와 같거나 전달된 키보다 큰 키 중 가장 작은 키 반환(없으면 null)
        System.out.println(((TreeMap<String, Integer>) map).ceilingKey("second")); // second
        System.out.println(((TreeMap<String, Integer>) map).ceilingKey("tttt"));  // null

        // 전달된 키와 같거나 전달된 키보다 작은 키 중 가장 큰 키 반환(없으면 null)
        System.out.println(((TreeMap<String, Integer>) map).floorKey("second")); // second
        System.out.println(((TreeMap<String, Integer>) map).floorKey("tttt"));  // third
        System.out.println(((TreeMap<String, Integer>) map).floorKey("fafa"));  // null

        // 현재 Tree 내 가장 작은 키 반환
        System.out.println(((TreeMap<String, Integer>) map).firstKey()); // fifth

        // 현재 Tree 내 가장 큰 키 반환
        System.out.println(((TreeMap<String, Integer>) map).lastKey()); // third
    }
}

//결과
Key : fifth, Value : 50
Key : first, Value : 10
Key : fourth, Value : 40
Key : second, Value : 20
Key : third, Value : 30

 

사용법이 HashMap과 다를 것이 없다. 그런데 정렬 상태를 Natural Ordering으로 한다더니 왜 순서가 저 모양이냐고 묻는다면, String 형태의 Key값을 기반으로 정렬하기 때문이다.

잘 보면 Key값이 사전 순서대로 정렬되어 있는 것을 알 수 있다.(죄송합니다. 더 좋은 예제를 들어야 했는데..)

TreeMap은 HashMap과 다르게 더욱 유용한 몇 가지 Method를 제공하는데 그에 대한 코드를 위에서 보면 floorKey, firstKey, lastKey, ceilingKey 등이 있는데 그에 대한 주석을 살펴보면 내용을 알 수 있다.

 

간단히, ceilingKey method를 보면 전달된 키와 같거나 그 보다 큰 것 중 가장 작은 것을 반환하는데 "second"를 전달했을 때는 그와 동일한 것이 존재하여 "second"가 반환된 것이고 "tttt"라는 것을 전달했을 때는 "third"가 가장 큰 키인데 그보다 "tttt"가 사전 순서에서 더 큰 값이므로 null을 반환한 것이다. 이와 같은 방식으로 다른 method들도 이해해보길 바란다.

 

 

기타 참고

 

1. 이진 트리(Binary Tree)

 

이진 트리는 Node 기반(연결리스트)기반의 자료구조중 하나이다. 물론 배열(Array)로도 구현이 가능하다.

이진 트리는 하나의 Node가 2개의 Pointer를 갖고 있다고 보면 된다. 그런데 이전 포스팅에 설명한 Previous / Next의 Pointer가 아니라 Sub Node 2개를 갖고 있는 형태라고 볼 수 있다.

Left / Right라는 2개의 Sub Node를 갖고 해당 Sub Node(또는 Child Node)의 Pointer를 갖는 것이 Parent Node(부모 노드)의 형태로 구성된 자료 구조 이다. 그림으로 이해해보자.

 

Binary Tree의 형태

 

위와 같이 각각의 Node가 Sub Node 2개를 갖고 있는 형태의 자료구조를 이진 트리라고 한다. 제일 상단의 Node는 Root Node라고 하며, Sub Node를 갖지 않는 가장 아래의 Node는 Leaf Node라고 부른다.

그래서 더 정확한 정의는 "Leaf가 아닌 모든 Node가 1개 이상 2개이하의 Sub Node를 갖는 형태"가 될 것이다.

Root Node가 홀로 존재하더라도 동시에 Leaf Node가 되어 그 또한 이진 트리이며, Node3이 없이 Node2만 갖고 있더라도 그 또한 이진 트리의 형태이다.

 

Node2를 Root Node로 보고 이진 트리 안의 이진 트리를 별도로 바라볼 수도 있다. 그 또한 이진 트리이며 전체 이진 트리의 Sub 이진 트리로 판단할 수 있다. 여기서 알 수 있듯이 이진 트리는 재귀적인 성향을 갖는다고 볼 수 있다.

각 Node의 상단에 1 ~ 7까지의 숫자를 적어놓았는데, 이것을 배열의 Index라고 본다면 배열로도 구현할 수 있다는 의미이다.

배열로 구현한다면 Root Node를 1로 시작하여 그 Sub Node들은 Parent Node를 기준으로 Left Sub는 Parent Node Index * 2가 되고 Right Sub는 Parent Node Index * 2 + 1 이 될 것이다.

이와 같은 방식으로 구현하는 것 또한 가능하다.

 

 

2. 이진 검색 트리(Binary Search Tree)

 

이진 검색 트리는 이진 트리 중에서도 Node에 저장되어 있는 특정 비교 가능한(Comparable) 값이 순차적으로 저장되어 있는 Tree를 의미한다. 예를 들어 상단의 그림에서 Node에 값을 부여하여 아래와 같이 생성하였다고 생각해본다.

 

이 이진 트리는 부모(Parent) 노드를 기반으로 좌측에는 더 작은 Key값(여기서는 숫자)이, 우측에는 더 큰 Key값이 저장되어 있는 것을 알 수 있다.

만약 특정 값을 검색해야 한다면 기존의 연결리스트(LinkedList)방식에서는 전체 Node를 다 탐색해야 하는 경우가 있을 수 있어 시간 복잡도가 O(n)으로 발생할 수 있다.

그러나 이진 검색 트리는 단계가 내려갈 수록 2로 나누어져 전체 탐색의 범위가 줄어들기 때문에 O(logn)의 시간 복잡도를 기준으로 탐색이 가능하다는 장점이 있다.

 

 

3. 편향 트리, 완전 이진 트리, 포화 이진 트리

 

편향 트리는 말 그대로 한 쪽으로만 편향되어서 Tree가 구성된 형태를 의미한다. 쉽게 말해 Root Node가 있고 그 아래로 계속 Left Sub Child Node만 존재하는 식으로 구성이 되었다고 생각해보자.

이렇게 되면 이진 트리의 장점인 탐색 시간을 줄이는 효과를 볼 수 있을까? 그냥 선형 연결리스트와 다를 바가 전혀 없다. 그래서 이러한 현상을 방지하고자 여러 균형 트리 형태의 자료구조가 개발되었다.

 

균형(Balanced) 트리의 종류

① AVL Tree
  - 제일 초기에 균형을 제시한 형태의 구조
  - Adelson-Velskii와 E.M Landis가 논문을 발표하여 그 이름을 따서 구성.
  - 각 노드가 Left Sub Tree의 높이를 Right Sub Tree 높이로 뺀 균형치(Balanced Factor)를 보유
  - 해당 Factor 기반, 높이 사이의 균형 차이를 계산하여 부적절한 경우 Tree를 회전시켜서 균형 조절

② B-Tree
  - Binary가 아닌 Trinary Tree 구조(3개까지 Sub node 보유)
  - Sub Node가 짝수 / 홀수이냐에 따라 알고리즘이 다르다.
  - 전체 Tree의 높이 값과 Sub Node의 수에 따라 균형을 조절하는 알고리즘으로 구성됨

③ B+Tree / B*Tree
  - B-Tree가 좀 더 확장된 구조. 상용 DB 내 파일 구조에서 많이 쓰인다.

④ Red-Black Tree
  - Node에 색상 Property를 부여하여 색상 규칙에 따라 규칙에 부합하지 않으면 균형을 조절하는 방식
  - 현재 까지 고안된 균형 이진 탐색 트리 중 가장 성능이 좋다고 알려짐

균형 트리의 알고리즘은 상당히 복잡한 구조를 띤 경우가 많아 별도로 기회가 되면 포스팅 하도록 하겠습니다. 여기서는 저러한 구조를 별도로 만들었다는 사실만 알고 넘어가겠습니다.

완전 이진 트리(Complete Binary Tree)는 균형 트리 중 모든 Leaf가 좌측부터 빼곡히 채워져 있는 경우를 의미한다.
포화 이진 트리(Perfect Binary Tree)는 큔형 트리 중 모든 Leaf를 제외한 Node가 2개의 Sub Node를 보유한 경우를 의미한다.

즉, 포화 이진 트리는 완전 이진 트리이다. 만약 균형 트리라도 중간에 한 Node가 Right Sub Node만 갖고 Left는 없다면 완전 이진 트리가 아니다. 다시 아래의 그림을 보자

 

이 Tree는 포화 이진 트리인가? 그렇다. 그렇기에 완전 이진 트리 또한 성립한다. 만약 위의 그림에서 13의 값을 가진 Node를 제거한다면 어떨까?

 

그렇다면 그 Tree는 포화 이진 트리인가? 그렇지 않다. 그렇다면 완전 이진 트리인가? 그렇다.

상단에서 말한 조건 처럼 왼쪽부터 Sub Node들이 모두 빼곡히 채워져 있다면 완전 이진 트리인데, 10의 Parent Node가 Right Sub Node를 갖고 있지 않기 때문에 포화 이진 트리는 아닌 것이다. 한 번 더 아래의 그림을 보자.

 

 

위 Tree는 포화 이진 트리 인가? 아니다. 완전 이진 트리 인가? 역시 아니다. 중간에 Left Sub Node가 없어 빼곡히 채워지지 않았고 모든 Leaf를 제외한 Node가 2개의 Sub Node를 갖지 못하였기 때문이다.

간단히 완전 이진 트리와 포화 이진 트리의 성질을 설명하고 이번 포스팅을 마치도록 하겠다.

완전 이진 트리의 높이가 h라면, 노드의 수는 2^h 이상, 2^(h+1) 미만의 개수를 갖는다. 즉, 노드 개수가 K라면 높이는 floor(logK)가 된다. 만약 6이면 log6 = 2.xxx 이므로 높이가 2이다.
포화 이진 트리의 높이가 h라면, 노드의 수는 2^h 개이다.

위와 같은 성질에 의해서 균형 트리일 때, 탐색의 시간 복잡도는 최악일 때 O(logN)이 되는 것이다.

 

 

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.