Java 实现 LRU 缓存淘汰策略

缓存空间的容量是有限的，当有新的数据要进入缓存空间时，如果缓存空间不足就必须按照缓存淘汰策略淘汰掉一些数据。

常用的缓存淘汰策略有：

• 先进先出（FIFO）：最先进入的内容作为淘汰对象
• 最近最少使用（LFU）：最近最少使用的内容作为淘汰对象
• 最久未使用（LRU）：最久没有访问的内容作为淘汰对象
• 非最近使用（NMRU）：在最近没有使用的内容中随机选择一个作为淘汰对象

在 Java 中实现 LRU 可以结合 HashMap 和双向链表实现，也可以基于 LinkedHashMap 实现。

结合 HashMap 和双向链表实现 LRU

import java.util.HashMap;
import java.util.Map;

/**
 * 结合 HashMap 和双向链表实现 LRU 缓存策略
 */
public class LRUCacheBasedOnHashMap {

    Map<Integer, Node> cache = new HashMap();

    int cacheCapacity;

    Node head;

    Node tail;

    public LRUCacheBasedOnHashMap(int cacheCapacity) {
        this.cacheCapacity = cacheCapacity;
    }

    // 追加尾部节点
    private void appendTail(Node node) {
        if (cache.size() == 0) {
            head = node;
            tail = node;
        } else {
            node.prev = tail;
            tail.next = node;
            tail = node;
            tail.next = null;
        }
    }

    // 从链表中移除节点
    private void removeNodeFromChain(Node node) {
        // 如果当前节点就是 head，将 head 设为当前节点的下一个
        if (node == head) {
            head = node.next;
        }

        // 如果当前节点就是 tail，将 tail 设为当前节点的上一个
        if (node == tail) {
            tail = node.prev;
        }

        // 如果前一个不是 null，将前一个的 next 设为当前节点的 next
        if (node.prev != null) {
            node.prev.next = node.next;
        }

        // 如果后一个不是 null，将后一个的 prev 设为当前节点的 prev
        if (node.next != null) {
            node.next.prev = node.prev;
        }
    }

    private void handleContainsKey(Node node) {
        if (node == tail) {
            // nothing to do
        } else if (node == head) {
            removeNodeFromChain(node);
            appendTail(node);
        } else {
            removeNodeFromChain(node);
            appendTail(node);
        }
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            handleContainsKey(node);
        } else {
            // 达到缓存容量极限，删除头部节点，腾出空间
            if (cache.size() == cacheCapacity) {
                cache.remove(head.key);
                removeNodeFromChain(head);
            }

            Node node = new Node(key, value);
            appendTail(node);
            cache.put(key, node);
        }

        listCache();
    }

    public Node get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            handleContainsKey(node);

            listCache();
            return node;
        }

        return null;

    }

    public void remove(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            removeNodeFromChain(node);
            cache.remove(key);
        }
    }


    private void listCache() {
        Node currentNode = head;

        System.out.print("当前缓存的key：");
        while (currentNode != null) {
            System.out.print(currentNode.key + " ");
            currentNode = currentNode.next;
        }

        System.out.println();

    }

    public static void main(String[] args) {
        int capacity = 4;
        LRUCacheBasedOnHashMap lru = new LRUCacheBasedOnHashMap(capacity);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.get(1);
        lru.put(5, 5);
        lru.put(6, 6);
        lru.get(5);


    }
}


class Node {

    int key;

    int value;

    Node prev;

    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }


}

基于 LinkedHashMap 实现 LRU

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;


/**
 * 基于 LinkedHashMap 实现 LRU 缓存策略
 */
public class LRUCacheBasedOnLinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    // 当缓存空间满了，删除访问时间最早的数据
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheCapacity;
    }

    int cacheCapacity;

    public LRUCacheBasedOnLinkedHashMap(int cacheCapacity) {
        // 设置 accessOrder = true 开启按访问顺序排序
        super(16, 0.75f, true);
        this.cacheCapacity = cacheCapacity;
    }

    public V put(K key, V value) {
        super.put(key, value);

        listCache(this);
        return value;
    }

    public V get(Object key) {
        V value = super.get(key);

        listCache(this);

        return value;
    }

    public static void listCache(Map map) {
        Set set = map.keySet();

        System.out.print("当前缓存的key：");
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next().toString() + " ");
        }

        System.out.println();

    }

    public static void main(String[] args) {
        int capacity = 4;
        LRUCacheBasedOnLinkedHashMap lru = new LRUCacheBasedOnLinkedHashMap(capacity);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.get(1);
        lru.put(5, 5);
        lru.put(6, 6);
        lru.get(5);


    }
}


class Node {

    int key;

    int value;

    Node prev;

    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }


}