LRU (最近最少使用) 缓存

相关算法题：LRU 缓存 - LeetCode

LinkedHashMap 实现 LRU #

Java 其实是自带 LRU 缓存的，继承 LinkedHashMap 做简单的修改就能实现 LRU 缓存，需要在构造方法传参数 accessOrder 为 true，并重写 removeEldestEntry 方法在插入新元素后判断 size 是不是已经超过缓存容量，超过了会淘汰一个元素。

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
  private final int cacheSize;

  public LRUCache(int cacheSize) {
    super(cacheSize, 0.75f, true);
    this.cacheSize = cacheSize;
  }

  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > cacheSize;
  }
}

手撕 LRU #

如果你觉得调 API 不能展现你的技术水平，那我们试试自己写一个 LRU 缓存吧。

LRU 缓存是淘汰最近最少使用的 key ，使用哈希表和双链表实现 LRU 缓存，只需每次访问都将节点移动到链表尾部，淘汰时淘汰头部节点即可。这个方案 get 和 put 的时间复杂度为 O(1) ，Java 实现如下：

public class LRUCache<K, V> {

    static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> pre, next;

        Node(K key) {
            this.key = key;
        }
    }

    final int capacity;
    final Map<K, Node<K, V>> map;

    Node<K, V> head;// eldest
    Node<K, V> tail;// youngest

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
    }

    public V get(K key) {
        if (capacity == 0) return null;
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToTail(node);
        return node.value;
    }

    public V put(K key, V val) {
        if (capacity == 0) return null;
        Node<K, V> node = map.get(key);
        V old;
        if (node != null) {
            old = node.value;
        } else {
            old = null;
            if (map.size() == capacity) {
                removeEldest();
            }
            map.put(key, node = new Node<>(key));
        }
        node.value = val;
        moveToTail(node);
        return old;
    }

    private void moveToTail(Node<K, V> node) {
        if (node == tail) return;
        if (head == null) {
            head = node;
            tail = node;
            return;
        }

        Node<K, V> n = node.next;

        // unlink
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        }
        node.pre = null;
        node.next = null;

        if (node == head) {
            head = n;
            if (head != null) {
                head.pre = null;
            }
        }

        // link to tail
        tail.next = node;
        node.pre = tail;
        tail = node;
    }

    private void removeEldest() {
        if (head == null) return;
        Node<K, V> h = head;
        head = h.next;
        h.next = null;
        if (head != null) {
            head.pre = null;
        }
        map.remove(h.key);
    }
}

如果想让这个 LRU 缓存支持并发操作，可以考虑使用读写锁来保证多线程安全，当然加读写锁并不是最优解，如果追求极致的并发性能就比较复杂了，可以去看看 Caffeine 和 Guava 是如何实现的。

测试用例 #

class LRUCacheTest {

    @Test
    void test() {
        LRUCache<Integer, Integer> cache = new LRUCache<>(3);
        assertNull(cache.put(1, 1));
        assertNull(cache.put(2, 2));
        assertNull(cache.put(3, 3));
        assertEquals(1, cache.get(1));
        assertEquals(3, cache.put(3, 3));
        assertNull(cache.put(4, 4));
        assertNull(cache.get(2));
        assertEquals(4, cache.get(4));
        assertNull(cache.put(5, 5));
        assertNull(cache.get(1));
        assertEquals(4, cache.get(4));
        assertEquals(5, cache.get(5));
    }
}