[Java] HashMap, LinkedHashMap, TreeMap, Hashtable 차이

'코딩인터뷰'와 '유튜브'를 참고하여 작성하였습니다.

HashMap, LinkedHashMap, TreeMap, Hashtable 네 가지 모두 키(key)에서 값(value)으로의 대응 관계가 있고 키를 기준으로 순회할 수 있다. 이 클래스들의 가장 큰 차이점은 시간 복잡도와 키가 놓이는 순서에 있다.

 

HashMap

• 검색과 삽입에 O(1) 시간이 소요된다.
• 키의 순서는 무작위로 섞여 있다.
• 구현은 연결리스트로 이루어진 배열로 되어 있다.
• null key와 null value를 모두 허용

LinkedHashMap

• 검색과 삽입에 O(1) 시간이 소요된다.
• 키의 순서는 삽입한 순서대로 정렬되어 있다.
• 구현은 양방향 연결 버킷(double-linked bucket)으로 구현되어 있다.

TreeMap

• 검색과 삽입에 O(log N) 시간이 소요된다.
• 키의 순서는 정렬되어 있다.
  • 즉, 키는 반드시 Comparable 인터페이스를 구현하고 있어야 한다.
• 구현은 레드-블랙 트리로 구현되어 있다.

Hashtable

• 검색과 삽입에 O(1) 시간이 소요된다.
• 키의 순서는 무작위로 섞여 있다.
• 구현은 연결리스트로 이루어진 배열로 되어 있다.

여기까지 HashMap과 동일

• null key와 null value 모두 불허
• 동기화를 지원한다. (thread safe)

따라서 Hashtable은 멀티스레드 환경에서 동작가능하며, 동기화를 지원하기 때문에 HashMap보다는 느리다.

 

 

코드

package Study;
 
import java.util.*;
 
public class Learn_Map {
 
    public static void main(String[] args) {
        HashMap<String, String> dictionary = new HashMap<String, String>();
//        Hashtable<String, String> dictionary = new Hashtable<>();
//        LinkedHashMap<String, String> dictionary = new LinkedHashMap<String, String>();
//        TreeMap<String, String> dictionary = new TreeMap<String, String>();
 
        dictionary.put("Brave", "ready to face and endure danger or pain; showing courage.");
        dictionary.put("Brilliant", "exceptionally clever or talented.");
        dictionary.put("Joy", "a feeling of great pleasure and happiness.");
        dictionary.put("Confidence", "the state of feeling certain about the truth of something");
 
        dictionary.put("Brilliant", "XXXXX");         // map cannot be used to store duplicates -> overriding (similar to Set)
 
//        for(String word: dictionary.keySet()){
//            System.out.println(word);                 // print Key
//            System.out.println(dictionary.get(word)); // print Value
//        }
 
        for(Map.Entry<String, String> entry: dictionary.entrySet()){
            System.out.println(entry.getKey());       // print Key
            System.out.println(entry.getValue());     // print Value
        }
 
    }
}
 

실행결과

왼 위 : HashMap 결과, 오 위 : Hashtable 결과, 왼 아래 : LinkedHashMap 결과, 오 아래 : TreeMap

keySet을 가져와서 key와 value를 출력할 수도 있으나 일반적으로 둘 다 출력이 필요한 경우 entrySet을 가져와서 출력하는것이 좋다고 한다.

HashMap과 Hashtable은 무작위로 출력이 되며, LinkedHashMap은 삽입한 순서대로 출력되며 TreeMap은 정렬되어 출력되는 것을 확인할 수 있다.

 

활용

이름과 Person이라는 객체 사이에 대응 관계를 만든다고 해 보자. 그리고 주기적으로 이름순으로 사람을 출력하고 싶다면 TreeMap을 사용하는 것이 좋다.

또한 TreeMap은 이름이 주어졌을 때 그다음 10명의 사람도 출력할 수 있다. 이는 많은 프로그램에서 사용하는 'More'기능을 구현할 때 유용할 수 있다.

LinkedHashMap은 삽입한 순서대로 키를 정렬하고 싶을 때 유용하다. 캐시를 구현할 때 가장 오래된 아이템을 먼저 삭제하고 싶은 경우에 유용할 수 있다.

결론

일반적으로 별다른 이유가 없으면 HashMap을 사용하는 것이 좋다. 일반적으로 빠르고 오버헤드가 적기 때문이다.

특별한 상황 즉, 삽입한 순서대로 키 정보를 얻고 싶다면 LinkedHashMap을 사용하면 되고, 정렬된 순서대로 키 정보를 얻고 싶다면 TreeMap, 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 Hashtable을 사용하면 된다.