Java에는 여러 종류의 Map이 있다.
차이를 알고 써야 한다.
셋의 가장 큰 차이는 시간복잡도와 키가 놓이는 순서에 있다.
HashMap
- 내부적으로 Entry<K,V>[] Entry 의 array 로 되어 있다. 해당 array 에 index 는 내부 해쉬 함수를 통해 계산된다.
- String 은 sun.misc.Hashing.stringHash32 함수를 사용하고 일반 Object는 내부 hashcode 함수와 비트연산으로 계산되어진다.
- 검색과 삽입에 O(1)이 소요된다. 키를 기준으로 순회 할 때 키의 순서는 무작위로 섞여 있다. 그리고 이 클래스의 구현은 연결리스트로 이루어진 배열로 되어있다.
Map<String, String> map = Maps.newHashMap();
map.put("c", "1");
map.put("a", "1");
map.put("b", "1");
map.put("k", "1");
for (String s : map.keySet()) {
System.out.println(s);
}
// b, c, a, k 출력- 내부 hash 값에 따라서 키순서가 정해지므로 특정 규칙없이 출력됨!
TreeMap
- 내부적으로 RedBlack Tree로 저장됨, 키값에 대한 Compartor 구현으로 정렬 순서를 바꿀수 있다.
- 검색과 삽입에 O(logN) 시간이 소요된다. 키는 정렬되어있다.
- 정렬된 순서로 키를 순회할 수 있어서 키는 반드시 Comparable 인터페이스를 구현하고 있어야 한다.
Map<String, String> map = Maps.newTreeMap();
map.put("c", "1");
map.put("a", "1");
map.put("b", "1");
map.put("k", "1");
for (String s : map.keySet()) {
System.out.println(s);
}
// a, b, c, k 출력- 키값이 알파벳 순서대로 정렬된다. 트리에 저장되므로 키값은 일정 기준으로 정렬된 상태로 출력된다.
LinkedHashMap
- 링크드 리스트로 저장된다.
- 검색과 삽입에 O(1) 시간이 소요된다. 키는 삽입한 순서대로 정렬되어 있고 양방향 연결 버킷으루 구현되어 있다.
Map<String, String> map = Maps.newLinkedHashMap();
map.put("c", "1");
map.put("a", "1");
map.put("b", "1");
map.put("k", "1");
for (String s : map.keySet()) {
System.out.println(s);
}
// c, a, b, k 출력- 키값은 입력 순서대로 출력되어서 나온다.
결론
- 특별한 이유가 없다면 검색 성능이 좋은(O(1)) HashMap 을 사용하자
- 키 값이 일정한 수준대로 iterate 하려고 한다면 TreeMap 을 사용하자. 하지만 랜덤 접근에 대해서는 O(logn) 성능을 지니므로 많은 데이터를 넣을경우 좋지 않은 성능이 나올수 있다.
- 입력 순서가 의미있다면 LinkedHashMap 을 사용하자. 랜덤 접근에 대해 O(n) 성능을 지니므로 많은 데이터를 입력할 경우 사용하지 않는 것이 좋겠다.
➕
- 이름과 Person객체 사이 대응 관계를 만들 때, 주기적으로 이름순으로 사람을 출력하고 싶다면 Treemap을 사용해도 좋다.
- Treemap은 이름이 주어졌을 때, 그 다음 10명의 사람도 출력할 수 있다. More 기능 구현 시 좋다는 것.
- LinkedHashMap은 삽입한 순서대로 키를 정렬하고 싶을 때 유용하다. 캐시 구현 할 때 가장 오래된 아이템 먼저 삭제 할때 가장 유용할 듯.
추가적으로
List, Set, Map의 차이도 알아보자.
List
- 데이터를 순차적으로 저장한다.
- 데이터의 중복을 허용한다.
- 데이터로 null을 허용한다.
Set
- 순서없이 Key로만 데이터를 저장한다.
- Key의 중복을 허용하지 않는다.
- Key로 null을 허용하지 않는다.
Map
- 순서없이 Key, Value로 데이터를 저장한다.
- Value는 중복을 허용하지만 Key의 중복을 허용하지 않는다.
- Key로 null을 허용하지 않는다.
developer