자바의 맵

Map은 key와 value를 쌍으로 저장하는 자료구조 키는 중복될 수 없고, 값은 중복될 수 있다.

   import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
    import java.util.Set;   
    public class MapExam {  
        public static void main(String[] args) {
            // Key, Value가 모두 String 타입인 HashMap인스턴스를 만듭니다.
            Map<String, String> map = new HashMap<>();

            // key와 value값을 put으로 저장합니다.
            map.put("001", "kim");
            map.put("002", "lee");
            map.put("003", "choi");
            // 같은 key가 2개 있을 수 없습니다. 첫번째로 저장했던 001, kim은 001, kang으로 바뀐다.
            map.put("001", "kang");

            // map에 저장된 자료의 수를 추력합니다. 3이 출력됩니다.
            System.out.println(map.size());

            // 키가 001, 002, 003인 값을 꺼내 출력합니다.
            System.out.println(map.get("001"));
            System.out.println(map.get("002"));
            System.out.println(map.get("003"));

            // map에 저장된 모든 key들을 Set자료구조로 꺼냅니다.
            Set<String> keys = map.keySet();
            // Set자료구조에 있는 모든 key를 꺼내기 위하여 Iterator를 구합니다.
            Iterator<String> iter = keys.iterator();
            while (iter.hasNext()) {
                // key를 꺼냅니다.
                String key = iter.next();
                // key에 해당하는 value를 꺼냅니다.
                String value = map.get(key);
                // key와 value를 출력합니다.
                System.out.println(key + " : " + value);
            }
        }
    }

HashMap

내부적으로 Entry<K,V>[] Entry 의 array 로 되어 있다. 해당 array 에 index 는 내부 해쉬 함수를 통해 계산된다.
String 은 sun.misc.Hashing.stringHash32 함수를 사용하고 일반 Object는 내부 hashcode 함수와 비트연산으로 계산되어진다.

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 구현으로 정렬 순서를 바꿀수 있다.

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

링크드 리스트로 저장됨

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) 성능을 지니므로 많은 데이터를 입력할 경우 사용하지 않는것이 좋다.

프로그래머스
rangken.github.io/blog/2015/java.map/