java缓存(三)——实现一个固定大小的对象缓存池

本文将介绍使用java语言实现一个对象缓存池。一步步的实现包括高速命中，固定大小的缓存队列等功能。

这一期我们终于能够动手编写一些代码，使用java来实现一个在内存中的对象缓存池。

不限大小的高速缓存池

最开始的需求是实现一个能够在单线程模式下，根据唯一主键key来缓存对象的功能。
对于java的集合类来说，能够得到近似的存取时间复杂度为O(1)的数据结构就是HashMap了，此处我们不再讲述其数据结构实现，简单的一段代码实现此功能：

public class ObjectCache {

    private Map<String, Object> cache;

    public ObjectCache() {
        cache = new HashMap<>();
    }

    public void put(String key, Object value) {
        cache.put(key, value);
    }

    public Object get(String key) {
        return cache.get(key);
    }

}

限制大小的高速缓存池

JVM的堆内存大小是有限的，如果一个缓存没有退出机制，永远只能往里面加入对象的话，那么最终就会导致堆内存溢出错误。所以一般来说我们都要限制缓存池的大小，以免内存耗尽。
那么当缓存对象达到最大限制大小后，用什么机制来淘汰过期的缓存对象呢？常用的有如下策略：

• FIFO
  此策略根据写入的时间排序，当需要淘汰时，首先淘汰最早写入的对象。
• LRU
  此策略根据最后读取的时间排序，当需要淘汰时，首先淘汰最后读取时间最早的对象。
• LFU
  此策略根据一段时间窗口内，总的读取次数排序，当需要淘汰时，首先淘汰时间窗口内读取次数最少的对象。

其中LFU实现比较复杂，需要使用滑窗计数器来帮助实现，后续会单独一篇文章来介绍此算法。这次我们先来了解比较简单的FIFO和LRU算法的实现。
我们最开始使用的HashMap是无序的，所以无法单独来实现读取或者写入的排序。我们考虑此场景，FIFO需要每次写入或者更新的时候都改变排序，而LRU每次读取的时候要改变排序，所以我们就需要一个能够排序的，而且很快速改变某个节点位置的数据结构。那么当然我们会想到LinkedList链表数据结构，其插入节点的时间复杂度为O(1)且能够保持节点次序，但是单独的LinkedList的查询时间复杂度又是O(N)，超出我们预期。所以此处我们需要将其结合使用，在使用HashMap提供高速查询写入的同时，又使用LinkedList来维护其插入或者最后读取的次序，同时我们在HashMap和LinkedList里维护同一个对象的引用，这样整体的存储空间保持基本不变。

其实JDK在1.7之后已经为我们提供了这样的数据结构：java.util.LinkedHashMap<K,V>
LinkedHashMap直接继承自HashMap类，同时在内部维护了一个双向链表，其实现为：

image.png

可以看到其内部的链表类LinkedHashMap.Entry继承自HashMap.Node，同时也实现了Map.Entry接口，这样就能在直接在链表中使用HashMap中的Node对象，从而保持同一个对象引用。
在LinkedHashMap.Entry类中，其before和after属性分别指向当前节点的前节点和后节点，而LinkedHashMap中也通过属性head和tail维护了此链表的头节点和尾节点：

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

LinkedHashMap通过重写了HashMap中创建节点的一些方法来在新增节点时维护链表数据：

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

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

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

这里可以看到，在HashMap的EntrySet数组中，根据hash碰撞的命中数量，采用链表和红黑树两种节点结构（JDK1.8以后），分别用newNode和newTreeNode插入节点，每次都把新的节点放在LinkedHashMap双向链表的最末尾。

同时我们来看HashMap中，在1.7之后为了LinkedHashMap提供了三个回调方法，其在HashMap中的默认实现为空：

    // Callbacks to allow LinkedHashMap post-actions
    // 访问节点的值后调用
    void afterNodeAccess(Node<K,V> p) { }
    // 插入新的节点后调用
    void afterNodeInsertion(boolean evict) { }
    // 删除节点后调用
    void afterNodeRemoval(Node<K,V> p) { }

而LinkedHashMap在继承HashMap后重写这三个方法：

    // 删除节点后被HashMap回调
    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<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;
    }

    // 插入新的节点后被HashMap回调
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    // 访问节点的值后被HashMap回调
    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

可以看到其中主要就是一些经典的链表操作，更新其次序；我们注意到accessOrder属性，其为true后才会在访问节点对象后更新其次序，我们来看其在LinkedHashMap中的定义：

    /**
     * The iteration ordering method for this linked hash map: true
     * for access-order, false for insertion-order.
     *  
     * @serial
     */
    final boolean accessOrder;

也就是当accessOrder为true时链表采用访问次序排序，为false时采用插入次序排序。其值在LinkedHashMap的构造函数中写入：

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        ……
    }

我们再来看afterNodeInsertion回调方法中调用的方法：removeEldestEntry，其默认实现永远返回false，那么就是说其实LinkedHashMap不会自动删除过期节点，需要我们自己继承后实现。
好了，既然如此，我们就来继承它来实现一个固定大小的对象缓存池吧：

public class FixedSizeCache<K, V> extends LinkedHashMap<K, V> {

    /**
     * 缓存池的最大大小
     */
    private int maxSize = 0;

    public FixedSizeCache(int initialCapacity,
                          float loadFactor,
                          boolean accessOrder,
                          int maxSize) {
        super(initialCapacity, loadFactor, accessOrder);
        this.maxSize = maxSize;
    }


    /**
     * 当前缓存大小已经大于maxSize后返回true，在新增节点后会删除一个最老的节点
     * 
     * @param eldest
     * @return
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > maxSize;
    }
    
}

好了，如此简单，当accessOrder为true时就是一个LRU缓存池，当为false时就是一个FIFO缓存池。当然此缓存池不保证线程安全，只能在单线程下使用了。