介绍

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

实现

最常见的实现是使用一个链表保存缓存数据，详细算法实现如下：

public class LRUCache<K, V> {

    /**
     * 节点类
     */
    class Node {
        /** 父节点 */
        Node parent;
        /** 子节点 */
        Node child;
        /** 散列表的键 */
        K key;
        /** 散列表的值 */
        V value;

        /**
         * 节点类的构造方法
         * @param key 散列表的键
         * @param value 散列表的值
         */
        private Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    /** 缓存的最大容量 */
    private final int capacity;

    /** 当前缓存的实际大小 */
    private int size;

    /** 头节点 */
    private Node root;

    /** 尾节点 */
    private Node tail;

    /**
     * LRU 缓存对象的构造方法
     * @param capacity 缓存的最大容量
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 根据散列表的键从缓存中取出散列表中对应的值
     * @param key 散列表的键
     * @return 散列表中对应的值
     */
    public V get(K key) {
        Node node = searchNode(key);
        if (node != null) {
            V value = node.value;
            //如果root节点是查找节点则无需提升节点
            if (node == root) {
                return value;
            }
            //进行节点提升
            setHeaderNode(node);
            return value;
        }
        return null;
    }

    /**
     * 向缓存中放入一组缓存键值
     * @param key 散列表的键
     * @param value 散列表的值
     */
    public void put(K key, V value) {
        if (root == null) {
            root = new Node(key, value);
            tail = root;
            size++;
            return;
        }
        if (get(key) != null) {
            root.value = value;
            return;
        }
        if (size < capacity) {
            size++;
        } else {
            //移除队尾节点
            //如果是尾节点是根节点
            if (tail == root) {
                root = null;
                tail = null;
            } else {
                //有且仅有根尾两个节点
                if (root.child == tail && tail.parent == root) {
                    root.child = null;
                    tail.parent = null;
                    tail = root;
                } else {
                    Node tempNode = tail.parent;
                    tail.parent = null;
                    tempNode.child = null;
                    tail = tempNode;
                }
            }
        }
        Node node = new Node(key, value);
        node.child = root;
        if (root != null) {
            root.parent = node;
        }
        root = node;
        if (tail == null) {
            tail = root;
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("size=");
        stringBuilder.append(size).append(",data=[");
        for (Node node = root; node != null; node = node.child) {
            stringBuilder.append(node.key).append("=").append(node.value).append(",");
        }
        if (stringBuilder.charAt(stringBuilder.length() - 1) == ',') {
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    /**
     * 根据key进行节点搜索
     * @param key key
     * @return 搜索到的节点
     */
    private Node searchNode(K key) {
        if (size < 1) {
            return null;
        } else if (size == 1) {
            return root.key.equals(key) ? root : null;
        } else if (size == 2) {
            return root.key.equals(key) ? root : tail.key.equals(key) ? tail : null;
        }
        Node left = root, right = tail;
        while (left != right && left.child != right && right.parent != left) {
            if (left.key.equals(key)) {
                return left;
            }
            if (right.key.equals(key)) {
                return right;
            }
            left = left.child;
            right = right.parent;
        }
        return left.key.equals(key) ? left : right.key.equals(key) ? right : null;
    }

    /**
     * 将指定节点提升到根节点
     * @param target 指定的节点
     */
    private void setHeaderNode(Node target) {
        Node source = root;
        //只有两个节点
        if (size == 2) {
            source.parent = target;
            target.child = source;
            source.child = null;
            target.parent = null;
            root = target;
            tail = source;
        } else if (target == tail) {
            //尾节点需要提升到根节点
            target.parent.child = null;
            tail = target.parent;
            target.parent = null;
            target.child = source;
            source.parent = target;
            root = target;
        } else {
            //中间节点需要提升到根节点
            Node tempNode1 = target.child;
            Node tempNode2 = target.parent;
            tempNode1.parent = tempNode2;
            tempNode2.child = tempNode1;
            target.child = source;
            source.parent = target;
            target.parent = null;
            root = target;
        }
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        LRUCache<Integer, Integer> cache = new LRUCache<>(2048);
        Random random = new Random();
        for (int i = 0;i < 5000;i++) {
            int value = random.nextInt(1000);
            if (random.nextBoolean()) {
                cache.put(value, value);
            } else {
                System.out.println(cache.get(value));
            }
        }
        System.out.printf("running time: %dms", System.currentTimeMillis() - start);
    }