LinkedHashMap实现缓存及LRU算法

>>最全面的Java面试大纲及答案解析(建议收藏)  

平时的项目中,为了提高运行速度,我们都会用到缓存,而缓存内存容量是有限的,那么应该如何实现呢?在Java中提供了一个自动清理最老元素的LinkedHashMap类,通过重写removeEldestEntry(java.util.Map.Entryeldest)这个方法,当插入元素时,该方法会判断是否达到缓存上限,如果达到缓存的上限,则会移除掉最老的元素。具体代码如下所示:

public class LruLinkedHashMapCache<KVextends LinkedHashMap<KV{
    private final int maxCapacity;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public LruLinkedHashMapCache(int maxCapacity) {
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
        this.maxCapacity = maxCapacity;
    }

    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        // 当达到预设缓存上限时删除最老元素
        return this.size() > maxCapacity;
    }

    public static void main(String[] args){
        LruLinkedHashMapCache<String, String> cache = new LruLinkedHashMapCache<String, String>(3);
        cache.put("a""a");
        cache.put("b""b");
        cache.put("c""c");
        cache.put("a""a");
        cache.put("d""d");
        System.out.println(cache);
    }
}

输出结果如下:

LinkedHashMap实现缓存及LRU算法

从输出结果可以看出,当缓存满了的时候,就会remove掉最远使用的那个元素。LinkedHashMap默认的元素顺序是put的顺序,LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端,当内存容量满了的时候,这样一来每次顶端的元素就是remove的元素。

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为true时,此时会调用afterNodeAccess()方法:

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;
        }
    }

我们访问的节点Node会移动到最后,使之成为尾部节点,从而改变了数据在LinkedHashMap中的存储顺序。

LRU算法

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

LinkedHashMap实现缓存及LRU算法

  1. 新数据插入到链表头部;

  2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

  3. 当链表满的时候,将链表尾部的数据丢弃。

具体实现如下所示:

public class LRUCache {
    private int cacheSize;//缓存大小
    private Hashtable nodes;//缓存容器
    private int currentSize;//当前缓存对象数量
    private CacheNode first;//(实现双链表)链表头
    private CacheNode last;//(实现双链表)链表尾

    class CacheNode {
        CacheNode prev;//前一节点
        CacheNode next;//后一节点
        Object value;//值
        Object key;//键

        CacheNode() {
        }
    }

    public LRUCache(int i) {
        currentSize = 0;
        cacheSize = i;
        nodes = new Hashtable(i);//缓存容器
    }

    /**
     * 获取缓存中对象
     *
     * @param key
     * @return
     */

    public Object get(Object key) {
        CacheNode node = (CacheNode) nodes.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        } else {
            return null;
        }
    }

    /**
     * 添加缓存
     *
     * @param key
     * @param value
     */

    public void put(Object key, Object value) {
        CacheNode node = (CacheNode) nodes.get(key);

        if (node == null) {
            //缓存容器是否已经超过大小.
            if (currentSize >= cacheSize) {
                if (last != null)//将最少使用的删除
                    nodes.remove(last.key);
                removeLast();
            } else {
                currentSize++;
            }

            node = new CacheNode();
        }
        node.value = value;
        node.key = key;
        //将最新使用的节点放到链表头,表示最新使用的.
        moveToHead(node);
        nodes.put(key, node);
    }

    /**
     * 将缓存删除
     *
     * @param key
     * @return
     */

    public Object remove(Object key) {
        CacheNode node = (CacheNode) nodes.get(key);
        if (node != null) {
            if (node.prev != null) {
                node.prev.next = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            }
            if (last == node)
                last = node.prev;
            if (first == node)
                first = node.next;
        }
        return node;
    }

    public void clear() {
        first = null;
        last = null;
    }

    /**
     * 删除链表尾部节点
     * 表示 删除最少使用的缓存对象
     */

    private void removeLast() {
        //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象)
        if (last != null) {
            if (last.prev != null)
                last.prev.next = null;
            else
                first = null;
            last = last.prev;
        }
    }

    /**
     * 移动到链表头,表示这个节点是最新使用过的
     *
     * @param node
     */

    private void moveToHead(CacheNode node) {
        if (node == first)
            return;
        if (node.prev != null)
            node.prev.next = node.next;
        if (node.next != null)
            node.next.prev = node.prev;
        if (last == node)
            last = node.prev;
        if (first != null) {
            node.next = first;
            first.prev = node;
        }
        first = node;
        node.prev = null;
        if (last == null)
            last = first;
    }
}

以上便是双链表的LRU实现,将Cache的所有位置都用双链表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。


原文始发于微信公众号(一盏红茶):LinkedHashMap实现缓存及LRU算法