LRU(Least Recently Used) 表示最近最少使用

LinkedHashMap

LRU内部维护的是一个LInkedHashMap,因此先从LinkedHashMap看起

LinkedHashMap与HashMap的区别:
LinkedHashMap保持了元素的插入顺序,使得遍历顺序可按插入顺序输出

盗图来查看LinkedHashMap的内部结构

image.png

说白了就是每个结点即是HashMap里每个桶的结点也是一条双向链表里的结点。
而LinkedHashMap依靠该双向链表保存着插入的顺序

这三个方法是HashMap预留给LinkedhashMap的接口,

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

首先看afterNodeAccess，当为accessOrder的时候，就把结点放到末尾

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
            // 省略一堆指针的操作，就是将读取到的结点e 放到链表末尾
            ++modCount;
        }
    }

afterNodeInsertion 参数evict 必为true
若用户定义了removeEldestEntry 就会在哈希表中移除链表的表头元素，而removeEldestEntry默认返回false

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

afterNodeRemoval() 用于从链表中删除结点

    void afterNodeRemoval(Node<K,V> e) { // unlink
       //省略,其实也是指针操作,从链表中删除该结点
    }

LinkedHashMap对put操作没有重写,而对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的时候就执行afterNodeAccess();

因此当LinkedHashMap设置成accessOrder并定义removeEldestEntry，
该双向链表的特性不就是刚被访问过的结点将在链表表尾，
插入的时候可根据removeEldestEntry决定是否要删除表头元素。
因此很适合构建LRU缓存

LRU_Cache

image.png

LruCache的构造函数如图，可见他将accessOrder设置成TRUE了。
然而LruCache并没有使用removeEldestEntry的返回值来决定是否删除元素。而是使用trimToSize方法删除超出lrucache大小的最旧的元素。

在每次put的时候会调用trimToSize来保证大小小于maxSize

    private void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size <= maxSize) {
                    break;
                }
                 Map.Entry<K, V> toEvict = map.eldest();
                for (Map.Entry<K, V> entry : map.entrySet()) {
                    toEvict = entry;
                }
                // END LAYOUTLIB CHANGE
                if (toEvict == null) {
                    break;
                }
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            entryRemoved(true, key, value, null);
        }
    }