자바의 자료구조 Collection Framework (1) - Map

자바를 매일 같이 사용하면서 매번 자연스럽게 가져다 쓰는 자료구조 중 하나가 바로 Map 자료 구조이다. Java는 JDK 1.2 이후 버전부터 Collection Framework를 추가했다. Collection Framwork의 추가로 편하게 사용할 수 있는 인터페이스 및 구현된 클래스들이 제공되게 되었으며 그 중 하나가 오늘 글을 쓰게된 Map이다.

1. Map의 개요

Map인터페이스는 키와 값을 하나의 쌍으로 묶어서 저장하는 컬랙션 클래스를 구현하는 데 사용된다. 키의 중복은 허용하지 않지만 다른 키를 가지는 같은 값은 허용된다. Java의 Map 인터페이스를 구현한 클래스로는 대표적으로 HashMap, LinkedHashMap, TreeMap 등이 있다.

2. HashMap

Java의 HashMap 은 내부적으로 Hash Algorithm을 사용하여 검색 속도가 매우 빠르다는 장점을 가지고 있다.  내부적으로 Entry의 배열로 구성되어있다. HashMap의 get 메소드는 O(1)로 동작한다. 입력 순서를 보장하지 않기 때문에 입력 순서 보장이 필요한 Map을 구현해야 한다면 LinkedHashMap이 필요하다

3. LinkedHashMap 

일반적으로 Key가 Map에 삽입된 순서를 보장한다. HashMap의 모든 기능들은 그대로 사용가능할 수 있게 확장하여 구현하되, 이중 연결 리스트를 통해 각 데이터들의 순서를 유지한다. 데이터의 크기가 커지면 랜덤하게 접근할 때 최악의 경우 O(n)으로 동작하기 때문에 순서가 유의미한 것이 아니라면 많은 데이터를 입력할 땐 사용에 유의해야 한다.

4. TreeMap

트리맵은 내부적으로 Red-Black Tree Algorithm으로 구성되어 있다. TreeMap에 자료를 추가하게 되면 Key를 기준으로 입력 즉시 정렬하게 된다. 때문에 일반적으로 HashMap 보다 성능이 떨어지게 된다. 일반적으로 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 범위 검색할 때 유용하게 사용할 수 있다.

References

1. https://medium.com/@igniter.yoo/java-linkedhashmap-%EC%88%9C%EC%84%9C%EB%A5%BC-%EC%9C%A0%EC%A7%80%ED%95%98%EB%8A%94-%ED%95%B4%EC%8B%9C%EB%A7%B5-11a7846d8893

2. https://rangken.github.io/blog/2015/java.map/

3. https://coding-factory.tistory.com/557