缓存策略之LRU实现及分析

  1. LRU定义

Cache的容量有限,因此当Cache的容量用完后,而又有新的内容需要添加进来时, 就需要挑选并舍弃原有的部分内容,从而腾出空间来放新内容。 LRU Cache 的替换原则就是将最近最少使用的内容替换掉 Least recently used. 可以理解为, 淘汰不常用的数据

2. 数据更新测量

基于双链表的LRU算法的实现,

它的原理: 将Cache的所有位置都用双连表连接起来,

a 访问操作:

当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,

b 插入操作

1 如果cache 未满 新加入的Cache直接加到链表头中。

2 当需要替换内容时候,链表的最后位置就是最少被命中的位置,

我们只需要淘汰链表最后的部分即可。

结果:

经常被访问数据在前面

不经常被访问数据在后面

3 代码实现

我们用一个对象来表示Cache,并实现双链表,

Java代码

public class LRUCache {  
 /** 
     * 链表节点 
     * @author Administrator 
     * 
     */ 
 class CacheNode {  
        ……  
    }  
 
 private int cacheSize;//缓存大小 
 private Hashtable nodes;//缓存容器 
 private int currentSize;//当前缓存对象数量 
 private CacheNode first;//(实现双链表)链表头 
 private CacheNode last;//(实现双链表)链表尾 
}  

下面给出完整的实现,这个类也被Tomcat所使用( org.apache.tomcat.util.collections.LRUCache),但是在tomcat6.x版本中,已经被弃用,使用另外其他的缓存类来替代它。

Java代码

public class LRUCache {  
 /** 
     * 链表节点 
     * @author Administrator 
     * 
     */ 
 class CacheNode {  
        CacheNode prev;//前一节点 
        CacheNode next;//后一节点 
        Object value;//值 
        Object key;//键 
        CacheNode() {  
        }  
    }  
 
 public LRUCache(int i) {  
        currentSize = 0;  
        cacheSize = i;  
        nodes = new Hashtable(i);//缓存容器 
    }  
 
 /** 
     * 获取缓存中对象 
     * @param key 
     * @return 
     */ 
 public Object get(Object key) {  
        CacheNode node = (CacheNode) nodes.get(key);  
 if (node != null) {  
            moveToHead(node);  
 return node.value;  
        } else {  
 return null;  
        }  
    }  
 
 /** 
     * 添加缓存 
     * @param key 
     * @param value 
     */ 
 public void put(Object key, Object value) {  
        CacheNode node = (CacheNode) nodes.get(key);  
 
 if (node == null) {  
 //缓存容器是否已经超过大小. 
 if (currentSize >= cacheSize) {  
 if (last != null)//将最少使用的删除 
                    nodes.remove(last.key);  
                removeLast();  
            } else {  
                currentSize++;  
            }  
 
            node = new CacheNode();  
        }  
        node.value = value;  
        node.key = key;  
 //将最新使用的节点放到链表头,表示最新使用的. 
        moveToHead(node);  
        nodes.put(key, node);  
    }  
 
 /** 
     * 将缓存删除 
     * @param key 
     * @return 
     */ 
 public Object remove(Object key) {  
        CacheNode node = (CacheNode) nodes.get(key);  
 if (node != null) {  
 if (node.prev != null) {  
                node.prev.next = node.next;  
            }  
 if (node.next != null) {  
                node.next.prev = node.prev;  
            }  
 if (last == node)  
                last = node.prev;  
 if (first == node)  
                first = node.next;  
        }  
 return node;  
    }  
 
 public void clear() {  
        first = null;  
        last = null;  
    }  
 
 /** 
     * 删除链表尾部节点 
     *  表示 删除最少使用的缓存对象 
     */ 
 private void removeLast() {  
 //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象) 
 if (last != null) {  
 if (last.prev != null)  
                last.prev.next = null;  
 else 
                first = null;  
            last = last.prev;  
        }  
    }  
 
 /** 
     * 移动到链表头,表示这个节点是最新使用过的 
     * @param node 
     */ 
 private void moveToHead(CacheNode node) {  
 if (node == first)  
 return;  
 if (node.prev != null)  
            node.prev.next = node.next;  
 if (node.next != null)  
            node.next.prev = node.prev;  
 if (last == node)  
            last = node.prev;  
 if (first != null) {  
            node.next = first;  
            first.prev = node;  
        }  
        first = node;  
        node.prev = null;  
 if (last == null)  
            last = first;  
    }  
 private int cacheSize;  
 private Hashtable nodes;//缓存容器 
 private int currentSize;  
 private CacheNode first;//链表头 
 private CacheNode last;//链表尾 
} 

