TreeMap vs HashMap vs LinkedHashMap

개요

---

 Java의 Collections 중에 Map이 있습니다. 평소에는 코딩 테스트에서 HashMap만 주로 사용하다보니 다른 Map은 접할 기회가 적었는데, 이번 시간에 한번 정리해보겠습니다.

 

 

 

목차

 Map의 특징
key 저장순서
Map 종류별 특징
시간복잡도, 구현방식

 

 

 Map의 특징

---

  기본적으로 Map은 <key, value> 한 쌍으로 저장하는 방식이며 key를 통해서 value를 조회하는 구조입니다. Map은 구현방식에 따라 크게 3가지로 나뉘는데, key를 저장하는 순서와 조회 / 저장 시간복잡도에 따라서 갈립니다. 먼저 key의 저장순서를 먼저 알아보겠습니다.

 

void insertAndPrint(AbstractMap<Integer, String>map){
    int[] array = {1,-1,0};
    for(int x: array){
    	map.put(x,Integer.toString(x));
    }
    for(int k : map.keySet()) {
    	System.out.print(k+", ");
    }
}

 

  위의 코드에서 key값을 1,-1,0의 순서로 넣는 것에 유의해 주시기 바랍니다. 이렇게 <key, value>를 넣었을 때 각 HashMap, LinkedHashMap, TreeMap은 어떤 방식으로 key값을 저장할까요? 

 

HashMap	LinkedHashMap	TreeMap
{ 임의의 순서 }	{ 1, -1, 0 }	{ -1, 0, 1 }

 

 

  

• HashMap

 HashMap은 임의의 순서로 저장됩니다. {-1,0,1}일수도 {0,-1,1}일수도 또 다른 형식일 수도 있습니다. 여기서는 3!으로 총 6가지의 경우의 수가 가능하겠네요. 가장 일반적으로 사용하는 Map이며 내부적으로 연결리스트로 구현된 배열을 사용합니다. 

 

public class HashMap extends AbstractMap 
implements Map,Cloneable, Serializable

 

 

 

• TreeMap

TreeMap은 오름차순으로 저장됩니다. {1,-1,0}의 순서로 넣었지만 그 결과는 {-1,0,1}이 나온 것을 알 수 있습니다. 그래서 출석부를 만들 때 사용하면 좋습니다. TreeMap<이름, Person객체> 형태로 이름과 Person객체를 대응시켜서 저장하면 알아서 이름의 순서를 기준으로 정렬이 됩니다. 이름에서 알 수 있듯이 내부적으로 Tree를 구현하고 있습니다. 

 

public class TreeMap extends AbstractMap implements
NavigableMap, Cloneable, Serializable

 

 

 

• LinkedHashMap

LinkedHashMap은 key를 저장한 순서대로 저장됩니다. 우리가 key값을 넣는 그대로 순서를 유지합니다. 시간순서로 관리하다보니 캐쉬를 구현할 때 가장 오래된 아이템 순서대로 삭제하고 싶을 때 유용합니다.

 

public class Hashtable extends Dictionary implements
Map, Cloneable, Serializable

 

 

시간복잡도, 구현방식

---

	HashMap	TreeMap	LinkedHashMap
조회 / 저장	O(1)	O(logN)	O(1)
구현방식	LinkedList로 연결된 배열	Red-Black-Tree (*key는 Comparable 구현)	double-linked bucket

 

또한 HashTable을 추가한 비교는 아래와 같습니다.

 

https://javarevisited.blogspot.com/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html#axzz7hkM4n200

 

 

참고

https://www.geeksforgeeks.org/differences-treemap-hashmap-linkedhashmap-java/