LeetCode 146. LRU缓存机制（中）

基于Python实现LRU（Least Recently Used）缓存算法

关键点 链表、hash map

题目来源 146. LRU缓存机制 LeetCode 题解

参考连接 看动画轻松理解「链表」实现「LRU缓存淘汰算法」 LeetCode官方题解

题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache(2); /* 缓存容量 */

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

直觉

使用双链表和哈希表实现LRU

哈希表的作用：保存key-value。

双向链表的作用：保存各个缓存的使用时间先后关系。

将所有Cache（缓存）的位置都用双链表连接起来，当一个位置被命中之后，通过调整链表的指向，将该位置调整到链表头的位置新加入的Cache直接加到链表头中。

这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而向链表后面移动，链表尾则表示最近最少使用的Cache。

当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

双链表

特点 1. 查询等操作的时间复杂度低 2. 空间复杂度高 3. 需要同时维护 next 和 prev 两个指针

添加元素：与单向链表相对比双向链表可以在 \(O(1)\) 时间复杂度搞定，而单向链表需要 \(O(n)\) 的时间复杂度。双向链表的添加元素包括头插法和尾插法。头插法：将链表的左边称为链表头部，右边称为链表尾部。头插法是将右边固定，每次新增的元素都在左边头部增加。尾插法：将链表的左边称为链表头部，右边称为链表尾部。尾插法是将左边固定，每次新增都在链表的右边最尾部。

查找元素：双向链表的灵活处就是知道链表中的一个元素结构就可以向左或者向右开始遍历查找需要的元素结构。因此对于一个有序链表，双向链表的按值查询的效率比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

删除元素：在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

  1. 删除结点中“值等于某个给定值”的结点
  2. 删除给定指针指向的结点

对于双向链表来说，双向链表中的结点已经保存了前驱结点的指针，删除时不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度。

算法

  • 如果此数据之前已经被缓存在链表中了，通过遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
  • 如果此数据没有在缓存链表中，可以分为两种情况：
    • 如果此时缓存未满，则将此结点直接插入到链表的头部；
    • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

复杂度分析

时间复杂度：对于 put 和 get 都是 \(O(1)\)。 空间复杂度：\(O(capacity)\)，因为哈希表最多存储 \(capacity + 1\) 个元素，而双向链表最多存储 \(capacity + 2\) 个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
# 定义双链表节点
class DLinkedNode():
    """bidirectional linked list
    """
    def __init__(self):
        self.key = 0
        self.val = 0
        self.prev = None
        self.next = None


# 定义LRU Cache类，有添加节点、删除节点、移动到链表开头、移动到链表结尾、删除链表尾结点、初始化、get函数 
class LRUCache():

    def __init__(self, capacity):
        self.cache = {}  # hash map负责保存DLinkedNode，双向链表负责保存使用时间。
        self.size = 0  # 保存当前已经存储的缓存数量
        self.capacity = capacity  # 保存该LRUCache能够保存的最多缓存数量
        self.head, self.tail = DLinkedNode(), DLinkedNode()  # head和tail起哑节点的作用
        self.head.next = self.tail
        self.tail.prev = self.head

    def addNode(self, node):
        """Always add the new node at the front of linkedlist
        """
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node
    
    def removeNode(self, node):
        """Remove an existing node from the linked list
        """
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev
    
    def moveToHead(self, node):
        """Move certian node to head
        """
        self.removeNode(node)  # 先删除
        self.addNodte(node)  # 后添加

    def popTailNode(self):
        """pop tail node in the DLinkedList
        """
        _node = self.tail.prev
        self.removeNode(_node)
        return _node

    def get(self, key):
        """get node which with the certain key
        """
        # p = self.head.next
        # while p:
        #     if p.key == key:
        #         # 在其中就返回 value
        #         return p.val
        # # 不在就返回 -1
        # return -1
        node = self.cache.get(key, None)
        if not node:
            return -1
        self.moveToHead(node)  # 只要访问过 就放到最前面
        return node.val

    def put(self, key, value):
        """put value into the node which with the certain key
        """
        node = self.cache.get(key)
        
        if not node:  # 新节点放到最前面
            newNode = DLinkedNode()
            newNode.key = key
            newNode.val = value
            self.cache[key] = newNode
            self.addNode(newNode)
            self.size += 1

            if self.size > self.capacity:
                tail = self.popTailNode()
                del self.cache[tail.key]
                self.size -= 1
        else:  # 之前已经存在的节点
            node.val = value
            self.moveToHead(node)


if __name__ == "__main__":
    cache = LRUCache (2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache.cache)
    print(cache.get(1))  # 返回  1
    cache.put(3, 3)      # 该操作会使得密钥 2 作废
    print(cache.cache)
    print(cache.get(2))  # 返回 -1 (未找到)
    cache.put(4, 4)      # 该操作会使得密钥 1 作废
    print(cache.cache)
    print(cache.get(1))  # 返回 -1 (未找到)
    print(cache.get(3))  # 返回  3
    print(cache.get(4))  # 返回  4