原文来自：2019阿里巴巴面试题+答案 这篇文章里的第三道面试题。但是原文并没有讲解解题思路，以及提供的算法解答也存在一些问题。所以我重新撰文深度讲解一遍。

内容目录

题目描述：LRU解释解题思路代码演示

题目描述：

1设计和实现一个LRU(最少最近使用)缓存数据结构，使他应该支持一下操作：get和put。2get(key)-如果key存在于缓存中，则获取key的value(总是正数)，否则返回 -1。3put(key, vale)-如果key不存在，请设置或插入value。4当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目作废。

出题人：文景，阿里巴巴出题专家，阿里云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了重复数据怎么办？

就像我上次说的，考虑到多种边际情况并询问面试官，是会加分的。

话说完了，那么开始写代码。

代码演示

 1class LRUCache(): 2    def __init__(self, capactiy): # 需要的输入其实只有容量，也就是这个capacity。 3        self.cache = {} # 这就是我们的初始缓存。 4        self.keys = [] # 这就是我们的初始列表。 5        self.capactiy = capactiy 6 7    def visit_key(self, key): # 这个是更新高频数据的位置，我这里是挪到尾部。 8                self.keys.remove(key) 9                self.keys.append(key)1011    def elim_key(self): # 这个是删除最低使用数据。12        key = self.keys[0] # 去掉头部这个最低使用数据。13        self.keys = self.keys[1:] # 然后挪动位置，重新复制一遍剩余数据。14        del self.cache[key] # 同时记得删除缓字典里的数据。1516    def get(self, key):17        if not key in self.keys:18            return -119        else:20            self.visit_key(key)21            return self.cache[key]2223    def put(self, key, value):24        if not key in self.keys:25            if len(self.keys) >= self.capactiy:26                self.elim_key()27                self.cache[key] = value28                self.keys.append(key)29            else:30                self.cache[key] = value31                self.keys.append(key)32        else:33            self.visit_key(key) # 这里如果put进的数据之前出现过，那么也调整一次顺序。这次操作是我自己补充的。34        print("现有列表", self.keys)35        print("现有缓存", self.cache)36        print("------------------")3738def main():39    s = [["put", "put", "get", "put", "get", "put", "get", "get", "get"],\40    [[1,11], [2,12], [1], [3,13], [2], [4,14], [1], [3], [5]]]41    obj = LRUCache(3)42    l = []43    for i,c in enumerate(s[0]):44        if(c == "get"):45            print("get", s[1][i][0])46            l.append(obj.get(s[1][i][0]))47            print("return:", l[-1])48            print("--------------")49        else:50            print("put: key", s[1][i][0], "value", s[1][i][1])51            obj.put(s[1][i][0], s[1][i][1])52    print(l)5354if __name__ == '__main__':55    main()

上述代码里的 main 函数其实就才测试路径。

欢迎大家自己跑一遍。然后能自己亲手写出来，就更好了。

最后，LRU思想可以知道生活的很多方面。下次再遇到类似“舍断离”的场景，就可以试着用这个思路解决。

--- EOF ---

EOF是一个计算机术语，为End Of File的缩写，在操作系统中表示资料源无更多的资料可读取。通常在文本的最后存在此字符表示资料结束。

本人公众号[火山灰]，[time_ash_past]