자료구조 : Map

오늘은 알고리즘 문제에서도 많이 사용하고 실전에서도 많이 사용한다고 알려져있는 Map에 대해서 알아보도록 하겠습니다. 

 

Map

맵은 사전과 비슷합니다. people이란 단어에 "사람", baseball이란 단어에 "야구" 라는 뜻이 부합되듯이 Map은 Key와 Value라는 것을 한 쌍으로 갖는 자료구조입니다. Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해서 Value를 얻습니다. 

 

Map의 가장 큰 특징은 Key로 Value를 얻어낸다는 것입니다. people이라는 단어의 뜻을 찾기 위해서 사전의 내용을 순차적으로 검색하는 것이 아니라 해당 단어가 있는 곳만을 펼쳐보는 것이죠.

 

우리가 잘 아는 Map은 List와 마찬가지로 인터페이스입니다. Map인터페이스를 구현한 HashMap, LinkedHashMap, TreeMap 등이 있습니다. 

 

기본적으로 put 메서드를 이용해 데이터를 집어넣고 get 메서드를 이용해 데이터를 조회합니다.

 

또한 다양한 메서드로 Map 객체에 접근할 수 있습니다. contains 라는 메서드는 파라미터로 넘긴 키값이 존재하는지를 빠르게 찾을 수 있습니다. 위에서도 설명했지만 Map은 순차적으로 모든 키-값을 조회하는 것이 아니라 키가 존재하면 바로 값을 리턴해주는 빠른 자료구조입니다. 

 

값이 더이상 필요 없어지만 remove를 이용해 키-값을 삭제할수도 있습니다. 혹은 size 메서드를 통해 키의 개수를 세어볼 수도 있습니다. 

 

키값만 따로 모아서 Set 자료구조에 넣을수도 있습니다. 바로 entrySet 메서드를 이용하면 됩니다. 

 

이처럼 다양한 메서드로 key-value에 접근할 수 있고 이러한 방식은 key를 입력해서 value를 빠르게 구하고 싶으면 사용해볼만한 자료구조입니다.

 

HashMap

Map 인터페이스의 가장 기본적인 구현체입니다. 대중적으로 많이 사용되는 구현체로 많은 개발자들에게 사랑을 받고 있습니다. 

 

Map인터페이스에서 제공하는 기본적인 메서드를 그대로 가져왔으며 특별히 다른 메서드는 존재하지않습니다. 

 

 

TreeMap

TreeMap은 기존 Map과 다르게 정렬을 제공합니다. 기본적으로 선언할 때 오름차순을 디폴트 값으로 지정됩니다. 혹시 내림차순으로 값을 정렬하고싶다면 Collections.reverseOrder() 메서드를 사용하면 간단하게 뒤집을 수 있습니다.

 

Map<String, String> map = new TreeMap<>();	// 기본적인 초기화 (오른차순)
Map<String, Stirng> map = new TreeMap<>(Collections.reverseOrder());	// 내림차순으로 초기화

 

HashMap은 데이터 정렬이 없습니다. key 를 기준으로 정렬할 필요성이 있다면 유용하게 사용할 수 있는것이 TreeMap 클래스입니다. 

 

 

LinkedHashMap

LinkedHashMap은 입력순서대로 정렬하는 기능을 제공합니다. 

 

즉, 입력 순서가

map.put("a", "A");

map.put("b", "B");

map.put("c", "C");

 

이렇게 되었다면 다시 출력했을 때 A, B, C 순으로 출력됩니다. 그럼 HashMap은 그렇게 안될까요? 

 

직접 해보시면 뒤죽박죽으로 출력되는 것을 확인하실 수 있습니다. 

 

 

HashMap vs TreeMap vs LinkedHashMap

정리를 해보자면 HashMap은 기본적인 Map과 같고 TreeMap은 키값으로 정렬하고싶을 때 LinkedHashMap은 입력순서대로 정렬하고싶을 때 사용한다고 할 수 있겠습니다. 

 

참고로 TreeMap, 그리고 이후 포스팅에서 설명할 TreeSet은 이름에서도 알 수 있듯이 이진트리로 데이터를 관리하기 때문에 TreeMap, TreeSet을 사용한다면 값을 찾을 때 시간복잡도가 O(log n)으로 굉장히 빠른축에 속합니다. 

 

웬만한 알고리즘 문제에서 타임오버되는 문제들의 시간복잡도를 O(n)으로 해주면 대부분 풀리는데 O(log n)은 O(n)보다 훨씬 빠른 결과를 도출해냅니다. 

 

하지만 정말 중요한 개념이 하나 남아있습니다. 바로 ConcurrentHashMap인데요, 멀티스레드 환경인 실무환경에서 제일 많이 사용하는 구현체로서 기존 HashMap에서 해결하지 못했던 동시성문제를 센스있게 해결한 것으로 유명합니다. 

 

ConcurrentMap, ConcurrentHashMap은 바로 다음 포스팅에서 알아보도록 하겠습니다. 

 

그럼 이번 포스팅은 여기까지 마치도록 하겠습니다. 긴 글 읽어주셔서 감사합니다. 오늘도 좋은 하루 되세요~