美文网首页
java缓存(三)——实现一个固定大小的对象缓存池

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

作者: 郭亮_fa85 | 来源:发表于2020-02-07 20:45 被阅读0次

    本文将介绍使用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缓存池。当然此缓存池不保证线程安全,只能在单线程下使用了。

    相关文章

      网友评论

          本文标题:java缓存(三)——实现一个固定大小的对象缓存池

          本文链接:https://www.haomeiwen.com/subject/rpcpxhtx.html