자바 소스 분석 링크 드 HashMap

구성원 변수
먼저 저장 요소 의 구 조 를 살 펴 보 자.

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

이 Entry 는 HashMap 에서 인 용 된 적 이 있 는데 주로 LinkedHashMap 도 트 리 화 를 지원 하기 위해 서 입 니 다.여기 서 는 원 소 를 저장 하 는 데 쓰 인 다.

//       ，  AccessOrder        
transient LinkedHashMap.Entry<K,V> head;

//       ，  AccessOrder        
transient LinkedHashMap.Entry<K,V> tail;

// true      ，false      
final boolean accessOrder;

구조 함수
링크 드 HashMap 의 구조 함수 에 대해 우 리 는 하나만 주목 합 니 다.다른 것 은 모두 HashMap 과 유사 합 니 다.다만 accessOrder 를 false 로 설정 합 니 다.위 문서 에서 말 했 듯 이 initial Capacity 는 HashMap 에서 만큼 중요 하지 않 습 니 다.링크 는 배열 처럼 충분 한 공간 을 먼저 밝 혀 야 하지 않 기 때 문 입 니 다.아래 의 이 구조 함 수 는 접근 순 서 를 지원 합 니 다.

//       ，  AccessOrder        
transient LinkedHashMap.Entry<K,V> head;

//       ，  AccessOrder        
transient LinkedHashMap.Entry<K,V> tail;

// true      ，false      
final boolean accessOrder;

3.중요 한 방법
링크 드 하 쉬 맵 은 더 이상 삭제 하고 고 치 는 방법 을 실현 하지 않 고 하 쉬 맵 을 복사 하 는 과정 에서 정 의 된 몇 가지 방법 으로 이 루어 졌 다.이에 익숙 하지 않 은 것 은 지난 HashMap 분석 에 관 한 글 을 보 거나 HashMap 의 소스 코드 를 대조 해 볼 수 있다.
1.요소 삽입
HashMap 을 삽입 할 때 new Node 를 호출 하여 노드 를 새로 만 들 거나 replacementNode 를 통 해 값 을 바 꿉 니 다.트 리 화 할 때 도 두 가지 대응 하 는 방법 이 있 는데 그것 이 바로 new TreeNode 와 replacement TreeNode 이다.완 료 된 후에 after NodeInsertion 방법 도 호출 되 었 습 니 다.이 방법 은 우리 가 삽입 이 완 료 된 후에 일 을 할 수 있 도록 해 주 었 습 니 다.기본 값 은 비어 있 습 니 다.
분석 을 편리 하 게 하기 위해 우 리 는 HashMap 의 실현 과 LinkedHashMap 의 실현 을 비교 하여 그것 이 어떻게 하 는 지 알 아 볼 것 이다.

// HashMap    
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
    return new Node<>(hash, key, value, next);
}

// LinkedHashMap    
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

// HashMap    
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

// LinkedHashMap    
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

// newTreeNode replacementTreeNode    

상기 비 교 를 통 해 알 수 있 듯 이 링크 드 HashMap 은 새로 추 가 했 을 때 링크 Node Last 를 호출 했 고 다시 교체 할 때 transferLinks 를 호출 했다.다음은 이 두 가지 방법의 실현 이다.

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

//  dst  src
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                            LinkedHashMap.Entry<K,V> dst) {  
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

마지막 으로 after Node Insertion 이 어떤 일 을 했 는 지 살 펴 보 자.

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

removeEldestEntry 는 요 소 를 삽입 할 때 가장 오래된 요 소 를 자동 으로 삭제 하려 면 복사 하 는 방법 입 니 다.기본 값 은 다음 과 같 습 니 다.

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

2.조회
접근 순 서 를 지원 해 야 하기 때문에 요 소 를 가 져 오 는 방법 과 HashMap 도 다르다.다음은 그 실현 을 살 펴 보 자.

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

getNode 방법 은 HashMap 에서 이 루어 졌 기 때문에 이것 은 HashMap 을 포장 하 는 방법 이 고 after Node Access 를 추 가 했 습 니 다.이 는 다음 과 같 습 니 다.

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

        //  e  ， b a   
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;

        // e    
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

자바 소스 코드 분석 에 관 한 링크 드 하 쉬 맵 에 관 한 글 은 여기까지 입 니 다.더 많은 자바 링크 드 하 쉬 맵 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부탁드립니다!