在知乎上看到一篇文章 ：

他采用HashMap+双向链表实现LRU(淘汰掉最不经常使用的)。先来将原文简单引用介绍下，以免原作者删除。

很久前参加过今日头条的面试，遇到一个题，目前半部分是如何实现 LRU，后半部分是 Redis 中如何实现 LRU。

我的第一反应是操作系统课程里学过，应该是内存不够的场景下，淘汰旧内容的策略。LRU ... Least Recent Used，淘汰掉最不经常使用的。可以稍微多补充两句，因为计算机体系结构中，最大的最可靠的存储是硬盘，它容量很大，并且内容可以固化，但是访问速度很慢，所以需要把使用的内容载入内存中；内存速度很快，但是容量有限，并且断电后内容会丢失，并且为了进一步提升性能，还有CPU内部的 L1 Cache，L2 Cache等概念。因为速度越快的地方，它的单位成本越高，容量越小，新的内容不断被载入，旧的内容肯定要被淘汰，所以就有这样的使用背景。

LRU原理

在一般标准的操作系统教材里，会用下面的方式来演示 LRU 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。

但是如果让我们自己设计一个基于 LRU 的缓存，这样设计可能问题很多，这段内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。

那么如何设计一个LRU缓存，使得放入和移除都是 O(1) 的？

我们需要把访问次序维护起来，但是不能通过内存中的真实排序来反应，有一种方案就是使用HashMap+双向链表。

 

基于 HashMap 和 双向链表实现 LRU 的

整体的设计思路是，可以使用 HashMap<key,value>  key存储双向链表的数值，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。（key指向Node节点，value指向数值也可以）

LRU中数据的存储和对使用时间新旧的维护是由 双向链表 实现的。（

1. 在链表头的是最新使用的。
2. 在尾部的是最旧的。也是下次要清除的。
3. 如果加入的值是链表内存在的则要移动到头部。）

HashMap是来配合双向链表，用于减少时间复杂度的。它是可以快速的（O(1)的时间）定位，链表中某个值是否存在。（要不然需要遍历双向链表，时间复杂度为O(n) n为链表长度），定位到某个值存在后能马上获得他的node节点，因为是双向链表，直接用此节点的父节点，指向此节点的子节点。在将此节点放到头部就可以了。免除了遍历查找。

完整基于 Java 的代码参考如下

 

class DLinkedNode {	String key;	int value;	DLinkedNode pre;	DLinkedNode post;}

LRU Cache 

public class LRUCache {       private Hashtable
     
                  cache = new Hashtable
      
