[Java]LinkedHashMap 실현 원리

1.개술
#7 이 소개 한 HashMap 을 이해 한 후에 우 리 는 LinkedHashMap 의 작업 원리 와 실현 을 배 웠 다.우선 비슷 합 니 다.간단 한 링크 드 HashMap 프로그램 을 쓰 겠 습 니 다.

LinkedHashMap<String, Integer> lmap = new LinkedHashMap<String, Integer>();
lmap.put("  ", 1);
lmap.put("  ", 2);
lmap.put("  ", 3);
lmap.put("  ", 4);
lmap.put("  ", 5);
lmap.put("  ", 6);
lmap.put("  ", 7);
lmap.put("  ", 8);
for(Entry<String, Integer> entry : lmap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

실행 결 과 는:

  : 1
  : 2
  : 3
  : 4
  : 5
  : 6
  : 7
  : 8

HashMap 의 실행 결과 와 달리 LinkedHashMap 의 교체 출력 결 과 는 삽입 순 서 를 유지 하고 있 음 을 관찰 할 수 있 습 니 다.어떤 구조 로 인해 링크 드 하 쉬 맵 은 이러한 특성 을 가지 게 되 었 습 니까?우 리 는 똑 같이 링크 드 하 쉬 맵 의 내부 구 조 를 살 펴 보고 감성 적 인 인식 을 가진다.
맞습니다.공식 문서 에서 말 한 것 처럼:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

링크 드 HashMap 은 Hash 표 와 링크 의 실현 이 고 양 방향 링크 에 의 해 교체 순서 가 삽입 순서 임 을 보증 합 니 다.
2.세 가지 중점 실현 함수
HashMap 에서 다음 과 같은 정 의 를 언급 했 습 니 다.

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

링크 드 HashMap 은 HashMap 에 계승 되 었 기 때문에 이 세 가지 함 수 를 다시 실현 했다.말 그대로 이 세 가지 함수 의 역할 은 노드 방문 후,노드 삽입 후,노드 제거 후 일 을 하 는 것 이다.afterNodeAccess 함수

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //      accessOrder，               
    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;
    }
}

즉,put 를 한 후에 노드 에 대한 방문 이 라 고 해도 이 럴 때 링크 를 업데이트 하고 최근 에 방문 한 것 을 마지막 에 두 어 링크 를 확보 하 는 것 이다.
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);
    }
}

사용자 가 removeEldestEntry 의 규칙 을 정의 하면 해당 제거 작업 을 수행 할 수 있 습 니 다.
afterNodeRemoval 함수

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;
}

이 함 수 는 노드 를 제거 한 후에 호출 된 것 으로 노드 를 양 방향 링크 에서 삭제 하 는 것 입 니 다.우 리 는 위의 세 가지 함 수 를 통 해 알 수 있 듯 이 대체적으로 양 방향 링크 의 노드 순서 나 양 방향 링크 용량 을 확보 하기 위해 추가 적 인 일 을 하 는 것 이다.목적 은 양 방향 링크 의 노드 순 서 를 eldest 에서 youngst 까지 유지 하 는 것 이다.
3.put 와 get 함수
put 함 수 는 링크 드 HashMap 에서 다시 실현 되 지 않 았 으 며,after Node Access 와 after Node Insertion 두 개의 반전 함수 만 실현 되 었 습 니 다.get 함 수 는 after Node Access 를 다시 실현 하고 가입 하여 방문 순 서 를 확보 합 니 다.다음은 get 함수 의 구체 적 인 실현 입 니 다.

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

주의해 야 할 것 은 accessOrder 모드 에서 get 이나 put 등 작업 을 수행 할 때 structural modification 이 발생 한 다 는 점 이다.공식 문 서 는 이렇게 설명 합 니 다.

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with get is a structural modification.

유사 한 문 제 를 범 하지 마라.
한 마디 로 하면 링크 드 하 쉬 맵 은 하 쉬 맵 의 아들 답 게 노자 와 너무 닮 았 습 니 다.물론 청 출어 람 이 파란색 보다 낫 습 니 다.링크 드 하 쉬 맵 의 다른 조작 도 기본적으로 방문 순 서 를 가 진 양 방향 링크 를 잘 지 키 기 위해 서 입 니 다.:-)