# LRU快取 (LRU Cache)

## 快取機制

LRU Cache 機制藉由資料取用的頻率和時間來做為快取的順序

需要實現的方法有兩個：

1. put(key,value)
把資料放入快取，放入的時候，會把資料的順序放在第一個

2. get()
取出資料，並把資料的順序更改到第一個

## 實現

一般的 LRU Cache 使用 Double Linked List + Hash Map 來實現

Double Linked List 裡面主要會儲存 key + value，會使用 Dobule Linked List 是因為要排序 LRU Cache 的順序

Dobule Linked List 會有一個 head 和一個 tail，用來定位最前面和最後面的節點，還有方便插入節點

Hash Map 的 value 是用來指向 node，眾所周知，Linked List 在查詢資料的時候需要花上 O(n) 的時間，所以使用 Hash Map 就可以把查詢快取的時候所短到 O(1)，結構如下:
**{ key: node (pointer) }**

LRU Cache 都會有一個數字 capacity 來限制快取大小，當快取的容量大於這個數字時，LRU Cache 就會移除掉最後一筆資料，來確保 Cache 不會溢出

class DListNode: # 雙向鏈表節點
    def __init__(self, key: int = -1, val: int = -1, prev = None, next = None):
        self.key = key
        self.val = val
        self.prev = prev
        self.prev = prev

class DLinkedList: # 雙向鏈表實現
    def __init__(self):
        self.head = DListNode()
        self.tail = DListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def insert(self, head: DListNode, node: DListNode, tail: DListNode) -> None:
        head.next = node
        node.prev = head
        node.next = tail
        tail.prev = node
    
    def insertToFirst(self, node: DListNode) -> None: # 插入節點到第一個位置
        head = self.head
        tail = self.head.next
        self.insert(head,node,tail)
    
    def remove(self, node: DListNode) -> None: # 移除節點
        print(node.key,node.val,node.prev,node.next)
        head = node.prev
        tail = node.next
        head.next = tail
        tail.prev = head
        node.prev = None
        node.next = None
    
    def changeOrderToFirst(self, node: DListNode) -> None: # 把節點的順序插入到第一個
        self.remove(node)
        self.insertToFirst(node)

class LRUCache(DLinkedList):
    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity
        self.current_capacity = 0
        self.hash_map = {}
    
    @property
    def reach_to_maximin_capacity(self) -> bool: # 查看是否超出 capacity
        return self.current_capacity > self.capacity

    def get(self, key: int) -> int:
        if key in self.hash_map: # 利用 Hash Map O(1) 的特性 查看是否在快取裡
            node = self.hash_map[key]
            self.changeOrderToFirst(node) # 把資料移到第一個位置
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.hash_map:
            node = DListNode(key,value) # 如果沒有就創建一個資料
            self.insertToFirst(node) # 插入到第一個
            self.hash_map[key] = node # 把節點指針方入 hash map
            self.current_capacity += 1 # 增加 capacity
            if self.reach_to_maximin_capacity: # 如果超出就移除，這裡有一個說法，就是其實在寫入資料之前，應該要先看有沒有溢出，如果有就先刪除在插入，才是比較好的做法
                node = self.hash_map[self.tail.prev.key] # 找到前面的節點
                del self.hash_map[self.tail.prev.key] # 刪除 hash map 裡的指針
                self.remove(node) # 移出雙向鏈表裡的節點
                self.current_capacity -= 1 # 修改 capacity
        else: # 如果有就把原本的節點找出來修改資料，並把順序移動到第一個
            node = self.hash_map[key]
            node.val = value
            self.changeOrderToFirst(node)

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