java.util.LinkedHashMap

 

Map Interface의 구현체중의 하나로 HashMap과 기능이 유사하지만, LinkedHashMap은 입력한 순서대로 key의 순서를 보장해 준다는 특징이 있습니다. 이 LinkedHashMap 는 HashMap을 extends 하고있기에 내부적인 기능을 그대로 사용하지만, key의 순서를 보장하기위해 LinkedHashMap에서만 추가 구현된 부분이 있습니다. 이번 포스팅에서는 이 부분을 기록해 보겠습니다.

 

먼저 LinkedHashMap 생성자를 살펴보면 다음과 같습니다.

public LinkedHashMap(int initialCapacity, float loadFactor) {
     super(initialCapacity, loadFactor);
     accessOrder = false;
 }
 
 public LinkedHashMap(int initialCapacity) {
     super(initialCapacity);
     accessOrder = false;
 }

 public LinkedHashMap() {
     super();
     accessOrder = false;
 }
  
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

public LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

HashMap과는 별도로 LinkedHashMap에서는 accessOrder 이라는 값을 가지고 있습니다.

이값은 기본적으로 false로 설정이 되어있는데, 해당 두개의 부분은 다음과 같습니다.

true : access-order : 최근에 접근한 element를 가장 마지막에 표기

false : insertion-order ( 입력한 순서대로 key저장 )

 

 

사실상 아무 설정을 해주지 않는다음 다음과 같이 선언한 문법처럼 동작하게 됩니다.

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, false);

 

 

먼저 LinkedHashMap put 작업을 살펴보겠습니다. 일반적으로 hashMap과 동일한 putVal 메서드를 수행하지만, 이 과정에서 생성되는 Node의 작업이 LinkedHashMap에서 구현된 newNode를 호출하게 됩니다.

//HashMap에서 newNode를 하는 부분중 하나.
.....
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
.....

// LinkedHashMap newMap
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);
    return p;
}


static class Entry<K,V> extends HashMap.Node<K,V> {
     Entry<K,V> before, after;
     Entry(int hash, K key, V value, Node<K,V> next) {
         super(hash, key, value, next);
     }
}

해당 new LinkedHashMap.Entry<>(hash, key, value, e); 를 통해서 생성되는 node자체는 HashMap에서 사용하는 Entry를 사용합니다. 단, linkNodeLast(p)작업을 통해서 LinkedHashMap는 순서를 보장하는 작업을 가지가 됩니다. 이 과정에서 Entry<K,V> before, after;의 추가공간을 가지기에 LinkedHashMap은 HashMap보단 좀 더 많은 공간을 차지하게 됩니다.

 

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

해당부분을 통하여 head, tail 등의 변수에 순서를 저장하고, keySet()등을 통하여 forEach문을 돌리게 되면 입력된 순서대로 key값이 출력되는것을 확인할 수 있게 됩니다.

 

 

이외에도 HashMap에는 아래 3개의 메서드가 비어있지만, 이부분은 LinkedHashMap에서 구현 되어있습니다. 

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { } // 데이터에 접근했을때
void afterNodeInsertion(boolean evict) { } // 데이터 추가 후 동작
void afterNodeRemoval(Node<K,V> p) { } // 데이터가 삭제되었을 때

해당 부분을 각각 확인해보면, 

 

afterNodeRemoval : 친절하게 주석에서도 써있다싶이 node가 제거되었을 때, 연결을 끊는 작업을 진행합니다.

 void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p = LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

 

afterNodeInsertion : 해당코드는 데이터가 추가된 후 발생되는 부분으로, removeEldestEntry라는 함수를 호출하게 되는데 현재 LinkedHashMap에서는 이부분이 return false로만 되어있습니다. 만약 특정 조건에서 first(head)를 삭제해야할 일이 있다면, LinkedHashMap를 상속받는 클레스를 구현, removeEldestEntry를 구현하여 사용하면 아래의 afterNodeInsertion를 이용할 수 있습니다.

 void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}


protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

마지막으로 afterNodeInsertion의 경우에는 accessOrder가 true로 접근하였을 경우, key의 순서를 변경해주는 작업을 진행해주게 됩니다. 해당부분이 기본으로 사용한다면 호출은 되나, 실제 실행은 되지않게 됩니다.

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

 

간략하게나마 LinkedHashMap을 정리하면서 애매한 부분도 같이 정리가 되었고, 새로운 부분 accessOrder (이런게 있었다니.. ) 역시 공부는 일단 해야하나봅니다. 

 

 

 

참고 사이트 : https://www.baeldung.com/java-linked-hashmap