4 性能分析:

lur 算法 时间复杂度是 o(1)

为啥不是o(n)

hashtable作为索引 --快速访问

list链表 ---存储有序数据

5 扩展 (hashtable+list方式)

Q1 用redis数据结构 zset结构如何实现的 请问是用红黑树吗 ?

A:不是

1 hash--快速查找 key-value 2 链表方式 --保证数据顺序

KIPLIST 编码的有序集

当使用 REDIS_ENCODING_SKIPLIST 编码时, 有序集元素由 redis.h/zset 结构来保存:

/* * 有序集 */typedef struct zset {

    // 字典
    dict *dict;

    // 跳跃表
    zskiplist *zsl;} zset;

采用复合结构,

字典维护了name=>score的映射表,

而跳跃表则维护了按score排序的列表. 按name和按score的范围查询都天然支持.

Q2 为什么用能map 代替(hash+list方式) 两个结构表示多麻烦呀

STL的map底层是用红黑树实现的,查找时间复杂度是log(n); STL的hash_map底层是用hash表存储的,查询时间复杂度是O(1)重复记录 最坏情况o(n)

A2:

map在数量大时候缺点

一般应用情况下,我们保存的数据不超过100万份,查找的频繁程度不高情况下使用map性能比较好;

而保存的数据较多时(超过100万),查找频繁时使用hash_map的性能就高于map了

参考

1 http://redisbook.readthedocs.io/en/latest/datatype/sorted_set.html

原文发布于微信公众号 - 架构说(JiaGouS)

原文发表时间:2017-04-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

网易2013校园招聘笔试题详解

http://blog.csdn.net/silangquan/article/details/18142651

15320
来自专栏PHP在线

URL短链接实现方法

最近项目开发中,需要实现URL长链接转短链接的需求,于是在网上找了一些资料,顺便整理了下,欢迎有想法的童鞋踊跃留言,我们共同探讨。 一.短链接的好处 1.内...

1.3K140
来自专栏散尽浮华

Linux下的计算命令和求和、求平均值、求最值命令梳理

在Linux系统下,经常会有一些计算需求,那么下面就简单梳理下几个常用到的计算命令 (1)bc命令 bc命令是一种支持任意精度的交互执行的计算器语言。bash内...

45870
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(二) ——Redis中的字典(Hash)

《Redis设计与实现》读书笔记(二) ——Redis中的字典(Hash) (原创内容,转载请注明来源,谢谢) 一、概述 字典,又称符号表、关联数组、映射,是一...

406100
来自专栏Golang语言社区

GO语言标准库概览

在Go语言五周系列教程的最后一部分中,我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包,提供了丰富广泛的功能特性。这里提供了概览仅仅是...

396100
来自专栏DOTNET

.Net多线程编程—并发集合

并发集合 1 为什么使用并发集合? 原因主要有以下几点: System.Collections和System.Collections.Generic名称空间中所...

35770
来自专栏机器学习从入门到成神

队列和栈面试题(一)— 请编写一个程序,按升序对栈进行排序,要求最多只能使用一个额外的栈存放临时数据

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

14020
来自专栏Fundebug

Source Map的原理探究

经过这一系列骚气的操作后,发布到线上的代码已经面目全非,对带宽友好了,但对开发者调试并不友好。于是就有了Source Map。顾名思义,他是源码的映射,可以将压...

33250
来自专栏前端杂货铺

深入seajs源码系列三

入口方法        每个程序都有个入口方法,类似于c的main函数,seajs也不例外。系列一的demo在首页使用了seajs.use(),这便是入口方法。...

28560
来自专栏张戈的专栏

Linux运维基础技能: 脚本编程与Linux命令

本系列文章一共三篇,分别为《脚本编程与 Linux 命令》、《接入层与网络基础》和《 MySQL 与 SQL 优化》,由腾讯高级工程师 luaruan(阮永顺)...

24020

扫码关注云+社区

领取腾讯云代金券