[Map] TreeMap 이론 및 코드 정리

•TreeMap 클래스는 키와 값을 한 쌍으로 하는 데이터를 이진 검색 트리(binary search tree)의 형태로 저장합니다.

레드-블랙 트리(Red-Black Tree)

•TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있습니다.

 

•레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍니다..

 

• TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다.

 

•정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Etnry 객체를 저장합니다.

 

• TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어집니다.

 

• TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸립니다.

 

하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋습니다

 

•정렬된 상태로 데이터를 조회하는 경우가 빈번하다면, 데이터를 조회할 때 정렬해야 하는 hashMap보다는 이미 정렬된 상태로 저장되어 있는 TreeMap이 빠른 조회결과를 얻을 수 있다.

 

•위의 설명을 정리하면 HashMap을 사용하고, 정렬이나 범위검색이 필요한 경우에만 TreeMap을 사용하는 것이 좋다.

 

•TreeMap 클래스는 Map 인터페이스를 구현하므로, 중복된 키로는 값을 저장할 수 없습니다.하지만 같은 값을 다른 키로 저장하는 것은 가능합니다.

 

장단점

•이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠릅니다

•Map의 장점인 빠른 검색과 Tree의 장점인 정렬과 범위검색의 장점을 모두 갖고 있다.

이진검색트리처럼, 데이터를 저장할 때 정렬하기 때문에 저장시간이 길다는 단점이 있다

 

log

192.168.0.1 20210517000000 /main.do 200
192.168.0.1 20210517000000 /login.do 200
192.168.0.2 20210517000000 /main.do 200
192.168.0.2 20210517000000 /login.do 200
192.168.0.2 20210517000000 /login.do 200
192.168.0.3 20210517000000 /main.do 200
192.168.0.3 20210517000000 /main.do 200
192.168.0.3 20210517000000 /login.do 200
192.168.0.4 20210517000000 /main.do 500
192.168.0.4 20210517000000 /login.do 500

 

 

package HashMap_ex;

import sun.reflect.generics.tree.Tree;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapTest {
    public static void main(String[] args) {
        try {
            Map<String, Integer> map = new TreeMap<>();
            String filePath = "C:\\Users\\최민준\\Desktop\\AccessLog_sample\\access.log";

            FileReader fileReader = new FileReader(filePath);
            BufferedReader bufferedReader = new BufferedReader(fileReader);

            String line;
            while ((line = bufferedReader.readLine()) != null) {
                String[] outPutLine = line.split(" ");
                String ip = outPutLine[0];

                if (!map.containsKey(ip)) {
                    map.put(ip, 0);
                }
                map.put(ip, map.get(ip) + 1);
            }

            for (Map.Entry<String, Integer> key : map.entrySet()) {
                System.out.println("key 값 : " + key.getKey() + " | " + "Value 값 : " + key.getValue());
            }

        } catch (FileNotFoundException e) {
            System.out.println("파일을 찾을수 없다.");
        } catch (IOException e) {
            System.out.println(e);
        }
    }
}