데이터를 모아서 관리할 수 있는 클래스를 컬렉션이라고 한다.
컬렉션은 그 타입에 따라 내부에 데이터를 저장하는 구조와 처리하는 방법이 다르다. 내부에서 처리하는 방법에 따라 데이터의 탐색이 빠른 경우가 있고, 추가/제거가 빠른 경우가 있다. 사용하는 컬렉션의 특성을 잘 알고 사용해야 불필요한 성능 저하를 피할 수 있다.
자바에서 제공하는 컬렉션의 대표적인 예로 List, Map, Set 등이 있다. 그 중에 이번 포스트에서 알아볼 Map 종류는 Key 값과 Value 값을 관리해주는 컬렉션이다. Key - Value 쌍은 java.util.Map.Entry 클래스로 정의되며 이 Entry 들을 저장, 관리 해주는 컬렉션이 Map이다.
Map 컬렉션은 다음과 같이 사용할 수 있다. 가장 많이 사용하는 HashMap을 사용한 예제를 살펴보겠다.
Map<String, String> map = new HashMap<String, String>();
map.put("key1", "value1");
map.put("key2", "value2");
System.out.println(map.get("key1"));"key1"이라는 Key 값과 "value1"이라는 Value 값을 갖는 Entry가 HashMap 내부에 put() 메소드를 통해 저장된다. 나중에 해당 값을 가져올 때에는 Key 값인 "key1"라는 문자열만 넘겨주면 Value 값을 얻어올 수 있는 형태의 컬렉션이다.
Map 컬렉션은 그 내부 구현 방식에 따라 'HashMap', 'TreeMap', 'LinkedHashMap' 등으로 나뉜다. 이번 포스트에서는 가장 많이 사용되는 이들 Map 컬렉션의 특징을 알아보도록 하겠다. (이 들이 제공해야하는 기본적인 메소드는 Map 인터페이스의 정의를 찾아보자.)
HashMap
자바 개발자가 사용하는 Map 컬렉션 중에 가장 많이 사용되는 것을 꼽으라면 HashMap을 꼽을 것이다.
HashMap은 내부적으로 Entry 배열을 만들어 관리한다. map.put() 메소드를 이용해서 엔드리를 추가하면 Key 값으로 넘겨준 객체의 해시 코드를 계산하여 Entry 배열의 접근 인덱스로 사용한다. 예를 들어 "key1"이라는 문자열의 해시 코드를 계산했을 때 10이라는 값이 나오면 배열의 10번째 항목으로 Value를 저장하는 식이다.
HashMap의 해시값 계산은 자바 버전에 따라 다르겠지만 기본적으로 객체의 hashCode() 메소드의 리턴 값을 기반으로 동작한다. 또 한 해시 충돌(Hash Collision)의 경우를 대비해 equals() 메소드까지 사용해서 Key 값이 정말 같은 경우에만 Value를 리턴해준다. 따라서 키 값으로 사용할 클래스의 특성에 따라 필요한 경우 hashCode() 메소드와 equals() 메소드를 오버라이드(Override)해야 할 수도 있다.
HashMap으로 관리되는 데이터 전체를 다시 뽑을 때에는 순서가 뒤섞이게 된다. HashCode를 계산해서 사용하기 때문이다. 다음 예제를 살펴보자.
Map<String, String> map = new HashMap<String, String>();
map.put("Google", "USA");
map.put("Naver", "Korea");
map.put("Facebook", "USA");
for(Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
// 출력 값
// Naver:Korea
// Facebook:USA
// Google:USA입력된 순서나 Key 값의 정렬 순서는 지켜지지 않고 다 섞이게 된다. 다만 다른 Map에 비해 빠른 탐색시간을 갖는다. 해시 함수를 사용하기 때문에 O(1)의 시간 복잡도를 갖는다.
TreeMap
HashMap과 다르게 TreeMap은 입력된 Key - Value 쌍을 내부적으로 RedBlack Tree로 저장하여 관리한다. 따라서 Key 값을 기준으로 정렬된 상태를 유지할 수 있다.
이 때, Key 값으로 사용할 클래스에 Comparator 인터페이스를 구현하면 사용자가 정렬된 순서를 조정할 수 있다. (Comparator 인터페이스를 구현하는 Key 클래스에 대해서는 본 포스트에서 따로 다루지는 않겠다)
위에서 봤던 예제 코드를 TreeMap으로 바꿔서 실행해보자
Map<String, String> map = new TreeMap<String, String>();
map.put("Google", "USA");
map.put("Naver", "Korea");
map.put("Facebook", "USA");
for(Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
// 출력 값
// Facebook:USA
// Google:USA
// Naver:Korea문자열의 비교 연산에 따라 사전순으로 정렬된 결과를 확인할 수 있다.
TreeMap은 데이터를 내부적으로 RB-Tree 형태로 관리하기 때문에 데이터를 탐색하는데 O(log N)의 시간이 걸린다. 또 한, 엘리먼트의 추가/삭제 역시 O(log N) 시간이 걸린다. HashMap과 비교해보면 좀 더 느린 속도를 갖는다.
LinkedHashMap
LinkedHashMap으로 구현된 Map은 데이터의 '입력된 순서'를 기억한다. LinkedHashMap에 저장되는 각 항목은 Map.Entry 클래스를 구현한 Node 클래스로 내부에 before, after 멤버를 갖는 연결리스트 구조를 가지고 있다.
위에서 봤던 예제를 LinkedHashMap으로 바꿔서 실행해보면
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("Google", "USA");
map.put("Naver", "Korea");
map.put("Facebook", "USA");
for(Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
// 출력 값
// Google:USA
// Naver:Korea
// Facebook:USAmap.put() 메소드로 입력한 순서대로 출력되는 것을 확인할 수 있다.
LinkedHashMap은 HashMap 클래스를 확장한 클래스로 엘리먼트의 추가/제거는 O(1) 시간에 이뤄지고, 모든 멤버들을 순회하는 연산도 O(1) 시간에 이뤄진다. (LinkedList의 각 항목을 순회하는 동작이므로)
요약
요약하자면,
- HashMap은 순서를 보장하지 않는다
- TreeMap은 Key 값으로 사용된 클래스의 비교 연산을 활용하여 순서를 보자한다. ( 이 때, Key 값으로 사용한 클래스가 Comparator 인터페이스를 구현하게 한다면 원하는대로 순서를 조정할 수 있다)
- LinkedHashMap은 입력된 순서를 보장한다
각각의 특성이 모두 다르지만, TreeMap이나 LinkedHashMap을 사용해야하는 특별한 이유가 없다면 HashMap을 쓰자. HashMap의 시간 복잡도는 O(1)이다. 해시 값을 사용하기 때문이다. 반면 RB-Tree를 사용하는 TreeMap의 접근 연산은 O(log n)이다. 대신 정렬된 순서를 얻을 수 있다. LinkedHashMap의 경우 O(1)의 시간 복잡도를 갖지만 불필요하게 Linked-list를 유지하는 비용이 생길 수 있다.
댓글