HashMap, TreeMap 그리고 LinkedHashMap의 차이

최근 어떤 기회로 TreeMap과 HashMap은 어떤 차이가 있는지에 대한 질문을 받았다.

과거 Java 책에서 관련 내용을 본 적은 있으나 잘 기억이 나질 않았다. 특별한 경우를 제외하고는 HashMap을 주로 사용했기 때문에 크게 관심 두지 않았던 것 같다.

(Java 개발자라 칭하면서도 기본적인 것을 놓치고 있었던 것에 반성해 본다.)

그래서 한 번 정리해 본다.

Java에는 Collection이라는 이름하에 Map, List, Set이 있다. 그 중에서도 Map에 대해서 정리해 보고자 한다.(JDK 1.8 기준)

Map이란?

key-value 형식의 데이터를 저장할 수 있는 자료 구조이다. Java 개발자라면 HashMap을 자주 사용할 것이다.

Map은 인터페이스로 아래와 같이 선언되어 있다.

public interface Map<K,V> { int size(); boolean isEmpty(); boolean containsKey(Object key); boolean containsValue(Object value); V get(Object key); V put(K key, V value); V remove(Object key); void putAll(Map<? extends K, ? extends V> m); }

(각 메서드의 역할에 대해서는 설명하지 않을 것이다. Interface 명세만 열어보아도 기능은 확인할 수 있다.)

그렇다면 Map 인터페이스를 구현한 구현체에는 어떤 것들이 있을까?

답은 수도 없이 많다. 그 중 주로 사용하는 HashMap이 있다.

여기서는 TreeMap, HashMap, LinkedHashMap, HashTable(HashMap과 차이를 확인하기 위함)에 대해서 알아 볼 것이다.

HashMap

Java 개발자라면 아마도 Map을 이야기할 때 HashMap을 주로 생각할 것이다. 

HashMap은 내부적으로 Entry<K,V>[] Entry Array로 구성되어 있다. Array의 index를 hash 함수를 통혜 계산한다.

 

위 그림처럼 Entry로 저장이 되는데, 내부적으로 Hash 값에 의해 어떤 Bucket에 담길지 결정이 된다.

만약 Hash 값이 같다면 같은 Bucket에 List로 연결될 것이다.(마치 LinkedList처럼 Entry 안에 next Entry를 저장하는 변수가 있음)

Hash 값을 이용하여 저장하기 때문에 순서를 보장하지 않는다. get() 메서드는 Hash 값으로 해당 Array에 바로 접근이 가능하기 때문에 성능은 O(1)으로 빠르다.

TreeMap

TreeMap은 HashMap과 다르게 Entry가 Tree 구조로 저장되어 있는 것이 특징이다.

위 그림처럼 Tree 구조를 가지는데, Tree 구조 특성상 특정 Entry를 접근하려면 O(logn) 성능을 보인다.

TreeMap은 SortedMap 인터페이스를 구현하고 있어 Key 값을 기준으로 정렬이 되어 있는데, 이는 Comparator를 구현하여 정렬 순서를 변경할 수 있다.

LinkedHashMap

큰 흐름에서는 HashMap과 동일하다. 하지만 Entry 내에 before, after Entry가 저장되어 있는 것이 특징이다.(아래 코드 참고)

static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

이를 통해 입력(put 메서드) 순서를 보장할 수 있게 된다.

HashTable

Map 인터페이스를 구현한 클래스로 중복을 허용하지 않는다. 또한 동기화(synchronized) 처리가 되어 있어 Thread-safe 하다는 특징이 있다.

HashMap과는 다르게 Key 값으로 null을 허용하지 않는 것이 특징 중 하나이다.

public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; }

결론

대부분의 Java 개발자가 HashMap을 주로 사용하는 이유는 get() 메서드의 성능이 O(1)로 빠르기 때문인 것 같습니다. 특별한 이유가 없다면 get() 성능이 빠른 HashMap을 사용하자. 순서 보장이 필요하다면 TreeMap이나 LinkedHashMap을 고려해 볼 수도 있다. 

만약 동기화 이슈가 있다면 HashTable도 고려할 수 있다. 다만 동기화 수준에 따라 ConcurrentHashMap을 사용해도 성능 상 효과를 볼 수 있을 것이다.

(HashMap, HashTable, ConcurrentHashMap 3가지는 동기화 처리에서도 그 차이가 있다. 다음 기회에 정리해 보기로 한다.

첨부된 이미지에 대해서 구글링에서 얻은 이미지로 출처를 밝히지 못했습니다. 혹시 문제가 된다면 댓글 남겨 주시면 삭제하도록 하겠습니다.

---

참고

• http://rangken.github.io/blog/2015/java.map/
  
• http://www.albumbang.com/board/board_view.jsp?board_name=free&no=125
  
• http://egloos.zum.com/pelican7/v/881589
  
• http://www.programcreek.com/2013/03/hashmap-vs-treemap-vs-hashtable-vs-linkedhashmap/
  
• http://gnujava.com/board/article_view.jsp?article_no=7081&menu_cd=14&board_no=1&table_cd=EPAR01&table_no=01
  
• http://blog.lauramamina.com/article?title=map
  
• http://blog.leekyoungil.com/?p=159
  
• http://d2.naver.com/helloworld/831311