如何自己实现一个LRU Cache

如何自己实现一个LRU Cache

LRU是Least Recently Used的缩写，即最近最少使用的淘汰，在内存有限的情况下，可以使用这种算法，保持内存中是最热的数据。

思路

lru有两种实现方法，可以通过HashMap+双向链表的形式实现，保证最近访问的放在尾部，最长时间未访问的放在头部就可以了，也可以直接通过LinkedHashMap实现。

实现

HashMap+双向链表实现

public class LruCache {
    /**
     * 缓存容量
     */
    private int capacity;
    /**
     * 头结点
     */
    private Node head;
    /**
     * 尾结点
     */
    private Node tail;
    /**
     *
     */
    private Map<String, Node> cache;

    public LruCache(int capacity) &#123;
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.pre = head;
    &#125;

    class Node &#123;
        String key;
        Object value;
        Node pre;
        Node next;

        Node(String key, Object value) &#123;
            this.key = key;
            this.value = value;
        &#125;

    &#125;

    public void set(String key, Object value) &#123;
        Node node = cache.get(key);
        // 已存在，更新value并且移动到尾部
        if (Objects.nonNull(node)) &#123;
            node.value = value;
            cache.put(key, node);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            nodeMoveToTail(node);
            return;
        &#125;
        // cache已满，移除head元素
        if (cache.size() == capacity) &#123;
            Node tmp = head.next;
            head.next = head.next.next;
            head.next.pre = head;
            cache.remove(tmp.key);
        &#125;
        node = new Node(key, value);
        nodeMoveToTail(node);
        cache.put(key, node);
    &#125;

    public Object get(String key) &#123;
        Node node = cache.get(key);
        if (Objects.nonNull(node)) &#123;
            node.pre.next = node.next;
            node.next.pre = node.pre;
            nodeMoveToTail(node);
            return node.value;
        &#125;
        return null;
    &#125;

    private void nodeMoveToTail(Node node) &#123;
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    &#125;

LinkedHashMap实现

HashMap+LinkedList？？？这不就是LinkedHashMap吗，LinkedHashMap就是在HashMap的基础上增加了链表，用于维护元素的顺序，使用LinkedHashMap实现就比较简单了，代码如下：

public class LruCache {
    /**
     * 缓存容量
     */
    private int capacity;
    private Map<String, Object> cache;

    public LruCache(int capacity) &#123;
        this.capacity = capacity;
        // 记录访问顺序设置为true
        cache = new LinkedHashMap<String, Object>(capacity, 0.75f, true) &#123;
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Object> eldest) &#123;
                return size() > capacity;
            &#125;
        &#125;;
    &#125;

    public Object get(String key) &#123;
        return cache.get(key);
    &#125;

    public void set(String key, Object value) &#123;
        cache.put(key, value);
    &#125;

    @Override
    public String toString() &#123;
        return "LruCache&#123;" +
                "cache=" + cache.toString() +
                '&#125;';
    &#125;
&#125;

验证

   public static void main(String[] args) {
        LruCache cache = new LruCache(3);
        cache.set("key1", 1);
        cache.set("key2", 2);
        cache.set("key3", 3);
        System.out.println(cache.toString());
        cache.get("key1");
        System.out.println(cache.toString());
        cache.set("key4", 4);
        System.out.println(cache.toString());
    }

总结

基于LinkedHashMap的缓存实现在很多地方都有实现，需要平时用心去观察。比如在SpringBoot中的SpringBootConfigurationFinder类

final class SpringBootConfigurationFinder {
    private static final Map<String, Class<?>> cache = Collections.synchronizedMap(new SpringBootConfigurationFinder.Cache(40));

    ...省略
    private static class Cache extends LinkedHashMap<String, Class<?>> &#123;
        private final int maxSize;

        Cache(int maxSize) &#123;
            super(16, 0.75F, true);
            this.maxSize = maxSize;
        &#125;

        protected boolean removeEldestEntry(Entry<String, Class<?>> eldest) &#123;
            return this.size() > this.maxSize;
        &#125;
    &#125;
&#125;

可以看出直接实现的lru缓存因为继承的是基础的Map类，所以是线程不安全的，在多线程环境下请包装成线程安全的Map类进行使用。