LRU原理及实现是怎样的

LRU（Least Recently Used，最近最少使用）原理是：如果数据最近被访问过，那么将来被访问的几率也更高。 LRU的实现方式： 1. 使用双向链表，每次访问一个数据时，将其从原来的位置删除，放到链表头部； 2. 使用哈希表来加快寻找数据，哈希表存储数据和链表节点的映射关系；

// 利用双向链表实现LRU
public class LRUCache {
// 双向链表节点
class Node {
    int key;
    int value;
    Node pre;
    Node next;
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

// 哈希表
private HashMap map;
// 链表头节点
private Node head;
// 链表尾节点
private Node tail;
// 链表容量
private int capacity;

public LRUCache(int capacity) {
    this.capacity = capacity;
    map = new HashMap<>();
    head = new Node(0, 0);
    tail = new Node(0, 0);
    head.next = tail;
    tail.pre = head;
}

public int get(int key) {
    if (!map.containsKey(key)) {
        return -1;
    }
    // 将节点移到链表头部
    Node node = map.get(key);
    moveToHead(node);
    return node.value;
}

public void put(int key, int value) {
    Node node = map.get(key);
    if (node == null) {
        // 添加新节点
        node = new Node(key, value);
        map.put(key, node);
        addToHead(node);
        // 如果超出容量，则删除最后一个节点
        if (map.size() > capacity) {
            Node tailNode = popTail();
            map.remove(tailNode.key);
        }
    } else {
        // 更新节点
        node.value = value;
        moveToHead(node);
    }
}

// 将节点移动到链表头部
private void moveToHead(Node node) {
    removeNode(node);
    addToHead(node);
}

// 将节点添加到链表头部
private void addToHead(Node node) {
    node.next = head.next;
    node.pre = head;
    head.next.pre = node;
    head.next = node;
}

// 删除节点
private void removeNode(Node node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

// 弹出链表尾部节点
private Node popTail() {
    Node node = tail.pre;
    removeNode(node);
    return node;
}
}