什麼是LRU快取淘汰機制
LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。
LRU正如我們日常生活時使用手機那樣子：我們會打開多個應用，在後台應用管理可以看到你打開的應用列表，最近的開的排的靠前，比較舊的沒用就靠的比較後了。可是，要知道，我們的手機記憶體是有限的，如果開太多應用，把記憶體都佔滿，那麼手機就特別卡了。所以，在這時候，手機會自動清理記憶體，過程如下：會將最久未使用的應用程式進程停止（判定為無用的數據），就是按照時間來，然後停掉倒數第二久未使用的應用……以此類推，直到有足夠空間才停止清理。如果你又去訪問未停止的應用，那麼他就跳到了我們後台應用列表的第一個了。
LRU演算法就是這樣的，將最久、最少使用的數據進行淘汰。
如果叫我們設計一個LRU演算法如何設計呢？
-
要接受一個最大的快取容量 capacity
-
實現兩個方法：
- get(int key)：獲取key對應的val
- put(int key, int value)：存入新的鍵值對，如果存在的話就更新val
- 注意：不管是訪問，還是添加 已存在 / 不存在 鍵值對，那麼就說明訪問了該數據
-
使用雙向鏈表和哈希表的結合實現LRU演算法: 哈希表的查找速度快,但是是無序的; 而鏈表是有序的, 但是查找速度慢, 為\(O(N)\), 所以我們可以利用這兩個特性,結合起來,形成了哈希鏈表, 這樣的話,get和put都是\(O(1)\)的時間複雜度了, 圖解如下:
這對應力扣上面的142題以及我的題解，大家可以去練習一下，相信你寫過一遍就會明白其中原理了．．．
