LinkedHashMap 및 그 응용 LruCache

LinkedHashMap
간단 한 소개
링크 드 하 쉬 맵 은 하 쉬 맵 의 하위 클래스 입 니 다.HashMap 을 바탕 으로 양 방향 링크 로 이 루어 졌 습 니 다.다시 말 하면 LinkedHashMap 의 모든 요 소 는 HashMap 의 데이터 구 조 를 만족 시 킬 뿐만 아니 라 LinkedList 의 구 조 를 만족 시 키 고 이 두 가지 실현 방식 을 유지 하고 있다.
링크 드 HashMap 류 는 주로 양 방향 링크 를 유지 하고 다른 작업 은 주로 HashMap 에서 이 루어 집 니 다.
LinkedHashMapEntry

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

주요 변수

transient LinkedHashMapEntry<K,V> head;   ，           ；
transient LinkedHashMapEntry<K,V> tail;   ，         ；
final boolean accessOrder;        ，         ；   false;  LruCache       ；

링크 드 하 쉬 맵 은 주로 하 쉬 맵 의 세 가지 빈 방법 을 실현 합 니 다.

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

put () 방법
put () 방법 은 HashMap 의 put () 방법 을 호출 하 는 것 입 니까? 주로 putVal () 에서 new Node () 방법 과 차이 가 있 습 니 다. LinkedHashMap 자신의 new Node () 방법 을 호출 합 니 다.다른 것 은 다 똑 같 습 니 다. 마지막 으로 Liked HashMap 방법 이 실현 되 었 습 니 다.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
		//1   LinkedHashMap newNode()    ；
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
			//2    key   ，afterNodeAccess() LinkedHashMap      ；
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
	//3      ，HashMap     ，LinkedHashMap      ；
    afterNodeInsertion(evict);
    return null;
}

LinkedHashMap 의 new Node () 방법;

//     ，       ，      ；
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMapEntry<K,V> p =
        new LinkedHashMapEntry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

//         ；
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
    LinkedHashMapEntry<K,V> last = tail;
	//        ；
    tail = p;
	//     null,  LinkedHashMap   ，head  null, head   ；
    if (last == null)
        head = p;
	//head    null，    ：  p before    last  ，last   after    p  ；
    else {
        p.before = last;
        last.after = p;
    }
}

after NodeAccess (): 방문 순서에 따라 정렬 되 고 방문 하 는 노드 가 끝 점 이 아니라면;현재 노드 를 링크 에서 삭제 하고 끝 점 에 삽입 한 후;

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

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

after NodeInsertion (): 양 방향 링크 에서 가장 오래된 노드 즉 머리 결산 점 을 삭제 합 니 다.기본적으로 removeEldestEntry () 는 false 를 되 돌려 줍 니 다.LruCache 클래스 는 다시 쓰 고 true 로 돌아 갑 니 다.

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

get () 방법
get (): 대응 하 는 값 을 가 져 오고 방문 정렬 에 따라 양 방향 링크 에서 현재 노드 e 를 삭제 한 다음 에 링크 끝 노드 에 삽입 합 니 다.양 방향 링크 의 순 서 를 바 꿉 니 다.

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

remove () 방법
reove (): HashMap 의 reove () 방법 을 완전히 호출 하고 삭제 한 후에 after Node Removal () 을 호출 하여 현재 노드 를 양 방향 링크 에서 삭제 합 니 다.

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMapEntry<K,V> p =
        (LinkedHashMapEntry<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;
}

LruCache
내부 에서 LinkedHashMap 을 구성원 변수 로 저장 요소 로 사용 합 니 다.key, value 는 null 일 수 없습니다.링크 드 HashMap 의 더 블 링크 와 방문 순서 에 따라 정렬 되 는 지 여부 에 따라 이 루어 집 니 다.주로 이미지 로드 프레임 워 크 에 사용 되 며 최근 최소 알고리즘 에 따라 자주 사용 되 지 않 는 그림 을 삭제 하고 공간 을 절약 합 니 다.
초기 화

