11、LRU（Least Recently Used）算法

1、LRU是什么

LRU（Least Recently Used）最近最少使用，

package com.algorithm;

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

/**
 * LRU算法（Least recently used）最近最少使用
 * 要求：查找、删除时间复杂度都为 O(1)
 * 使用双向链表 + 哈希表实现
 */
public class LRUCache {
    /**
     * 双向链表
     */
    class LinkedNode {
        int key;
        int value;
        LinkedNode pre;
        LinkedNode next;

        public LinkedNode() {
        }

        public LinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, LinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private LinkedNode head;
    private LinkedNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 使用伪头尾节点，防止越界
        head = new LinkedNode();
        tail = new LinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        LinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // key 存在，通过哈希表定位，移动到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        LinkedNode node = cache.get(key);
        // 哈希表中 key 不存在则新建节点
        if (node == null) {
            LinkedNode newNode = new LinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > this.capacity) {
                LinkedNode removeTail = removeTail();
                cache.remove(removeTail.key);
                --size;
            }
        }
        // 哈希表中存在 key
        else {
            // 更新值，并移动到头部
            node.value = value;
            moveToHead(node);
        }
    }

    /**
     * 在头部添加节点
     * head 1
     * head node 1
     *
     * @param node
     */
    private void addToHead(LinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    /**
     * 删除节点
     * 1 2 3
     * 1 3
     *
     * @param node
     */
    private void removeNode(LinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    /**
     * 删除尾部节点
     * 1 2 tail
     * 1 tail
     */
    private LinkedNode removeTail() {
        LinkedNode ans = tail.pre;
        removeNode(ans);
        return ans;
    }

    /**
     * 将节点移动到头部
     * 1 2 3 -> 1 2
     * 1 2 -> 3 1 2
     *
     * @param node
     */
    private void moveToHead(LinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 打印当前 LRUCache 的值
     */
    private void printLRUCache() {
        LinkedNode res = head.next;
        while (res != null && res != tail) {
            System.out.print(res.value);
            res = res.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 1, 4, 2, 1, 5, 8, 3};
        LRUCache cache = new LRUCache(3);
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            cache.put(arr[i], arr[i]);
            cache.printLRUCache();
        }
    }
}