LRU缓存机制的实现

leetcode 146.

LRU(Least Recently Used)是一种缓存替换策略。现实生活中，缓存的大小总是有限的，为了合理地利用缓存，在缓存满了以后需要利用合适的替换策略把某些内容从缓存中移出，以腾出空间给新的元素。LRU就是其中一种常见的策略，它把缓存中最不常访问到的数据移出。
为了实现LRU，可以利用哈希表+双向链表。哈希表以键值对的形式保存元素，并以O(1)的时间复杂度取出元素；双向链表用于记录每个元素的使用情况。具体如下：

• 每次缓存新元素时，都把它放在表尾（如果缓存中已存在该元素，把它移动到表尾）
• 每次获取元素时，也把该元素移动到表尾
• 这样就可以保证链表第一个元素始终是最不常使用的元素，在缓存满时只需要移除第一个元素即可

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.cache = {}
        self.head = Node(-1, -1)
        self.tail = self.head


    def get(self, key: int) -> int:
        if key in self.cache:
            e = self.cache[key]

            # 把元素移到表尾
            self.move2end(e)
            return e.value

        return -1


    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            if self.size < self.capacity:
                self.size += 1
            else:
                # 满了，移除第一个元素
                out = self.head.next_

                if out != self.tail:
                    self.head.next_ = out.next_
                    out.next_.prev = self.head
                else:
                    self.head.next_ = None
                    self.tail = self.head

                self.cache.pop(out.key)

            # 添加新元素到表尾
            e = Node(key, value)
            self.tail.next_ = e
            e.prev = self.tail
            self.tail = e
            self.cache[key] = e
        else:
            e = self.cache[key]
            e.value = value

            # 把元素移到表尾
            self.move2end(e)
    
    def move2end(self, e):
        """把e移到链表末尾."""
        if e != self.tail:
            prev = e.prev
            next_ = e.next_

            prev.next_ = e.next_
            next_.prev = prev

            self.tail.next_ = e
            e.prev = self.tail
            e.next_ = None
            self.tail = e


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


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

参考：
[1] https://zhuanlan.zhihu.com/p/76553221