LinkedHashMap 알아보기

HashMap은 Java에서 자주 사용하는 자료구조이다. 자료에 접근할 때 O(1)로 접근이 가능하여, 빈번하게 값을 찾아서 사용하는 경우 유용하게 사용할 수 있다. 다만, HashMap의 경우 저장된 값들을 순회하고자 할때 값을 넣은 순서가 아닌 무작위로 출력되게 된다.

이를 보완하고자 나온 것이 LinkedHashMap이다. LinkedHashMap은 doubly-linked list로 삽입한 값들을 관리한다. 그래서 삽입한 순서대로 값을 가져오고자할 때 사용할 수 있다. 아래는 LinkedHashMap과 HashMap에 들어간 값을 출력해보는 간단한 예제코드이다.

    public static void main(String[] args) throws Exception {
        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();

        linkedHashMap.put("apple", "apple");
        linkedHashMap.put("banana", "banana");
        linkedHashMap.put("monkey", "monkey");

        HashMap<String, String> hashMap = new HashMap<>();
        hashMap.put("apple", "apple");
        hashMap.put("banana", "banana");
        hashMap.put("monkey", "monkey");

        System.out.println("LinkedHashMap 순서");
        for (Entry<String, String> key : linkedHashMap.entrySet()) {
            System.out.println(key.getValue());
        }
        System.out.println();
        System.out.println("HashMap 순서");
        for (Entry<String, String> key : hashMap.entrySet()) {
            System.out.println(key.getValue());
        }
        //출력 값
        //LinkedHashMap 순서
        //apple
        //banana
        //monkey
        //
        //HashMap 순서
        //banana        <- apple과 banana의 순서가 바뀌어있다
        //apple
        //monkey
    }

HashMap과는 다르게 LinkedHashMap의 경우에는 삽입한 순서대로 출력되는 것을 알 수 있었다.

코드 살펴보기

동작되는 것을 살펴보았으니 실제로 어떻게 구현이 되었는지 살펴보도록 하자. doubly-linked list로 관리된다고 하였으니, 이와 관련된 멤버나 함수들이 추가 되어있을 것이다. 우선 상단에 head와 tail을 저장하는 변수가 선언되어 있다.

    //코드 상단에 doubly linked list 를 위한 head와 tail을 저장하는 변수가 선언되어있다.
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;

그 다음에는 put함수를 보자. put 함수는 HashMap class에 선언되어 있고 내부적으로 putVal이라는 함수를 호출한다.

    //in HashMap class
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

putVal의 함수 내부를 살펴보면, Node를 저장하고 있는 배열인 tab이라는 변수에 newNode함수를 호출하여 할당하는 줄이 이 보인다. 

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//newNode가 override되어있다!
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
 		...

LinkedHashMap은 이 newNode를 override 하여, 새로운 노드를 추가할 때마다 LinkedHashMap이 관리하고 있는 head와 tail에 연결하고 있음을 알 수 있었다. 생각보다 간단하게 구현 되어있는 것을 알 수 있다.

    //in LinkedHashMap
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<>(hash, key, value, e);
        linkNodeLast(p); // double-linked list로 entry를 관리한다.
        return p;
    }

 

여담

LinkedHashMap에는 LRU 알고리즘이 이미 구현되어있다. LinkedHashMap을 생성할 때, accessOrder값을 true로(default는 false) 주고 생성하게 되면, 우리가 LinkedHashMap에 있는 Node를 접근할 때마다, 그 Node를 제일 마지막으로 이동시키는 과정이 구현되어 있다.