<K, V>型缓存：LRU策略 FIFO策略

这两种替换策略都是通过 LinkedHashMap 实现

LinkedHashMap：

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表+红黑树，在此基础上LinkedHashMap 增加了一条双向链表，保持遍历顺序和插入顺序一致的问题。

访问顺序存储的LinkedHashMap会把get方法对应的Entry节点放置在Entry链表表尾。LinkedHashMap构造函数有3个参数：

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)，其中：

initialCapacity：是初始数组长度

loadFactor：负载因子，表示数组的元素数量/数组长度超过这个比例，数组就要扩容

accessOrder：false：基于插入顺序(默认) true：基于访问顺序

当accessOrder为true，每次get元素的时候，都会去执行 afterNodeAccess 方法，这个方法会将元素重新插入到双向链表的结尾。

LinkedHashMap在HashMap的基础上使用一个双端链表维持有序的节点。这个有序并不是通常意义上的大小关系，默认情况下使用的插入顺序，意味着新插入的节点被添加到双端链表的尾部，而一旦使用了访问顺序，即accessOrder为true，那么在访问某一节点时，会将该节点移到双端链表的尾部。正因为此特性，可以在LinkedHashMap中使用三个参数的构造方法并制定accessOrder为true将LinkedHashMap实现为LRU缓存，这样经常访问的就会被移到链表的尾部，而越少访问的就在链表的头部。

由于双端链表维持了所有的节点，所以keySet()、values()以及entrySet()得到的键、值、键值对都是按照双端链表中的节点顺序的。

另外尤其需要注意的是，在put、get、remove方法中涉及到的双端链表的操作，由于都是引用的更改，所以并没有影响到HashMap的底层结构：数组+链表+红黑树。

LRU Cache：

LRU Cache 通过重写 removeEldestEntry() 方法实现元素替换，同时 accessOrder 参数设置为 true，表示使用访问顺序

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class FIFOCache<K, V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;

    LinkedHashMap<K, V> map;

    public FIFOCache(int cacheSize) {
        MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        /*
         * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存
         * 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
         */
        map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (Map.Entry<K, V> entry : map.entrySet()) {
            stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
        }
        return stringBuilder.toString();
    }
}

FIFO Cache：

accessOrder 参数设置为 false，表示使用插入顺序

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class FIFOCache<K, V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTORY = 0.75f;

    LinkedHashMap<K, V> map;

    public FIFOCache(int cacheSize) {
        MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1;
        /*
         * 第三个参数设置为true，代表linkedlist按访问顺序排序，可作为LRU缓存
         * 第三个参数设置为false，代表按插入顺序排序，可作为FIFO缓存
         */
        map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY, false) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (Map.Entry<K, V> entry : map.entrySet()) {
            stringBuilder.append(String.format("%s: %s  ", entry.getKey(), entry.getValue()));
        }
        return stringBuilder.toString();
    }
}

<K, V>型缓存：LRU策略 FIFO策略

<K, V>型缓存：LRU策略 FIFO策略

LinkedHashMap：

LRU Cache：

FIFO Cache：

推荐阅读