LRUCache

介绍

LRUCache 缓存的容量大小是固定的，当添加对象时，发现超出容量时，优先把那些最近没有访问的对象移除缓存。

缓存策略中，LRU是基于访问时间的，即最近被访问的对象存活可能行最大，除此之外，还有LFU（基于访问频率），优先移除访问频率最小的。

实现原理

主要的实现原理就是使用了LinkedHashMap，在其构造方法中，设置元素排序按照访问顺序来排（accessOrder=true），而非默认的按插入排序。
当访问元素时，将该结点移动到末尾，而删除元素时，总是优先删除队首的元素，这样便能实现“保留最近使用”。

源码

构造

public class LruCache<K, V> {


   /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;   //当前缓存块的个数
    private int maxSize;


    private final LinkedHashMap<K, V> map;

    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        
        // 初始容量 0    map可以放置结点的个数
        // 负载因子 0.75    决定什么时候resize
        // accessOrder true     设置排序根据访问时间
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }
}

获取一个元素

/**
     * Returns the value for {@code key} if it exists in the cache or can be
     * created by {@code #create}. If a value was returned, it is moved to the
     * head of the queue. This returns null if a value is not cached and cannot
     * be created.
     */
    @Nullable
    public final V get(@NonNull K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        V mapValue;
        synchronized (this) {
            // linkedHashMap内部会将该节点移到末尾
            mapValue = map.get(key);
            if (mapValue != null) {
                hitCount++;
                return mapValue;
            }
            missCount++;
        }

        /*
         * Attempt to create a value. This may take a long time, and the map
         * may be different when create() returns. If a conflicting value was
         * added to the map while create() was working, we leave that value in
         * the map and release the created value.
         */
        
        // 当想要获取的元素不存在时，可以为此创建一个
        V createdValue = create(key);
        if (createdValue == null) {
            return null;
        }
        
        synchronized (this) {
            createCount++;
            mapValue = map.put(key, createdValue);

            if (mapValue != null) {
                // There was a conflict so undo that last put
                map.put(key, mapValue);
            } else {
                size += safeSizeOf(key, createdValue);
            }
        }

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

#### 放入一个元素

    /**
     * Caches {@code value} for {@code key}. The value is moved to the head of
     * the queue.
     *
     * @return the previous value mapped by {@code key}.
     */
    @Nullable
    public final V put(@NonNull K key, @NonNull V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            // 不管不顾，先将该节点插入
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            //若是放置的key已经存在，该存在的节点该如何处理，将该实现跑出来
            entryRemoved(false, key, previous, value);
        }
    
        //若是放置后，大小已经超出额定大小，将老元素置换出去
        trimToSize(maxSize);
        return previous;
    }

### 清除超出缓存大小的区域
    /**
     * Remove the eldest entries until the total of remaining entries is at or
     * below the requested size.
     *
     * @param maxSize the maximum size of the cache before returning. May be -1
     *            to evict even 0-sized elements.
     */
    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 || map.isEmpty()) {
                    break;
                }

                //什么元素该驱逐？
                //优先首端元素
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }
            
            entryRemoved(true, key, value, null);
        }
    }

}