如何实现的LRU缓存淘汰策略？

LRU 缓存 题目链接 LRU，即Least-Recently-Used。是一种高速缓存替换策略，是一种缓存机制。主要是利用局部性原理。 局部性原理分两种，空间局部性和时间局部性。 在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次应用。 在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。 显然，LRU是利用到了时间局部性。 在CSAPP的P434 组相联高速缓存中不命中时的行替换 出现。 最近最少使用（LRU）策略会替换最后一次访问时间最久远的那一行。 题目分析 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。 来源：力扣（LeetCode） 这是一道很优秀的设计问题，而不是关于某个问题的算法。 题目要求你利用相关的知识，设计一个能够简单实现LRU 缓存机制的类。 根据刚刚所说的CSAPP中的背景知识，可以知道要设计出的类： 需要存储每个键值。（put函数插入，get函数查询） 键值对（key，value）需要用哈希表来存储。（O(1) 的平均时间复杂度） 那现在留下的问题就是，如何做到逐出。 队列 首先可以想到，利用队列的先进先出原则。 如果使用了，就将它拿出，再插入到队列中。 队首为最久未使用，队尾为最近使用。 那么如何逐出？拿出怎么做到？这里就遇到了难以删除的问题。 双向链表 所以，下面介绍双向链表的解法。 双向链表可以直接访问到尾部。尾部代表最久未使用。 链表方便插入和删除。 根据键值，利用哈希表能定位到对应的存储节点。 内存泄漏？ 双向链表可以利用指向关系做到删除，将节点剔除于链表外。 然而我们在剔除后，对于访问的节点来说，还需要再加到头部节点。而对于没有访问的节点，我们需要真正删除它。 所以代码中有两个delete函数，来避免内存泄漏。