https://labuladong.online/algo/data-structure/lru-cache/
LRU算法是一种常见的缓存淘汰策略，全称是Least Recently Used, 很久没使用的应该是无用的数据应该删除
LRU算法的核心数据结构是使用LinkedHashMap，首先借助链表的有序性使得插入的元素还是保持有序的状态，同时借助哈希映射的快速访问能力，O(1)任意元素。

1、算法的描述

首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。
注意哦，get 和 put 方法必须都是 O(1)的时间复杂度，我们举个具体例子来看看 LRU 算法怎么工作。

• LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体
• 1、显然操作的元素必须有序，用来区分最近使用和最久未使用；
• 2、我们要才cache中快速找到某个key，得到对应 的val
• 3、每次访问某个key，必须将这个元素变为最近使用，也就是支持任意位置插入和查找；

2、代码实现

from numpy.ma.core import swapaxes


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


class DoubleLinkedList:
    def __init__(self):
        """
             head           tail
            [0 | 0 ]  ->  [0 | 0 ]  ->> head
            pre next  ->  pre next
        """
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.next = self.head
        self.size = 0

    def addLast(self, x: Node):
        """
        在尾部添加节点
             head             x           tail
            [0 | 0 ]  ->  [0 | 0 ]  ->  [0 | 0 ]  ->> head
            pre next  ->  pre next   ->  pre next ->> head
        """
        x.prev = self.tail.prev
        x.next = self.tail
        self.tail.prev = x
        self.tail.prev.next = x
        self.size += 1

    def remove(self, x: Node):
        """
        移除某个节点，O(1)

             head             x           tail
            [0 | 0 ]  ->  [0 | 0 ]  ->  [0 | 0 ]  ->> head
            pre next  ->  pre next   ->  pre next ->> head
        """
        x.prev.next = x.next
        x.next.prev = x.prev
        self.size -= 1

    def removeFirst(self):
        """
        删除链表的第一个节点，O(1)
        """
        if self.head.next == self.tail:
            return None
        x = self.head.next
        self.remove(x)
        return x

    def length(self):
        """
        返回链表的长度
        """
        return self.size


class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = DoubleLinkedList()
        self.map = {}

    def addRecently(self, key, value):
        x = Node(key, value)
        # 尾部就是经常使用的
        self.cache.addLast(x)
        # 添加扫映射表
        self.map[key] = x

    def makeRecently(self, key):
        """
        将数据提升为最近使用的
        """
        x = self.map.get(key)
        # 删除数据
        self.cache.remove(x)
        # 重新添加数据
        self.cache.addLast(x)

    def removeLeastRecently(self):
        """
        链表的头就是最久未使用的
        """
        deleteNode = self.cache.removeFirst()
        deleteKey = deleteNode.key
        self.map.pop(deleteKey)

    def deleteKey(self, key):
        x = self.map.get(key)
        self.cache.remove(x)
        self.map.pop(key)

    def get(self, key):
        if key not in self.map.keys():
            return -1
        # 将该数据提升为最近使用的
        self.makeRecently(key)
        return self.map[key].value

    def put(self, key, value):
        if key in self.map.keys():
            self.deleteKey(key)
            self.addRecently(key, value)
            return
        if self.capacity == self.capacity:
            # 删除最久未使用的元素
            self.removeLeastRecently()
        self.makeRecently(key)

我们最后用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法，逻辑和之前完全一致：

• java LinkedHashMap实现

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

• python OrderedDict 实现

from collections import OrderedDict


class LRU:
    d = OrderedDict()

    def __init__(self, capacity):
        self.capacity = capacity

    def get(self, key):
        if key not in self.d:
            return -1
        self.makeRecently(key)
        return self.d.get(key)

    def put(self, key, value):
        if key in self.d:
            self.d[key] = value
            self.makeRecently(key)  # {1:1,2:2,3:3}
        else:
            # 判断容量
            if len(self.d) >= self.capacity:
                old_key, old_value = self.d.popitem(last=False)
                self.d.pop(old_key)
            self.d[key] = value

    def makeRecently(self, key):
        """
        把这个标记为最近使用的key
        """
        if key not in self.d:
            return -1
        self.d.move_to_end(key)


if __name__ == '__main__':
    d = OrderedDict()
    d[1] = 1
    d[2] = 2
    d[3] = 3
    print(d)
    d.popitem()
    print(d)

__END__