LruCache<String, String> lruCache = new LruCache<String, String>(10) {
        //    1；   Bitmap      byte；
        @Override
        protected int sizeOf(String key, String value) {
			//super.sizeOf(key,value);
            return 2;
        }

        //         
        @Override
        protected void entryRemoved(boolean evicted, String key, String oldValue, String newValue) {
            super.entryRemoved(evicted, key, oldValue, newValue);
        }
    };

put () 방법: key 에 대응 하 는 노드 가 존재 하지 않 습 니 다. 새로운 노드 를 만 들 고 더 블 체인 체인 꼬리 에 추가 합 니 다.존재 하면 값 바 꾸 기;

 public final V put(K key, V value) {
    if (key == null || value == null) {
        throw new NullPointerException("key == null || value == null");
    }

    V previous;
    synchronized (this) {
        putCount++;
		//  value size,     sizeOf()  ，  value int ；       ；
        size += safeSizeOf(key, value);
		//  ，    key     ，      ，    null;
        previous = map.put(key, value);
		//    null，       
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }
	//entryRemoved     ，  ,      value;
    if (previous != null) {
        entryRemoved(false, key, previous, value);
    }
	//      size
    trimToSize(maxSize);
    return previous;
}

trimToSize () 방법: put () 방법 을 사용 한 후 현재 size 가 maxSize 보다 큰 지 판단 합 니 다. 크 면 최근 에 가장 적 게 사용 한 요 소 를 삭제 합 니 다 (즉, 더 블 체인 헤더 에서 두 노드 를 삭제 합 니 다).

 public void trimToSize(int maxSize) {
    while (true) {
        K key;
        V value;
        synchronized (this) {
            if (size < 0 || (map.isEmpty() && size != 0)) {
                throw new IllegalStateException(getClass().getName()
                        + ".sizeOf() is reporting inconsistent results!");
            }

            if (size <= maxSize) {
                break;
            }

            Map.Entry<K, V> toEvict = map.eldest();
            if (toEvict == null) {
                break;
            }

            key = toEvict.getKey();
            value = toEvict.getValue();
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
        }

        entryRemoved(true, key, value, null);
    }
}

get () 방법: key 에 대응 하 는 노드 가 존재 하고 해당 하 는 value 를 직접 되 돌려 줍 니 다.존재 하지 않 습 니 다. create (key) 방법 을 호출 합 니 다. 이 방법 은 기본적으로 null 로 돌아 갑 니 다.create () 방법 을 만들어 스스로 실현 할 수도 있다.

 public final V get(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V mapValue;
    synchronized (this) {
		//  key     value;
        mapValue = map.get(key);
        if (mapValue != null) {
            hitCount++;
            return mapValue;
        }
        missCount++;
    }

	//create    
    V createdValue = create(key);
    if (createdValue == null) {
        return null;
    }
	//create()     null
    synchronized (this) {
        createCount++;
		//  ，   oldVaue;
        mapValue = map.put(key, createdValue);
		//   ， create()  ，      value,      value  
        if (mapValue != null) {
            // There was a conflict so undo that last put
            map.put(key, mapValue);
		//  size
        } else {
            size += safeSizeOf(key, createdValue);
        }
    }

    if (mapValue != null) {
        entryRemoved(false, key, createdValue, mapValue);
        return mapValue;
    } else {
        trimToSize(maxSize);
        return createdValue;
    }
}

reove (): key 에 대응 하 는 노드 가 존재 합 니 다. 삭제 하고 size 를 줄 입 니 다.

 public final V remove(K key) {
    if (key == null) {
        throw new NullPointerException("key == null");
    }

    V previous;
    synchronized (this) {
        previous = map.remove(key);
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
    }

    if (previous != null) {
        entryRemoved(false, key, previous, null);
    }

    return previous;
}

모든 분석 내용 은 여기 서 끝 났 습 니 다.문제 가 있 으 면 많이 가르쳐 주세요. 감사합니다!