"Map 과 HashMap의 차이가 뭐에요?" (내 얘기)

본인이 쓴 글은 아니지만, 실제로 있던 질문이다

 

 

결론부터 말하자면,

Map이란 key-value로 값을 저장하는 자료구조를 의미하고, HashMap은 Map을 구현해놓은 구현체 중 하나이다. 

즉, 서로 비교대상이 될 대상이 아니다. Map이란 개념을 구현해서  HashTable, HashMap, TreeMap 등이 있는 것이니 말이다. 

 

'진자와 그네의 차이점이 뭔가요?' 와 비슷한 질문일 것 같다.

 

그럼 Map이란 무엇일까?

Java Collection의 주요 인터페이스엔 List, Set, Map이 있는데, 

우선 이 인터페이스를 구분하는 가장 중요한 개념은 "순서" 와 "데이터중복여부" 에 있다.

• List: 순서 O, 데이터 중복O
• Set: 순서 X, 데이터 중복X
• Map: Key&Value 저장, Key중복X, Value중복 O

Java Collection에 대해서는 따로 정리하도록 하겠다. 

 

 

Map은 Key와 Value로 구성된 객체를 저장한다.
키는 중복 저장될 수 없다. 

구현하는 클래스로는 

• HashMap
• TreeMap
• LinkedHashMap
• HashTable
  이 있다. 

 

 

HashMap

키에 대한 해시 값을 사용하여 값을 저장하고 조회한다. 

키 객체의 해시값을 '버킷'이라는 곳에 저장하고 있고, 

그 값을 통해 객체를 뽑아와서 O(1)의 속도로 객체를 찾아올 수 있다는 장점이 있다. 

Key-Value의 형태를 가지고 Key와 Value가 1:1매핑이 되어 하나의 쌍(pair)로 중복된 key를 허용하지 않는 순서가 없는 자료구조

라고할 수 있다. (value는 중복될 수 있다. key값이 다르면 된다) 

 

 

HashMap 선언

HashMap<String,String> map1 = new HashMap<String,String>();//HashMap생성
HashMap<String,String> map2 = new HashMap<>();//new에서 타입 파라미터 생략가능
HashMap<String,String> map3 = new HashMap<>(map1);//map1의 모든 값을 가진 HashMap생성
HashMap<String,String> map4 = new HashMap<>(10);// HashMap 크기 지정
HashMap<String,String> map5 = new HashMap<String,String>(){{//초기값 지정
    put("a","b");
}};

HashMap을 생성하려면 키 타입과 값 타입을 파라미터로 주고 기본생성자를 호출하면 된다.

HashMap은 저장공간보다 값이 추가로 들어오면 List처럼 저장공간을 추가로 늘리는데
List처럼 저장공간을 한 칸씩 늘리지 않고 약 두 배로 늘린다. 여기서 과부하가 많이 발생한다.

그렇기에 초기에 저장할 데이터 개수를 알고 있다면 Map의 초기 용량을 지정해주는 것이 좋다.

 

 

HashMap 값 추가

HashMap<Integer,String> map = new HashMap<>();//new에서 타입 파라미터 생략가능
map.put(1,"코엑스"); //값 추가
map.put(2,"강남");
map.put(3,"양재");

HashMap에 값을 추가하려면 put(key,value) 메소드를 사용하면 된다.

선언 시 HashMap에 설정해준 타입과 같은 타입의 Key와 Value값을 넣어야 하며

만약 입력되는 키 값이  HashMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로 대치된다.(덮어쓰기)

 

 

HashMap 값 삭제

HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"코엑스");
    put(2,"강남");
    put(3,"양재");
}};
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

HashMap에 값을 제거하려면 remove(key) 메소드를 사용하면 된다.

오직 키값으로만 Map의 요소를 삭제할 수 있고,

모든 값을 제거하려면 clear() 메소드를 사용하면 된다.

 

 

 

HashMap 값 출력

HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"코엑스");
    put(2,"강남");
    put(3,"양재");
}};
		
System.out.println(map); //전체 출력 : {1=코엑스, 2=강남, 3=양재}
System.out.println(map.get(1));//key값 1의 value얻기 : 코엑스
		
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:코엑스
//[Key]:2 [Value]:강남
//[Key]:3 [Value]:양재

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:코엑스
//[Key]:2 [Value]:강남
//[Key]:3 [Value]:양재

HashMap을 출력하는 방법에는 다양한 방법이 있다.

그냥 .print(HashMap)하게 되면 {}로 묶어 Map의 전체 key값, value가 출력된다.

특정 key값의 value를 가져오고싶다면 get(key)를 사용하면 되고

전체를 출력하려면 entrySet()이나 keySet()메소드를 활용하여 Map의 객체를 반환받은 후 출력하면 된다.

entrySet()은 key와 value 모두가 필요할 경우 사용하며

keySet()은 key 값만 필요할 경우 사용하는데 key값만 받아서

get(key)를 활용하여 value도 출력할 수도 있기에

어떤 메소드를 선택하든지 간에 큰 상관이 없다.

 

대부분 코드가 간단한 keySet을 활용하던데

key값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되므로

많은 양의 데이터를 가져와야 한다면 entrySet()이 좋다.(약 20%~200% 성능 저하가 있음)

 

 

 

HashMap의 주요 메소드를 정리하면

