JAVA的LRU缓存介绍与实现

的缓存介绍与实现JAVA LRU引子我们平时总会有一个电话本记录所有朋友的电话，但是，如果有朋友经常联系，那些朋友的电话号码不用翻电话本我们也能记住，但是，如果长时间没有联系了，要再次联系那位朋友的时候，我们又不得不求助电话本，但是，通过电话本查找还是很费时间的但是，我们大脑能够记住的东西是一定的，我们只能记住自己最熟悉的,而长时间不熟悉的自然就忘记了其实，计算机也用到了同样的一个概念，我们用缓存来存放以前读取的数据，而不是直接丢掉，这样，再次读取的时候，可以直接在缓存里面取，而不用再重新查找一遍，这样系统的反应能力会有很大提高但是，当我们读取的个数特别大的时候，我们不可能把所有已经读取的数据都放在缓存里，毕竟内存大小是一定的，我们一般把最近常读取的放在缓存里（相当于我们把最近联系的朋友的姓名和电话放在大脑里一样）现在，我们就来研究这样一种缓存机制LRU缓存LRU缓存利用了这样的一种思想LRU Least Recently Used的缩写，翻译过来就是“最近最少使用”，也就是说，LRU缓存把最近最少使用的数据移除，让给最新读取的数据而往往最常读取的，也是读取次数最多的，所以，利用LRU缓存，我们能够提高系统的performance.实现要实现LRU缓存，我们首先要用到一个类LinkedHashMapo用这个类有两大好处一是它本身已经实现了按照访问顺序的存储，也就是说，最近读取的会放在最前面，最最不常读取的会放在最后（当然，它也可以实现按照插入顺序存储）第二，LinkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数，但是，原始方法默认不需要移除（这是，LinkedHashMap相当于一个linkedlist）,所以,我们需要override这样一个方法，使得当缓存里存放的数据个数超过规定个数后，就把最不常用的移除掉LinkedHashMap的API写得很清楚，推荐大家可以先读一下要基于LinkedHashMap来实现LRU缓存，我们可以选择inheritance,也可以选择delegation,我更喜欢delegation基于delegation的实现己经有人写出来了，而且写得很漂亮，我就不班门弄斧了代码如下import java.util.LinkedHashMap;import java.util.Collection;import java.util.Map;import java.util.ArrayList;/**采用inheritance方式实现比较简单，而且实现了Map接口，在多线程环境使用时可以使用Collections.synchronizedMap方法实现线程安全操作package cn.lzrabbit.structure.lru;import java.util.LinkedHashMap;import java.util.Map;/***Created byliuzhao on14-5-

15.*/public classLRUCache2K,V extendsLinkedHashMapK,V{private final int MAX_CACHE_SIZE;public LRUCache2int cacheSize{superint Math.ceilcacheSize/

0.75+1,

0.75f,true;MAX CACHESIZE=cacheSize;}@Overrideprotected boolean removeEldestEntryMap.Entry eldest{return sizeMAX_CACHE_SIZE;@Overridepublic StringtoStringO{StringBuilder sb=new StringBuilder;for Map.EntryK,V entry:entrySet{sb.appendString.formatn%s:%s entry.getKeyO,entry.getValue;return sb.toStringO;这样算是比较标准的实现吧，实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦final int cacheSize=100;MapString,String map=new LinkedHashMapString,StringintMath.ceilcacheSize/

0.75f+1,

0.75f,true{@Overrideprotected booleanremoveEldestEntryMap.EntryString,String eldest{returnsizecacheSize;；缓存实现LRU LinkedHashMapdelegationdelegation方式实现更加优雅一些，但是由于没有实现Map接口，所以线程同步就需要自己搞定了▲▲package cn.lzrabbit.structure.lru;import java.util.LinkedHashMap;import java.util.Map;import java.util.Set;/***Created byliuzhao on14-5-

13.*/public classLRUCache3K,V{private finalint MAX_CACHE_SIZE;private final float DEFAULT_LOAD_FACTOR=

0.75f;LinkedHashMapK,V map;public LRUCache3int cacheSize{MAX CACHESIZE=cacheSize;//根据cacheSize和加载因子计算hashmap的capactiy,+1确保当达到cacheSize上限时不会触发hashmap的扩容，int capacity=int Math.ceilMAX_CACHE_SIZE/DEFAULT_LOAD_FACTOR+1;m叩二new LinkedHashMapcapacity,DEFAULT_LOAD_FACTOR,true@Overrideprotected booleanremoveEldestEntryMap.Entry eldest{return sizeMAX_CACHE_SIZE;；public synchronizedvoid putK key,V value{map.putkey,value;}public synchronizedV getK key{return map.getkey;}public synchronizedvoid removeK key{map.removekey;public synchronizedSetMap.EntryK,V»getAll{return map.entrySet;}public synchronizedint size{return map.size;public synchronizedvoid clear{map.clear;@Overridepublic StringtoStringO{StringBuilder sb=new StringBuilder;for Map.Entry entry:map.entrySet{sb.appendString.formatH%s:%s,entry.getKeyO,entry.getValue;}return sb.toStringO;•■的链表实现LRU Cache+HashMap注此实现为非线程安全，若在多线程环境下使用需要在相关方法上添加synchronized以实现线程安全操作*当package cn.lzrabbit.structure.lru;import java.util.HashMap;/***Created byliuzhao on14-5-

12.*/public classLRUCachelK,V{private finalint MAX_CACHE_SIZE;private Entryfirst;private Entrylast;private HashMapK,EntryK,V»hashMap;public LRUCachelintcacheSize{MAX CACHESIZE=cacheSize;hashMap=new HashMapK,EntryK,V»;public void putK key,V value{Entry entry=getEntrykey;if entry==null{ifhashMap.size=MAX_CACHE_SIZE{hashMap.removelast.key;removeLast;entry=new Entry;entry.key=key;entry.value=value;moveToFirstentry;hashMap.putkey,entry;public V getK key{Entry vK,V entry=getEntrykey;if entry==null return null;moveToFirstentry;return entry.value;public voidremoveKkey{Entry entry=getEntrykey;if entry!=null{if entry.pre!=null entry.pre.next二entry.next;if entry.next!=null entry.next.pre=entry.pre;if entry==first first=entry.next;if entry==last last=entry.pre;hashMap.removekey;private voidmoveToFirstEntry entry{if entry==first return;if entry.pre!=null entry.pre.next=entry.next;if entry.next!=null entry.next.pre=entry.pre;if entry==last last=last.pre;if first==null||last==null{first=last=entry;return;entry.next=first;first.pre=entry;first=entry;entry.pre=null;private voidremoveLast{if last!=null{last=last.pre;if last==null first=null;else last.next=null;private EntryK,V getEntryKkey{return hashMap.getkey;@Overridepublic StringtoStringO{StringBuilder sb=new StringBuilder;Entry entry=first;while entry!=null{sb.appendString.formatH%s:%s,entry.key,entry.value;entry=entry.next;return sb.toStringO;class EntryvK,V{public Entrypre;public Entry next;public Kkey;public V value;的实现LinkedHashMap FIFOFIFO是First InputFirst Output的缩写，也就是常说的先入先出，默认情况下LinkedHashMap就是按照添加顺序保存，我们只需重写下removeEldestEntry方法即可轻松实现一个FIFO缓存，简化版的实现代码如下finalintcacheSize=5;LinkedHashMapInteger,String Iru=new LinkedHashMapInteger,String{@Overrideprotected booleanremoveEldestEntryMap.EntryInteger,String eldest{returnsizecacheSize;；调用示例测试代码View Code运行结果View Code短址原理及其实现short URL前言最近看了一些关于短址short URL方面的一些博客，有些博客说到一些好的东西，但是，也不是很全，所以，这篇博客算是对其它博客的一个总结吧介绍短址，顾名思义，就是把长的URL转成短的URL,现在提供这种服务的有很多公司，我们以google家的URL shortener服务http://goo.gl/为例首先我们到http://goo.gl/,然后把本文博客的地址输入进去，最后它会返回一个更短的URL,http://goo.gl/Jfs6q如下图所示Google urlshortenerhttShorten URLPasteyour longURL here:All goo.gl URLsand clickanalytics arepublic andcan beaccessed byanyone.0minute ago-解析URL当我们在浏览器里输入http://goo.gl/Jfs6q时，DNS首先解析获得http://goo.gl/的IP地址当DNS获得IP地址以后比如

74.

125.

225.72,会向这个地址发送HTTP GET请求，查询Jfs6q,这个时候，http://goo.gl/服务器会把请求通过HTTP301转到对应的长URL后面的解析过程就和平常网址解析是一样的了短址本质短址本质上是实现了一个映射函数f:X-Yo而这个映射函数必须同时具有两个特点

1.如果x1!=x2,则f x1!=fx2;

2.对于每一个y,能够找到唯一的一个x使得fx=y;对于任何的线性函数，比如fx=2x,都满足这样的条件好了，如果了解了短址的本质，我们再来看它是如何实现的注明在google URLshortener服务中，它允许一个长url对应多个短的url这可能是出于安全上的考虑在本文中，我们不考虑这种情况实现短址的长度一般设为6位，而每一位是由［a-乙A-Z,0-9］总共62个字母组成的，所以6位的话，总共会有62人6〜=568亿种组合，基本上够用了在google URLshortener服务中，短址长度为5,大概有9亿多种组合.假设我们用数据库来保存长地址和短地址的映射，那么，在表LongtoShortURL中，我们会有三列

1.ID,int,自动增长；

2.LURL,varchar,//长URL；

3.SURL,varchar,//短URL现在我们考虑通过如何长URL得到唯一的短URLo在讲具体算法以前，先提一个问题10进制数和16进制数之间的转换是否满足刚刚提到的映射函数f X-Y中的两个条件？答案是本文的思路也是利用进制之间的转换因为我们总共有62个字母，我们可以自创一种进制，叫做62进制其规则如下0f a1b一25-z52-061-9所以，对于每一个长地址，我们可以根据它的ID,得到一个6位的62进制数，这个6位的62进制数就是我们的短址具体实现如下public ArrayListIntegerbase62int id{ArrayListInteger value=new ArrayListInteger;while id0{int remainder=id%62;value,addremainder;id=id/62;}return value;}举例对于ID=138,通过base62138,我们得到value=[14,2]根据上面的对应规则表，我们可以得到其对应的短址为aaaabn由value得到具体的短址，可以通过sw让ch语句得到，因为代码太长，在此略过当我们想通过短址找到所对应的长地址，方法也很简单，就是把62进制数转成10进制数即可，这样我们就可以得到长地址的ID了代码如下public staticint baselOArrayListIntegerbase62{//make surethe sizeof base62is6for inti=1;i=6-base

62.size;i++{base

62.add0,0;int id=0;int size=base

62.size;for inti=0;isize;i++{int value=base

62.get i;id+=int value*Math.pow62,size-i-1;}return id;}比如，对于短址aaae9a,其62进制为[0,0,0,4,61,0],则其长地址的ID为[0,0,0,4,61,0]=0x62A5+0x62A4+0x62A3+4x62八2+61x62A1+0x62A0=1915810c有了ID,我们自然就可以得到长地址了*An LRUcache,based oncodeLinkedIIashMap/code.**p*This cachehas afixed maximumnumber ofelements codecacheSize/code.*If the cache isfull andanother entryis added,the LRUleast recentlyused entryisdropped.**p*This classis thread-safe.All methodsof thisclass aresynchronized.**p*Author:Christian d，Heureuse,Inventec InformatikAG,Zurich,Switzerlandbr*Multi-licensed:EPL/LGPL/GPL/AL/BSD.*/public classLRUCacheK,V{private static finalfloathashTableLoadFactor=

0.75f;private LinkedHashMapK,V privatemap;int/**cacheSize;*Creates anew LRUcache.*©param cacheSizethe maximumnumber ofentries thatwill bekept inthis cache.*/public LRUCacheintcacheSize{this.cacheSize=cacheSize;int hashTableCapacity=intMath,ceilcacheSize/hashTableLoadFactor+1;map=new LinkedHashMapK,VhashTableCapacity,hashTableLoadFactor,true{//an anonymousinner classprivatestaticfinallong serialVersionUID=1;©Override protected booleanremoveEldestEntryMap.EntryK,V eldest{return sizeLRUCache.this.cacheSize;}};}/***Retrieves anentry from the cache.br*The retrievedentry becomesthe MRUmost recentlyused entry.*@param keythe keywhose associatedvalue isto bereturned.*©return thevalue associatedto this key,or nullif novalue withthiskeyexistsin thecache.*/public synchronizedVgetKkey{return map.getkey;}/***Adds anentry tothis cache.*The new entry becomesthe MRUmost recentlyused entry.*If anentry withthe specifiedkey alreadyexists in thecache,it isreplaced bythenewentry.*If thecache isfull,the LRUleast recentlyused entryis removedfromthecache.*@param keythe keywith whichthe specifiedvalue isto beassociated.*@param valuea valueto beassociated withthe specifiedkey.*/public synchronizedvoidputKkey,Vvalue{map.put key,value;}/***Clears thecache.*/public synchronizedvoid clear{map.clear;}/***Returns thenumber ofused entriesin thecache.*©return thenumber ofentries currentlyinthecache.public synchronizedint usedEntries{return map.size;}/***Returns acodeCollection/code thatcontains a copy ofall cacheentries.*©return acodeCollection/code withacopyof thecache content.*/public synchronizedCollectionMap.EntryK,V getAll{return newArrayListMap.EntryK,Vmap.entrySet;}}//end classLRUCache//Test routinefor theLRUCache class.public staticvoid mainString]]args{LRUCacheString,String c=new LRUCacheString,String3;c.put〃1〃one〃；//1〃，c.put2,two;//21c.put〃3“three;//321〃，c.put4,four;//432if c.get〃2〃==null throw new Error;//243c.put5,five;//524c.put〃4“second four;//452〃，//Verify cachecontent.if c.usedEntries!=3throw newError;if!c・get〃4〃・equalssecond fourthrow newError;if!c・get〃5〃,equals〃five〃throw newError;if!c・get〃2〃・equals〃two〃thrownewError;//List cachecontent.for Map.EntryString,String e:c.getAll System.out.printin e.getKey+〃〃+e.getValue;}代码出自在博客里，作者使用的是双链表+hashtable的方式实现的如果在面试题里考到如何实现LRU,考官一般会要求使用双链表+hashtable的方式所以，我把原文的部分内容摘抄如下双链表+hashtable实现原理将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可public classLRUCache{private intcacheSize;private HashtableObject,Entry nodes;〃缓存容器intprivate currentSize;private Entryfirst;〃链表头private Entrylast;〃链表尾public LRUCacheinti{currentSize=0;cacheSize=1;HashtableObject,Entry i;〃缓存容器nodes=new/***获取缓存中对象,并把它放在最前面*/public Entryget Object key{Entry node=nodes.get key;ifnode!=null{moveToHead node;return node;}else{returnnull;/***添加entry到hashtable,并把entry*/public voidput Objectkey,Object value{〃先查看hashtable是否存在该entry,如果存在，则只更新其valueEntry node=nodes,getkey;if node==null{〃缓存容器是否已经超过大小.if currentSize=cacheSize{nodes.removelast,key;removeLast;}else{currentSize++;node=new Entry;}node,value=value;〃将最新使用的节点放到链表头，表示最新使用的.moveToHead node;nodes,put key,node;/***将0玳可删除，注意删除操作只有在cache满了才会被执行*/public voidremove Objectkey{Entry node=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 lastnode二二last=node,prev;if firstnode二二first=node.next;〃在hashtable中删除nodes,remove key;}/***删除链表尾部节点，即使用最后使用的entry*/private voidremoveLast{〃链表尾不为空，则将链表尾指向null.删除连表尾删除最少使用的缓存对象if last!=null{if last,prev!=nulllast.prev.next=null;elsefirst=null;last=last,prev;/***移动到链表头，表示这个节点是最新使用过的private voidmoveToHead Entrynode{if node==first return;if node.prev!=null node.prev.next node.next;二if node.next!=nullnode.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;}/**清空缓存*/public voidclear{first=null;last=null;currentSize=0;}class Entry{Entry prev;〃前一节点Entrynext;〃后一节点Object value;〃值Objectkey;〃键的缓存实现JAVA LRU

1、LRU Cache的LinkedHashMap实现

2、LRU Cache的链表+HashMap实现

3、LinkedHashMap的FIFO实现

4、调用示例LRULeastRecentlyUsed的缩写，翻译过来就是最近最少使用〃，LRU缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉，比如我们缓存10000条数据，当数据小于10000时可以随意添加，当超过10000时就需要把新的数据添加进来，同时要把过期数据删除，以确保我们最大缓存10000条，那怎么确定删除哪条过期数据呢，采用LRU算法实现的话就是将最老的数据删掉，废话不多说，下面来说下Java版的LRU缓存实现Java里面实现LRU缓存通常有两种选择，一种是使用LinkedHashMap,一种是自己设计数据结构，使用链表+HashMap的实现LRU CacheLinkedHashMapLinkedHashMap自身已经实现了顺序存储，默认情况下是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面,然后它还有一个判断是否删除最老数据的方法，默认是返回false,即不删除数据，我们使用LinkedHashMap实现LRU缓存的方法就是对LinkedHashMap实现简单的扩展，扩展方式有两种，一种是inheritance,一种是delegation,具体使用什么方式看个人喜好Ait//LinkedHashMap的一个构造函数，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面public LinkedHashMapintinitialcapacity,float loadFactor,boolean accessOrder{superinitialCapacity,loadFactor;this.accessOrder=accessOrder;//LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false,即不删除老数据〃我们要做的就是重写这个方法，当满足一定条件时删除老数据protectedbooleanremoveEldestEntryMap.EntryK,V eldest{return false;缓存LRU LinkedHashMapinheritance^M。