       ();    private int count;    private int capacity;    private DLinkedNode head, tail;    public LRUCache(int capacity) {        this.count = 0;        this.capacity = capacity;        head = new DLinkedNode();        head.pre = null;        tail = new DLinkedNode();        tail.post = null;        head.post = tail;        tail.pre = head;    }    public int get(String key) {        DLinkedNode node = cache.get(key);        if(node == null){            return -1; // should raise exception here.        }        // move the accessed node to the head;        this.moveToHead(node);        return node.value;    }    public void set(String key, int value) {        DLinkedNode node = cache.get(key);        if(node == null){            DLinkedNode newNode = new DLinkedNode();            newNode.key = key;            newNode.value = value;            this.cache.put(key, newNode);            this.addNode(newNode);            ++count;            if(count > capacity){                // pop the tail                DLinkedNode tail = this.popTail();                this.cache.remove(tail.key);                --count;            }        }else{            // update the value.            node.value = value;            this.moveToHead(node);        }    }    /**     * Always add the new node right after head;     */    private void addNode(DLinkedNode node){        node.pre = head;        node.post = head.post;        head.post.pre = node;        head.post = node;    }    /**     * Remove an existing node from the linked list.     */    private void removeNode(DLinkedNode node){        DLinkedNode pre = node.pre;        DLinkedNode post = node.post;        pre.post = post;        post.pre = pre;    }    /**     * Move certain node in between to the head.     */    private void moveToHead(DLinkedNode node){        this.removeNode(node);        this.addNode(node);    }    // pop the current tail.    private DLinkedNode popTail(){        DLinkedNode res = tail.pre;        this.removeNode(res);        return res;    }}
      
     

 

其实在上面我已经对原文做了补充了，解释了HashMap 和双向链表在此各自扮演的角色。下面在详细说下为什么用这连个数据结构的组合。这也是我在这篇文章后面的评论

1)首先我想的是用队列不行吗？

不行队列只能做到先进先出，但是重复用到中间的数据时无法把中间的数据移动到顶端。

2)就用单链表不行吗？ 单链表能实现新来的放头部，最久不用的在尾部删除。但删除的时候需要遍历到尾部，因为单链表只有头指针。在用到已经用到过的数据时，还要遍历整合链表，来确定是否用过，然后再遍历到响应位置来剔除的节点，并重新放在头部。这效率可想而知。 这时hashmap的作用就出来了 他可以在单位1的时间判断value的值是否存在，key直接存储节点对象，能直接定位删除对应的节点(将比节点的父节点指向此节点的子节点)。

要通过一个节点直接获得父节点的话，通过单链表是不行的。

这时双向链表的作用也提现出来了。能直接定位到父节点。 这效率就很高了。而且由于双向链表有尾指针，所以剔除最后的尾节点也十分方便，快捷。

 

 

然后在补充原文作者在文章中所说的Redis的LRU实现

Redis的LRU实现

如果按照HashMap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以Redis采用了一个近似的做法，就是随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的，具体分析如下：

为了支持LRU，Redis 2.8.19中使用了一个全局的LRU时钟，server.lruclock，定义如下，

#define REDIS_LRU_BITS 24unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */

默认的LRU时钟的分辨率是1秒，可以通过改变REDIS_LRU_CLOCK_RESOLUTION宏的值来改变，Redis会在serverCron()中调用updateLRUClock定期的更新LRU时钟，更新的频率和hz参数有关，默认为100ms一次，如下，

#define REDIS_LRU_CLOCK_MAX ((1<
     
      lru */#define REDIS_LRU_CLOCK_RESOLUTION 1 /* LRU clock resolution in seconds */void updateLRUClock(void) {    server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &                                                REDIS_LRU_CLOCK_MAX;}
     

server.unixtime是系统当前的unix时间戳，当 lruclock 的值超出REDIS_LRU_CLOCK_MAX时，会从头开始计算，所以在计算一个key的最长没有访问时间时，可能key本身保存的lru访问时间会比当前的lrulock还要大，这个时候需要计算额外时间，如下，

/* Given an object returns the min number of seconds the object was never * requested, using an approximated LRU algorithm. */unsigned long estimateObjectIdleTime(robj *o) {    if (server.lruclock >= o->lru) {        return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;    } else {        return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) *                    REDIS_LRU_CLOCK_RESOLUTION;    }}

Redis支持和LRU相关淘汰策略包括，

• volatile-lru 设置了过期时间的key参与近似的lru淘汰策略
• allkeys-lru 所有的key均参与近似的lru淘汰策略

当进行LRU淘汰时，Redis按如下方式进行的，

......            /* volatile-lru and allkeys-lru policy */            else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||                server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)            {                for (k = 0; k < server.maxmemory_samples; k++) {                    sds thiskey;                    long thisval;                    robj *o;                    de = dictGetRandomKey(dict);                    thiskey = dictGetKey(de);                    /* When policy is volatile-lru we need an additional lookup                     * to locate the real key, as dict is set to db->expires. */                    if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)                        de = dictFind(db->dict, thiskey);                    o = dictGetVal(de);                    thisval = estimateObjectIdleTime(o);                    /* Higher idle time is better candidate for deletion */                    if (bestkey == NULL || thisval > bestval) {                        bestkey = thiskey;                        bestval = thisval;                    }                }            }            ......

Redis会基于server.maxmemory_samples配置选取固定数目的key，然后比较它们的lru访问时间，然后淘汰最近最久没有访问的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于严格LRU算法，但是相应消耗也变高，对性能有一定影响，样本值默认为5。

 

感谢知乎原文（ ）作者文西

LRU 的Java实现，光看代码的话还可以参考这篇文章：