void clear()	해당 맵(map)의 모든 매핑(mapping)을 제거함.
boolean containsKey(Object key)	해당 맵이 전달된 키를 포함하고 있는지를 확인함.
boolean containsValue(Object value)	해당 맵이 전달된 값에 해당하는 하나 이상의 키를 포함하고 있는지를 확인함.
V get(Object key)	해당 맵에서 전달된 키에 대응하는 값을 반환함. 만약 해당 맵이 전달된 키를 포함한 매핑을 포함하고 있지 않으면 null을 반환함.
boolean isEmpty()	해당 맵이 비어있는지를 확인함.
Set<K> keySet()	해당 맵에 포함되어 있는 모든 키로 만들어진 Set 객체를 반환함.
V put(K key, V value)	해당 맵에 전달된 키에 대응하는 값으로 특정 값을 매핑함.
V remove(Object key)	해당 맵에서 전달된 키에 대응하는 매핑을 제거함.
boolean remove(Object key, Object value)	해당 맵에서 특정 값에 대응하는 특정 키의 매핑을 제거함.
V replace(K key, V value)	해당 맵에서 전달된 키에 대응하는 값을 특정 값으로 대체함.
boolean replace(K key, V oldValue, V newValue)	해당 맵에서 특정 값에 대응하는 전달된 키의 값을 새로운 값으로 대체함.
int size()	해당 맵의 매핑의 총 개수를 반환함.

 

 

HashTable에 대해 잠깐 언급하자면,

HashMap과 비교하여

• Thread-safe 여부
  • Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다는 특징을 가지고 있다.
  • 그렇기에 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다는 단점을 가지고 있다.
• Null 값 허용 여부
  • Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.
• Enumeration 여부
  • Hashtable은 not fail-fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않는다.
• HashMap의 값의 동일성 여부를 확인할 때 .equals() 함수를 사용하는데,
  HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여
  해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
• 최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있다.

HashMap 클래스와 같은 동작을 하는 클래스이지만,  기존 코드와의 호환성을 위해서만 남아있으므로
Hashtable 클래스보다는 HashMap 클래스를 사용하는 것이 좋다.

 

 

TreeMap

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

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

- Key - Value 쌍을 내부적으로 RedBlack Tree로 저장하여 관리한다. 따라서 Key 값을 기준으로 정렬된 상태를 유지할 수 있다.

 

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

데이터를 RB-Tree 형태로 관리하기 때문에  데이터를 탐색하는데 O(log N)의 시간이 걸린다.
또한, 엘리먼트의 추가/삭제 역시 O(log N) 시간이 걸린다.

HashMap과 비교해보면 성능이 떨어진다. 

 

사용해야 하는 경우

1) 정렬된 상태로 데이터를 조회하는 경우
데이터를 조회할 때 정렬해야 하는 hashMap보다는 이미 정렬된 상태로 저장되어 있는 TreeMap이 빠른 조회결과를 얻을 수 있다.
2) 정렬된 상태로 Map 을 유지해야 하는 경우
3) 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우
4) 키 값을 기준으로 정렬을 해서 사용할 경우

 

🪬레드-블랙 트리(Red-Black Tree)
TreeMap 은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있다.
일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요하다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없지만 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우, 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 낸다. 이 문제를 보완하기 위해 레드 블랙 트리가 등장하였다.

1) 이진 탐색 트리가 편향 트리가 될 경우를 방지하는 조건을 추가함.
레드블랙트리의 높이는 logN에 바운드 됩니다 ->
레드블랙트리에서 삽입, 삭제, 검색 연산은 O(logN) 의 시간복잡도를 가진다.
2) 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다. (worst-case guarantees).
이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.

 

 

LinkedHashMap

입력된 key의 순서가 보장된다.”는 것이 가장 큰 특징이다.

LinkedHashMap은 HashMap을 확장한 것이라고 생각하면 좋다.

HashMap의 모든 기능을 사용하되, Doubly-Linked List(이중 연결 리스트)를 내부에 유지함으로써

입력된 자료의 순서를 보관한다.

즉, LinkedHashMap은 기존 HashMap 자료구조에서 LinkedList 자료구조를 섞어놓은 자료구조이다.

HashMap의 특징인, 저장된 값들을 순회하고자 할때 값을 넣은 순서가 아닌 무작위로 출력되게 되는 것을 보완하기 위해 등장하였다.
따라서,LinkedHashMap은 FIFO (First In First Out) 구조로 데이터를 저장한다.

HashMap과 LinkedHashMap의 최종 속도 차이는 큰차이가 없지만,

LinkedHashMap은 순서를 유지하기 때문에 메모리 사용량이 HashMap보다 높다.

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
/**
    * The head (eldest) of the doubly linked list.
    */
transient LinkedHashMap.Entry<K,V> head;

/**
    * The tail (youngest) of the doubly linked list.
    */
transient LinkedHashMap.Entry<K,V> tail;

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);

LinkedHashMap은 HashMap을 상속받았고,

여기에 head와 tail, before과 after라는 변수가 추가되었다.

이 변수들을 이용하여 Map에 들어온 순서를 기억한다. 

 

HashMap의 keySet순회는 단순히 0번부터 순회하여 hash값이 낮은 순서부터 순회하지만,
데이터가 늘어나 loadfactor를 넘는 순간 hashcode의 재 분배가 일어나 순서가 뒤바뀐다.
=> 특정한 순서를 보장할 수 없다!

 

 

 

 

 

참고

https://d2.naver.com/helloworld/831311

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/HashMap.html