LinkedHashMap 원본 학습

묘사 하 다.

원 소 를 첨가 하 는 순서에 따라 원 소 를 교체 할 수 있 는 HashMap 하위 클래스.

주의 하 세 요. 위 에서 말 한 것 은 요 소 를 추가 하 는 순서 입 니 다. 즉, 요 소 를 업데이트 할 때 구조 에 영향 을 주지 않 습 니 다. 매개 변수 accessOrder 를 true 로 설정 하지 않 는 한 업데이트 요 소 를 팀 끝 에 두 십시오.

이러한 종 류 는 부모 류 HashMap 에 대해 너무 많은 재 작성 을 하지 않 았 다. 주로 실현 afterNode* 관련 방법 을 통 해 데이터 구조 가 변 경 된 후에 나중에 설 치 된 구조 업 데 이 트 를 유지 했다.

상용 과 관건 적 인 방법linkNodeLast 방법
설명:

구성원 변수 초기 화 head 와 tail 를 책임 집 니 다.

head 와 tail 초기 화 완료 후 목표 요소 p 를 tail 에 연결 하고 기 존 tail 을 목표 요소 p transferLinks

로 업데이트 합 니 다.
코드:

private void linkNodeLast(LinkedHashMap.Entry p) {
    //     
    LinkedHashMap.Entry last = tail;
    //         
    tail = p;
    //             
    if (last == null)
        //        ,         .       
        head = p;
    else {
        //       , p        
        p.before = last;
        last.after = p;
    }
}

dst 방법
설명:
양 방향 링크 의 위치 변경 src 사용 하기
코드:

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

newNode 방법
설명:
부모 클래스 newNode 방법 을 다시 썼 습 니 다. 양 방향 링크 의 연결 작업 을 확장 합 니 다. HashMap.Node 의 하위 노드 LinkedHashMap.Entry 를 되 돌려 주 었 습 니 다.
코드:

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

replacementNode 방법
설명:
양 방향 링크 교체 노드 를 확장 하 는 작업 입 니 다. 이 방법 은 부모 클래스 HashMap 에서 HashMap.TreeNode 를 HashMap.Node 로 교체 할 때 호출 되 었 습 니 다. 여기 서 재 작성 되 었 습 니 다. 양 방향 링크 가 있 는 LinkedHashMap.Entry 를 반환 값 으로 사용 합 니 다. 여기 HashMap.TreeNode 는 LinkedHashMap.Entry 를 실현 하 였 습 니 다. 즉, 매개 변수 p 입 니 다. 그 는 직접 실현 류 LinkedHashMap.Entry 로 강하 게 전환 할 수 있 습 니 다.
코드:

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

newTreeNode 방법
설명:
부모 클래스 방법 newTreeNode 을 다시 썼 습 니 다. 양 방향 링크 를 확장 하 는 연결 작업 입 니 다. 마찬가지 로 HashMap.TreeNode 이 실현 되 기 때 문 입 니 다 LinkedHashMap.Entry. 직접 linkNodeLast 방법 으로 연결 작업 을 할 수 있 습 니 다.
코드:

TreeNode newTreeNode(int hash, K key, V value, Node next) {
    TreeNode p = new TreeNode(hash, key, value, next);
    linkNodeLast(p);
    return p;
}

replacementTreeNode 방법
설명:
같은 replacementNode. 양 방향 링크 교체 노드 를 확장 하 는 작업 입 니 다. 노드 유형 만 TreeNode 으로 바 뀌 었 습 니 다. 또한 그 는 LinkedHashMap.Entry 의 하위 클래스 이기 때문에 transferLinks 에 직접 전달 할 수 있 습 니 다. 양 방향 링크 교체 작업 을 할 수 있 습 니 다.
코드:

TreeNode replacementTreeNode(Node p, Node next) {
    LinkedHashMap.Entry q = (LinkedHashMap.Entry)p;
    TreeNode t = new TreeNode(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

afterNodeRemoval 방법
설명:
노드 를 삭제 한 후 호출 합 니 다. 양 방향 링크 동기 화 를 진행 합 니 다.
코드:

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

afterNodeAccess 방법
설명:
노드 를 업데이트 한 후 호출 합 니 다. 양 방향 링크 동기 화 를 진행 합 니 다.
코드:

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

내부 류LinkedHashIterator
설명:
링크 구조 에 대한 교체 기 를 밀봉 하고 하위 클래스 에 공 통 된 확장 방법 을 제공 합 니 다.
코드:

abstract class LinkedHashIterator {
    LinkedHashMap.Entry next;
    LinkedHashMap.Entry current;
    int expectedModCount;

    LinkedHashIterator() {
        //    next     head
        next = head;
        expectedModCount = modCount;
        current = null;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final LinkedHashMap.Entry nextNode() {
        //   next
        LinkedHashMap.Entry e = next;
        // fast-fail
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        // next  
        if (e == null)
            throw new NoSuchElementException();
        //     
        current = e;
        //   next    
        next = e.after;
        return e;
    }

    public final void remove() {
        //     
        Node p = current;
        // null  
        if (p == null)
            throw new IllegalStateException();
        // fast-fail
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        //      
        current = null;
        //   key
        K key = p.key;
        //      removeNode        
        removeNode(hash(key), key, null, false, false);
        //       
        expectedModCount = modCount;
    }
}

내부 류LinkedHashIterator
설명:
각각 LinkedHashIterator 을 계승 하고 전자의 nextNode 방법 으로 서로 다른 데 이 터 를 되 돌려 주 었 다.
코드:

final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator {
    public final K next() { return nextNode().getKey(); }
}

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator {
    public final V next() { return nextNode().value; }
}

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator> {
    public final Map.Entry next() { return nextNode(); }
}