LRU算法

LRU(Least Recently Used)算法，即最近最少使用算法，是置换算法(也叫淘汰算法)的一种，最早是在学习操作系统时接触的。

原理

当内存不足时，选择淘汰最久未使用的页面。

实现方法

实现方法有两种。

计时法

对于每个页面增加一个访问时间计时器。每当一个页面被访问时，当时的绝对时钟时间记录到被访问页面的计时器中；淘汰时，选取访问时间计时器中值最小的页面淘汰。

双向链表法(常用)

按照页面最后一次访问的时间次序将页面依次排列，最近被访问的页面排在队首，之前最久被访问的页面排在队尾。当一个页面被访问时，将这个页面排到队首；淘汰时，直接淘汰队尾那个最久未使用的页面即可。

LeetCode上实现LRU算法的题目：146. LRU 缓存。

• 使用Java JDK中封装的数据结构LinkedHashMap实现

public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

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

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

• 使用哈希表+双向链表实现

public static class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> hashMap = new HashMap<>();
    private int size;
    private Node head = new Node();
    private Node tail = new Node();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return -1;
        }
        // 移动该节点到表头第一位置
        moveNewestNode(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = hashMap.get(key);
        if (node == null) {
            node = new Node(key, value);
            hashMap.put(key, node);
            // 添加该节点到表头第一位置
            addNode(node);
        } else {
            node.value = value;
            // 移动该节点到表头第一位置
            moveNewestNode(node);
            return;
        }
        if (size > capacity) {
            // 删除最老的节点
            removeEldestNode(tail.pre);
        }
    }

    /**
      * 向链表开头添加元素
      *
      * @param node 节点
      */
    private void addNode(Node node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
        size++;
    }

    /**
      * 移动节点到表头
      *
      * @param node 节点
      */
    private void moveNewestNode(Node node) {
        Node pre = node.pre, next = node.next;
        if (pre != null && next != null) {
            pre.next = next;
            next.pre = pre;
        }
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    /**
      * 删除最老的节点
      *
      * @param node 节点
      */
    private void removeEldestNode(Node node) {
        Node pre = node.pre, next = node.next;
        pre.next = next;
        next.pre = pre;
        node.pre = null;
        node.next = null;
        hashMap.remove(node.key, node);
        size--;
    }

    private class Node {
        private int key;
        private int value;
        private Node pre;
        private Node next;
        public Node() {
        }
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}