LRU：least recently used，最近最少使用算法。它的使用場景是：在有限的空間中存儲對象時，當空間滿時，會按一定的原則刪除原有的對象，常用的原則（算法）有LRU，F(xiàn)IFO，LFU等。在計算機的Cache硬件，以及主存到虛擬內(nèi)存的頁面置換，還有Redis緩存系統(tǒng)中都用到了該算法。我在一次面試和一個筆試時，也遇到過這個問題。

LRU的算法是比較簡單的，當對key進行訪問時（一般有查詢，更新，增加，在get()和set()兩個方法中實現(xiàn)即可）時，將該key放到隊列的最前端（或最后端）就行了，這樣就實現(xiàn)了對key按其最后一次訪問的時間降序（或升序）排列，當向空間中增加新對象時，如果空間滿了，刪除隊尾（或隊首）的對象。

在Python中，可以使用collections.OrderedDict很方便的實現(xiàn)LRU算法，當然，如果你想不到用OrderedDict，那可以用dict+list來實現(xiàn)。本文主要參考了LRU CACHE IN PYTHON，寫的非常好，既實現(xiàn)了功能，又簡潔易讀。方法一的代碼與參考文章基本相同，方法二是我自己想出來的，比較繁瑣一些，其實OrderedDict本身也是類似的這種機制來實現(xiàn)的有序。

不過，下面的實現(xiàn)是有問題的，這個cache的key:value鍵值對中，value只能是不可變類型。因為，如果value是可變類型，那對于同一個key，所有調(diào)用get(key)方法返回的value都是指向同一個可變對象的，當修改其中一個value時，那所有的value都會被修改了，即使你沒有調(diào)用set()方法也會這樣。這是我們不希望看到的。解決方法我想到了兩種，一是可變對象序列化后再存儲，即將可變對象轉(zhuǎn)為不可變對象；二是仍存儲可變對象，但get()時，返回一個深拷貝，這樣每個get()調(diào)用返回的對象就不會相互影響了。推薦第一種方法。另外，對于key，推薦使用str/unicode類型。

當并發(fā)時，還會存在一個問題，因為這涉及到對公共資源的寫操作，所以必須要對set()加鎖。其實，在并發(fā)情況下，所有對公共資源的寫操作都要加鎖。如果不存在并發(fā)的情況，只有單線程，那可以不加鎖。

方法一：用OrderedDict實現(xiàn)（推薦）
代碼如下:
from collections import OrderedDict
 
 
class LRUCache(OrderedDict):
    '''不能存儲可變類型對象，不能并發(fā)訪問set()'''

    def __init__(self,capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    

    def get(self,key):
        if self.cache.has_key(key):
            value = self.cache.pop(key)
            self.cache[key] = value