文档章节

LRU(Least Recent Used) java 实现为这么采用HashMap+双向链表

为了美好的明天
 为了美好的明天
发布于 2018/03/14 10:31
字数 2108
阅读 917
收藏 5

在知乎上看到一篇文章 : LRU原理和Redis实现——一个今日头条的面试题

他采用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<Integer, DLinkedNode>
            cache = new Hashtable<Integer, DLinkedNode>();
    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 24
unsigned 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<<REDIS_LRU_BITS)-1) /* Max value of obj->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原理和Redis实现——一个今日头条的面试题)作者文西

LRU 的Java实现,光看代码的话还可以参考这篇文章: java LRU算法介绍与用法示例

© 著作权归作者所有

为了美好的明天

为了美好的明天

粉丝 37
博文 655
码字总数 185391
作品 0
通州
程序员
私信 提问
一个今日头条的面试题——LRU原理和Redis实现

很久前参加过今日头条的面试,遇到一个题,目前半部分是如何实现 LRU,后半部分是 Redis 中如何实现 LRU。 我的第一反应应该是内存不够的场景下,淘汰旧内容的策略。LRU ... Least Recent Us...

Java架构
2018/08/30
0
0
聊聊LinkedHashMap

LinkedHashMap简介 LinkedHashMap是一个根据某种规则有序的hashmap。根据名字,我们也可以看出这个集合是有hash散列的功能的同时也有顺序。hashmap是无法根据某种顺序来访问数据的,例如放入...

xpbob
2018/11/12
495
0
搞懂 Java LinkedHashMap 源码

LinkedHashMap 源码分析 上周学习了 的源码感觉收获颇多,虽然红黑树这个坑自己还没有填,但是我没脸没皮的先看了 的源码。因为的确跟有很大关系,看完这篇文章相信大家也会有这种感觉。由于...

群星纪元
03/31
3
0
使用 LinkedHashMap 实现 LRU 算法

LinkedHashMap 源码分析 上面是 LinkedHashMap 的继承结构。然后看下构造方法: 构造方法比较简单,主要是多个两个成员变量,并且构造方法当中多了 accessOrder。 下面看下 put 方法,Linke...

王爵nice
2015/07/30
359
0
LinkedHashMap原理分析

本文主要内容 LinkedHashMap使用 LinkedHashMap源码解析 Lru算法 今天打算看看android的图片缓存相关知识点,没想到引申到了LinkedHashMap容器了。 LinkedHashMap继承HashMap,相比于HashMap...

某昆
2018/06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部