자바 1.8 - 링크 드 HashMap 소스 분석

개술
    API 문서 에 따 르 면 링크 드 HashMap 은 Hash 표 와 링크 를 바탕 으로 이 루어 진 데이터 구조 이 고 양 방향 링크 에 의 해 데 이 터 를 삽입 하 는 순 서 를 확보 했다.
링크 드 하 쉬 맵 은 하 쉬 맵 에서 계승 되 었 으 며, 하 쉬 맵 과 같은 데이터 구 조 를 가지 고 있 습 니 다. 즉, 배열 + 링크 + 레 드 블랙 트 리 + 양 방향 링크 가 있 습 니 다. 링크 드 하 쉬 맵 은 모든 삽입 노드 를 양 방향 링크 로 연결 하기 때문에 데이터 의 삽입 순 서 를 확보 할 수 있 습 니 다.
상속 관계

public class LinkedHashMap
    extends HashMap
    implements Map
{

    링크 드 하 쉬 맵 은 하 쉬 맵 에서 계승 되 기 때문에 하 쉬 맵 에서 개인 적 인 방법 과 속성 을 제외 하고 다른 것 은 링크 드 하 쉬 맵 에서 직접 방문 할 수 있 습 니 다.
속성

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

/**
 *      
 */
transient LinkedHashMap.Entry head;

/**
 *      
 */
transient LinkedHashMap.Entry tail;

/**
 *       
 */
final boolean accessOrder;

방법.
put 방법
링크 드 HashMap 의 put 방법 은 다시 쓰 지 않 고 HashMap 의 put 방법 을 직접 사용 하 는 것 이 아니 라 put 방법 에서 리 셋 된 after Node Access 와 after Node Insertion 방법 을 다시 썼 습 니 다.

/**
 *       ，    put           ，    
 *       ，            ，       
 */
void afterNodeAccess(Node e) { // move node to last
    LinkedHashMap.Entry last;
    //        true，          
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)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;
    }
}

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

get 방법

/**
 *       accessOrder，  accessOrder true，          
 */
public V get(Object key) {
    Node e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

    위의 이런 방법 은 바로 LinkedHashMap 이 양 방향 링크 의 노드 순 서 를 유지 하기 위해 하 는 일이 다.
그 중에서 속성 을 주의해 야 합 니 다: accessOrder.이 속성 을 true 나 false 로 설정 하면 양 방향 링크 가 방문 순서에 따라 배열 되 는 지, 삽입 순서에 따라 배열 되 는 지 제어 할 수 있 습 니 다.
왜 방문 순서 가 있 을까요?사실 접근 순 서 는 고속 캐 시 를 실현 하 는 '최근 최소 사용' 원칙 에 매우 중요 하 다.접근 빈도 가 높 은 요 소 를 메모리 에 넣 고 접근 빈도 가 낮은 요 소 는 데이터베이스 에 넣 는 것 과 유사 합 니 다.여기 서 는 방문 빈도 가 높 은 요 소 를 앞으로 배열 한 다 는 것 이다.
우 리 는 작은 예 를 통 해 이 속성의 응용 을 간단하게 보 았 다.

public static void main(String[] args) {
    Map linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put("A", 1);
    linkedHashMap.put("B", 2);
    linkedHashMap.put("C", 3);
    System.out.println(linkedHashMap);
    
    //     LinkedHashMap     ，  accessOrder  
    Map map = new LinkedHashMap<>(16, 0.75f, true);
    map.put("A", 1);
    map.put("B", 2);
    map.put("C", 3);
    map.get("A");
    System.out.println(map);
}

인쇄 결과:

{A=1, B=2, C=3}
{B=2, C=3, A=1}

    사실 링크 드 HashMap 은 비교적 간단 하 다. 말하자면 원래 HashMap 을 바탕 으로 양 방향 링크 를 추가 하여 데 이 터 를 유지 하 는 순서 일 뿐이다.링크 드 하 쉬 맵 의 대부분 방법 은 이 순 서 를 지 키 기 위 한 것 이다.