Java - HashMap, LinkedHashMap, TreeMap 차이

Map이란?

 

지난 시간에는 List들에 대해서 알아보았다. 오늘은 Collection 중에 Map에 대해서 알아보도록하겠다. Map은 Key: Value 쌍으로 정의되는 자료구조이다. 예를 들면 { a: 1, b: 2 } 와 같은 형식으로 만들어진다. key는 보통 string이 사용되고 value에는 어떤 값이든 상관없이 사용할 수 있다. Java에서는 Map에 추가, 수정은 put() 함수, 읽기는 get() 함수를 사용한다. Map에 들어있는 원소들은 Entry라고 불리는데 EntrySet()이라는 함수를 사용하면 원소들의 Set을 얻어서 loop를 돌릴 수도 있다. Map은 키값이 유니크한 특징을 가지고 있어서 중복되지 않게 값을 덮어씌우거나 컨트롤 할 수 있다. 

 

Java에서는 3가지의 Map 구현체를 가지고 있는데 HashMap, LinkedHashMap, TreeMap이 있다. List 처럼 각각 조금씩 다르게 구현돼있어서 상황에 따라 잘 사용해야 불필요한 퍼포먼스 저하를 막을 수 있는데 각각의 특징에 대해서 알아보도록하겠다. 

 

HashMap

 

해시테이블 출처: hwamoc.log

Map을 생각없이 사용하다보면 가장 많이 쓰는 것은 HashMap이 아닐 수 없다. 개발자들이 가장 많이 사용하는 Map이 아닐까 싶다. HashMap은 HashTable을 사용해서 Entry 배열을 내부적으로 관리한다. HashMap은 이름 그대로 Hash 값을 이용한다. 예를 들어서 key가 "abc"라고 한다면 "abc"를 해시코드로 계산했을 때 5로 바꿀 수 있다고 치면 Entry 배열의 5번째 index에 value를 저장하는 것이다. Hash 값을 계산하는 방법은 Java 버전에 따라서 조금씩 차이가 있다고 한다. 또 Hash Collision을 대비해서 equals() 메소드까지 사용해서 정확하게 비교하는 과정을 거친다. HashMap은 Hash를 사용하기 때문에 읽는데 O(1)의 시간복잡도를 갖는다.

 

HashMap의 EntrySet을 돌려보면 넣은 순서대로 값을 얻을 수가 없는 이유도 Hash를 사용하기 때문이다. key의 hash값에 따라서 배열에 넣기 때문에 먼저 넣은 값의 Hash값이 크면 배열 뒤쪽에 위치하게 되는 것이다. 혹시나 순서를 중요시 한다면 다음에 소개할 LinkedHashMap을 사용하길 바란다.

 

LinkedHashMap

LinkedHashMap은 HashMap의 특징을 모두 상속받은 것에 추가로 순서를 보장이 필요할 때 사용할 수 있는 Map이다. LinkedHashMap은 내부적으로 HashTable과 LinkedList로 구현되어 있다. HashTable은 HashMap의 기능을 동일하게 하기 위해 HashMap에서 상속 받은 기능이고 추가적으로 LinkedList를 만들어서 저장하고 있다. put, get 등의 메소드들은 모두 HashMap의 메소드를 쓰고있고 새로운 원소를 추가할 때 LinkedList의 맨 뒤에 추가해주는 로직이 더해져있다.

정리하면 HashMap의 HashTable은 그대로 사용하고 순서용 + @로 LinkedList를 하나 더 가지고 있다고 생각된다.

 

LinkedHashMap의 코드를 들여다보면 EntrySet() 메소드 안에 loop를 해주는 forEach 함수가 있는데 다음과 같이 연결된 Entry들을 순서대로 iterate하는 것을 확인해볼 수 있다.

 

public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
    if (action == null)
        throw new NullPointerException();
    int mc = modCount;
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
        action.accept(e);
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

 

반면에 HashMap은 HashTable에서 가져와서 처음 index부터 보여주기 때문에 순서가 보장되지 않는다.

 

public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
    Node<K,V>[] tab;
    if (action == null)
        throw new NullPointerException();
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e);
        }
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

 

사실 HashTable이 무엇인지 알아야 이해가 가는 글인데 추후에 HashTable에 대해서 포스팅하도록하겠다.

TreeMap

 

출처: https://seeminglyjs.tistory.com/227

TreeMap은 Tree를 사용한 Map이라고 보면 된다. 좀 더 정확히는 Java에서는 Red-Black Tree를 사용하고 있다. RB Tree는 트리의 한 부분만 비대해지는 것을 막아서 언제나 O(logN)의 성능을 유지시켜준다. 한쪽이 치우쳐서 O(N)까지 성능이 떨어진 이진 탐색 트리의 단점을 보완한다. 트리는 부모를 기준으로 왼쪽에 값이 작은 원소 오른쪽에 값이 큰 원소를 저장한다. TreeMap의 특징은 자동으로 key값에 따라서 오름차순으로 정렬이 된다는 것이다. 원소를 삽입, 삭제 할 때 마다 정렬이 이뤄지기 때문에 HashMap이나 LinkedHashMap의 조회속도는 비교가 되지 않을 만큼 느리다. 따라서 정렬된 상태를 유지해야하거나 정렬된 데이터를 조회할 때 사용하면 좋다.