原文來自：2019 阿里巴巴面試題 + 答案 這篇文章裡的第三道面試題。但是原文並沒有講解解題思路，以及提供的算法解答也存在一些問題。所以我重新撰文深度講解一遍。
內容目錄
題目描述
LRU 解釋
解題思路
代碼演示
題目描述
<code>1設計和實現一個LRU(最少最近使用)緩存數據結構，使它應該支持以下操作：get和put。2get(key)-如果key存在於緩存中，則獲取key的value(總是正數)，否則返回-1。3put(key,vale)-如果key不存在，請設置或插入value。4當緩存達到其容量時，它應該在插入新項目之前使最近最少使用的項目作廢。/<code>
出題人：文景，阿里巴巴出題專家，阿里雲 CDN 資深技術專家。
LRU 解釋
首先有一本書推薦大家讀，《算法之美》，作者是布萊恩・克里斯汀和她的小夥伴湯姆・格里菲思，中信出版集團出版。
這本書的副標題是《指導工作與生活的算法》。
非常推薦大家讀。網上也有電子版。
本書我如果有時間和條件也會去寫一篇讀後感。
豆瓣上對這本書褒貶不一，貶低的原因主要是說太囉嗦了，而且看著實際但是並不實用。我同意說書寫得囉嗦，不過不同意寫的不實用。
這本書大概 1/2 的部分就提到了 LRU 原理，並且說這個原理在生活中有很多可以用到的地方，最典型的就是如何擺放我們的書櫃，哪些書適合放在書桌和書架容易拿到的地方。
傳統的擺放方法都是根據書名字母表、或者書的種類這裡方法進行規整地擺放。
實際上最好的擺放方法是按照 LRU 原理，最經常使用到的書放在最容易接觸到的地方，一年甚至幾年都用不到的書應該放在書庫裡。
而這個數據結構題也是類似。最經常被訪問的 key 放在緩存裡方便調取訪問。
這是一個非常有價值和意義的理論。
我們接下來看如何解決這個題。
解題思路
這個數據結構緩存包含的內容一開始肯定為空。同時對這個數據結構緩存的空間需要人為設置一個空間量，比如只容納 5 個數據空間。
接下來繼續想，題目既然要求這個緩存用來存放 key-value 值，那麼毫無疑問就是用哈希表（如果是 Python，那就是 Python 裡的字典）來儲存。數據結構的基礎敲定了。
題目中還提到要限制緩存的容量，方法有兩個，一個是直接限制哈希表 key 的容量，另一個是新開闢空間，把 key 值用數組（Python 裡就是用列表）來存儲，通過限制數組的大小（或者說列表的大小）來限制緩存（也就是哈希表或者字典）裡存的數據的量。
但是還要考慮到要求裡說：
當緩存達到其容量時，它應該在插入新項目之前使最近最少使用的項目作廢。
因為哈希表或者 Python 裡的字典，是沒有順序的，所以要解決這個需求，要麼把哈希錶轉為有序，要麼就用列表儲存 key 值。
簡單的辦法還是選擇後者。這樣新建一個列表用來儲存 key 值並更新位置和限制容量。
一開始，我們往緩存裡面添加 key 和 value，也就是 put 內容。比如 put (1, 11)。那麼數據結構緩存裡就有了 {1：11}，對應的列表則為 [1]。繼續添加比如 put (2, 12), put (3,13)。這時候數據結構緩存裡有 {1：11，2：12，3：13}，對應的列表則有 [1,2,3]。如果 get (3)，判斷 3 在列表 [1,2,3] 裡，然後去緩存裡尋找 value 值，返回 13 (因為 3 對應的 value 是 13)。同時，需要知道，3 被訪問了一次，所以 3 需要被提到前面去。這個時候空間還沒滿，所以繼續添加 key 和 value 就可以繼續增加緩存和列表。而這時候如果 get (10)，那麼就會返回 -1。因為 10 不在緩存裡。
好，如果繼續 put (4, 14)， put (5, 15)，此時列表裡有 [3,1,2,4,5]（因為 3 被 get 過一次，所以需要排前），對應的緩存 {1：11，2：12，3：13，4：14，5：15}（因為字典沒有順序，所以就這樣寫了）。然後如果這時候再 put (6, 16)，空間不足，那麼就需要在列表裡刪除一個 key，然後在緩存 / 字典裡更換 key 和 value（這句話說的簡單，實際上還是涉及到兩個操作，一步是刪除掉舊的 key，第二步是更新新的 key 和 value）。刪除哪個呢？就刪除最靠後的那個。因為它最不會用到。
當然，這裡其實把最經常被訪問到的放在末尾，刪除的時候刪除頭部的也可以。這個只需要自己定義好即可。
基本流程就解釋完畢了。
當然這種有一個極端情況就是，一個人反覆 put (5, 15) 和 put (6, 16)，導致這兩個數反覆被替換操作。但是這種情況一般比較腦殘，不考慮。因為既然反覆 put，肯定會進行 get，不然幹嘛反覆 put。
如果被 get 操作執行的越多，就越靠前。所以有一個優化就是在 get 的時候判斷一下這個 key 是否在列表的第一個，如果是，就不用進行挪位置操作了。當然這個優化對整體的改善效果值得商榷。
上面的操作，雖然只涉及了 get 和 put，但是我們看到，其實需要其他的操作。第一個就是如果有 get，那麼就需要更新位置，這是第一個需要新增的操作，然後就是如果空間滿了再有 put，那麼要刪除舊數據騰出新位置，這是第二個操作。
所以需要新增第一個操作，就是更新位置的操作。這個操作是當出現 get 的時候，就要調換這個 key 在列表裡的位置，需要把它挪到列表的頭部，或者尾部。挪到頭部或者尾部都可以，我這裡採用的是挪到尾部。
第二個操作是刪除數據。如果第一個操作是把高頻詞挪到頭部，那麼刪除的數據就是列表的尾部，而如果第一個操作是把高頻詞挪到尾部，那麼刪除的數據就是列表的頭部。而刪除的辦法其實就是去掉刪除位置的數據之外重新複製一遍原列表。
這裡還可以問一下面試官，如果 put 了重複數據怎麼辦？
就像我上次說的，考慮到多種邊際情況並詢問面試官，是會加分的。
話說完了，那麼開始寫代碼。
代碼演示
<code> 1classLRUCache(): 2def__init__(self,capactiy):#需要的輸入其實只有容量，也就是這個capacity。 3self.cache={}#這就是我們的初始緩存。 4self.keys=[]#這就是我們的初始列表。 5self.capactiy=capactiy 6 7defvisit_key(self,key):#這個是更新高頻數據的位置，我這裡是挪到尾部。 8self.keys.remove(key) 9self.keys.append(key)1011defelim_key(self):#這個是刪除最低使用數據。12key=self.keys[0]#去掉頭部這個最低使用數據。13self.keys=self.keys[1:]#然後挪動位置，重新複製一遍剩餘數據。14delself.cache[key]#同時記得刪除緩字典裡的數據。1516defget(self,key):17ifnotkeyinself.keys:18return-119else:20self.visit_key(key)21returnself.cache[key]2223defput(self,key,value):24ifnotkeyinself.keys:25iflen(self.keys)>=self.capactiy:26self.elim_key()27self.cache[key]=value28self.keys.append(key)29else:30self.cache[key]=value31self.keys.append(key)32else:33self.visit_key(key)#這裡如果put進的數據之前出現過，那麼也調整一次順序。這次操作是我自己補充的。34print("現有列表",self.keys)35print("現有緩存",self.cache)36print("------------------")3738defmain():39s=[["put","put","get","put","get","put","get","get","get"],\\40[[1,11],[2,12],[1],[3,13],[2],[4,14],[1],[3],[5]]]41obj=LRUCache(3)42l=[]43fori,cinenumerate(s[0]):44if(c=="get"):45print("get",s[1][i][0])46l.append(obj.get(s[1][i][0]))47print("return:",l[-1])48print("--------------")49else:50print("put:key",s[1][i][0],"value",s[1][i][1])51obj.put(s[1][i][0],s[1][i][1])52print(l)5354if__name__=='__main__':55main()/<code>上述代碼裡的 main 函數其實就才測試路徑。
歡迎大家自己跑一遍。然後能自己親手寫出來，就更好了。
最後，LRU 思想可以知道生活的很多方面。下次再遇到類似 “舍斷離” 的場景，就可以試著用這個思路解決。
--- EOF ---
EOF 是一個計算機術語，為 End Of File 的縮寫，在操作系統中表示資料源無更多的資料可讀取。通常在文本的最後存在此字符表示資料結束。
本人公眾號 [火山灰]，[time_ash_past]
閱讀更多 火山灰的荷蘭號 的文章
