JAVA的LRU缓存介绍与实现引子：我们平时总会有一个电话本记录所有朋友的电话，但是，如果有朋友经常联系，那些朋友的电话号码不用翻电话本我们
也能记住，但是，如果长时间没有联系了，要再次联系那位朋友的时候，我们又不得不求助电话本，但是，通过电话本查找还是很费时间的。但是，
我们大脑能够记住的东西是一定的，我们只能记住自己最熟悉的，而长时间不熟悉的自然就忘记了。其实，计算机也用到了同样的一个概念，我们用
缓存来存放以前读取的数据，而不是直接丢掉，这样，再次读取的时候，可以直接在缓存里面取，而不用再重新查找一遍，这样系统的反应能力会有
很大提高。但是，当我们读取的个数特别大的时候，我们不可能把所有已经读取的数据都放在缓存里，毕竟内存大小是一定的，我们一般把最近常读
取的放在缓存里（相当于我们把最近联系的朋友的姓名和电话放在大脑里一样）。现在，我们就来研究这样一种缓存机制。LRU缓存：LRU缓存
利用了这样的一种思想。LRU是LeastRecentlyUsed的缩写，翻译过来就是“最近最少使用”，也就是说，LRU缓存把
最近最少使用的数据移除，让给最新读取的数据。而往往最常读取的，也是读取次数最多的，所以，利用LRU缓存，我们能够提高系统的perf
ormance.实现：要实现LRU缓存，我们首先要用到一个类LinkedHashMap。用这个类有两大好处：一是它本身已经实现
了按照访问顺序的存储，也就是说，最近读取的会放在最前面，最最不常读取的会放在最后（当然，它也可以实现按照插入顺序存储）。第二，Li
nkedHashMap本身有一个方法用于判断是否需要移除最不常读取的数，但是，原始方法默认不需要移除（这是，LinkedHashM
ap相当于一个linkedlist），所以，我们需要override这样一个方法，使得当缓存里存放的数据个数超过规定个数后，就把最
不常用的移除掉。LinkedHashMap的API写得很清楚，推荐大家可以先读一下。要基于LinkedHashMap来实现LRU缓
存，我们可以选择inheritance,也可以选择delegation，我更喜欢delegation。基于delegatio
n的实现已经有人写出来了，而且写得很漂亮，我就不班门弄斧了。代码如下：importjava.util.LinkedHashMap
;importjava.util.Collection;importjava.util.Map;importjava.uti
l.ArrayList;/AnLRUcache,basedonLinkedHashMap>.Thiscachehasafixedmaximumnumberofelements(e>cacheSize ).Ifthecacheisfullandanotherentryisa
dded,theLRU(leastrecentlyused)entryisdropped.This
classisthread-safe.Allmethodsofthisclassaresynchronized
. Author:Christiand''Heureuse,InventecInformatikAG,Zu
rich,Switzerland
Multi-licensed:EPL/LGPL/GPL/AL/BS
D./publicclassLRUCache{privatestaticfinalfloathashTab
leLoadFactor=0.75f;privateLinkedHashMapmap;privateintc
acheSize;/CreatesanewLRUcache.@paramcacheSizethemaxi
mumnumberofentriesthatwillbekeptinthiscache./publicLR
UCache(intcacheSize){this.cacheSize=cacheSize;inthashTabl
eCapacity=(int)Math.ceil(cacheSize/hashTableLoadFactor)+1;
map=newLinkedHashMap(hashTableCapacity,hashTableLoadFact
or,true){//(ananonymousinnerclass)privatestaticfinallo
ngserialVersionUID=1;@OverrideprotectedbooleanremoveEldest
Entry(Map.Entryeldest){returnsize()>LRUCache.this.cac
heSize;}};}/Retrievesanentryfromthecache.
Theret
rievedentrybecomestheMRU(mostrecentlyused)entry.@param
keythekeywhoseassociatedvalueistobereturned.@return
thevalueassociatedtothiskey,ornullifnovaluewiththis
keyexistsinthecache./publicsynchronizedVget(Kkey){ret
urnmap.get(key);}/Addsanentrytothiscache.Thenewent
rybecomestheMRU(mostrecentlyused)entry.Ifanentrywith
thespecifiedkeyalreadyexistsinthecache,itisreplacedby
thenewentry.Ifthecacheisfull,theLRU(leastrecentlyuse
d)entryisremovedfromthecache.@paramkeythekeywithw
hichthespecifiedvalueistobeassociated.@paramvalueava
luetobeassociatedwiththespecifiedkey./publicsynchronized
voidput(Kkey,Vvalue){map.put(key,value);}/Clearst
hecache./publicsynchronizedvoidclear(){map.clear();}/
Returnsthenumberofusedentriesinthecache.@returnthenum
berofentriescurrentlyinthecache./publicsynchronizedintu
sedEntries(){returnmap.size();}/ReturnsaCollectio
nthatcontainsacopyofallcacheentries.@returnaode>Collectionwithacopyofthecachecontent./publics
ynchronizedCollection>getAll(){returnnewArra
yList>(map.entrySet());}}//endclassLRUCache--
-----------------------------------------------------------------
-----------------------//TestroutinefortheLRUCacheclass.pub
licstaticvoidmain(String[]args){LRUCachec
=newLRUCache(3);c.put("1","one");
//1c.put("2","two");
//21c.put("3","three");//321c
.put("4","four");//432if(c.get("
2")==null)thrownewError();//243c.put("5","five");
//524c.put("4","secondfour");
//452//Verifycachecontent.if(c.usedEntrie
s()!=3)thrownewError();if(!c.get("4").equals(
"secondfour"))thrownewError();if(!c.get("5").equals("five")
)thrownewError();if(!c.get("2").equals("two"))
thrownewError();//Listcachecontent.for(Map.Entry,String>e:c.getAll())System.out.println(e.getKey()+":"
+e.getValue());}代码出自：http://www.source-code.biz/snippets/java/6
.htm在博客http://gogole.iteye.com/blog/692103http://gogole.iteye.co
m/blog/692103里，作者使用的是双链表+hashtable的方式实现的。如果在面试题里考到如何实现LRU，考官一
般会要求使用双链表+hashtable的方式。所以，我把原文的部分内容摘抄如下：双链表+hashtable实现原理：将
Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cach
e直接加到链表头中。这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾
则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。publ
icclassLRUCache{privateintcacheSize;privateHashtable,Entry>nodes;//缓存容器privateintcurrentSize;privateEntryfirst;
//链表头privateEntrylast;//链表尾publicLRUCache(inti){currentSize
=0;cacheSize=i;nodes=newHashtable(i);//缓存容器}
/获取缓存中对象,并把它放在最前面/publicEntryget(Objectkey){Entrynode
=nodes.get(key);if(node!=null){moveToHead(node);returnnode
;}else{returnnull;}}/添加entry到hashtable,并把entry/publi
cvoidput(Objectkey,Objectvalue){//先查看hashtable是否存在该entry,如
果存在，则只更新其valueEntrynode=nodes.get(key);if(node==null){//缓存
容器是否已经超过大小.if(currentSize>=cacheSize){nodes.remove(last.key);
removeLast();}else{currentSize++;}node=newEntry();}node.valu
e=value;//将最新使用的节点放到链表头，表示最新使用的.moveToHead(node);nodes.put(key,
node);}/将entry删除,注意：删除操作只有在cache满了才会被执行/publicvoidremo
ve(Objectkey){Entrynode=nodes.get(key);//在链表中删除if(node!=n
ull){if(node.prev!=null){node.prev.next=node.next;}if(nod
e.next!=null){node.next.prev=node.prev;}if(last==node)las
t=node.prev;if(first==node)first=node.next;}//在hashtable中删
除nodes.remove(key);}/删除链表尾部节点，即使用最后使用的entry/privatevoid
removeLast(){//链表尾不为空,则将链表尾指向null.删除连表尾（删除最少使用的缓存对象）if(last!=
null){if(last.prev!=null)last.prev.next=null;elsefirst=n
ull;last=last.prev;}}/移动到链表头，表示这个节点是最新使用过的/privatevoid
moveToHead(Entrynode){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!=n
ull){node.next=first;first.prev=node;}first=node;node.prev
=null;if(last==null)last=first;}/清空缓存/publicvoidcl
ear(){first=null;last=null;currentSize=0;}}classEntry{En
tryprev;//前一节点Entrynext;//后一节点Objectvalue;//值Objectkey;//键}JA
VA的LRU缓存实现1、LRUCache的LinkedHashMap实现2、LRUCache的链表+HashMap实现3、Li
nkedHashMap的FIFO实现4、调用示例LRU是LeastRecentlyUsed的缩写，翻译过来就是“最近最少使用
”，LRU缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉，比如我们缓存1000
0条数据，当数据小于10000时可以随意添加，当超过10000时就需要把新的数据添加进来，同时要把过期数据删除，以确保我们最大缓存
10000条，那怎么确定删除哪条过期数据呢，采用LRU算法实现的话就是将最老的数据删掉，废话不多说，下面来说下Java版的LRU缓
存实现Java里面实现LRU缓存通常有两种选择，一种是使用LinkedHashMap，一种是自己设计数据结构，使用链表+HashM
apLRUCache的LinkedHashMap实现LinkedHashMap自身已经实现了顺序存储，默认情况下是按照元素的添加
顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方
法，默认是返回false，即不删除数据，我们使用LinkedHashMap实现LRU缓存的方法就是对LinkedHashMap实现
简单的扩展，扩展方式有两种，一种是inheritance，一种是delegation，具体使用什么方式看个人喜好//LinkedH
ashMap的一个构造函数，当参数accessOrder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
publicLinkedHashMap(intinitialCapacity,floatloadFactor,boole
anaccessOrder){super(initialCapacity,loadFactor);this.access
Order=accessOrder;}//LinkedHashMap自带的判断是否删除最老的元素方法，默认返回false，即不
删除老数据//我们要做的就是重写这个方法，当满足一定条件时删除老数据protectedbooleanremoveEldestE
ntry(Map.Entryeldest){returnfalse;}LRU缓存LinkedHashMap(in
heritance)实现采用inheritance方式实现比较简单，而且实现了Map接口，在多线程环境使用时可以使用Collec
tions.synchronizedMap()方法实现线程安全操作packagecn.lzrabbit.structure.lr
u;importjava.util.LinkedHashMap;importjava.util.Map;/Creat
edbyliuzhaoon14-5-15./publicclassLRUCache2extends
LinkedHashMap{privatefinalintMAX_CACHE_SIZE;publicLR
UCache2(intcacheSize){super((int)Math.ceil(cacheSize/0.75)
+1,0.75f,true);MAX_CACHE_SIZE=cacheSize;}@Overrideprotec
tedbooleanremoveEldestEntry(Map.Entryeldest){returnsize()>
MAX_CACHE_SIZE;}@OverridepublicStringtoString(){StringBui
ldersb=newStringBuilder();for(Map.Entryentry:entry
Set()){sb.append(String.format("%s:%s",entry.getKey(),entry.
getValue()));}returnsb.toString();}}这样算是比较标准的实现吧，实际使用中这样写还是有些
繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦finalintcacheSize=100;Map,String>map=newLinkedHashMap((int)Math.ceil
(cacheSize/0.75f)+1,0.75f,true){@Overrideprotectedboole
anremoveEldestEntry(Map.Entryeldest){returns
ize()>cacheSize;}};LRU缓存LinkedHashMap(delegation)实现delegation方
式实现更加优雅一些，但是由于没有实现Map接口，所以线程同步就需要自己搞定了packagecn.lzrabbit.structu
re.lru;importjava.util.LinkedHashMap;importjava.util.Map;import
java.util.Set;/Createdbyliuzhaoon14-5-13./publicclas
sLRUCache3{privatefinalintMAX_CACHE_SIZE;privatefin
alfloatDEFAULT_LOAD_FACTOR=0.75f;LinkedHashMapmap;pu
blicLRUCache3(intcacheSize){MAX_CACHE_SIZE=cacheSize;//根据c
acheSize和加载因子计算hashmap的capactiy，+1确保当达到cacheSize上限时不会触发hashmap的扩容
，intcapacity=(int)Math.ceil(MAX_CACHE_SIZE/DEFAULT_LOAD_FA
CTOR)+1;map=newLinkedHashMap(capacity,DEFAULT_LOAD_FACTOR,
true){@OverrideprotectedbooleanremoveEldestEntry(Map.Entry
eldest){returnsize()>MAX_CACHE_SIZE;}};}publicsynchroni
zedvoidput(Kkey,Vvalue){map.put(key,value);}publicsync
hronizedVget(Kkey){returnmap.get(key);}publicsynchronize
dvoidremove(Kkey){map.remove(key);}publicsynchronizedSet
>getAll(){returnmap.entrySet();}publicsync
hronizedintsize(){returnmap.size();}publicsynchronizedvo
idclear(){map.clear();}@OverridepublicStringtoString(){
StringBuildersb=newStringBuilder();for(Map.Entryentry:ma
p.entrySet()){sb.append(String.format("%s:%s",entry.getKey(),
entry.getValue()));}returnsb.toString();}}LRUCache的链表+HashM
ap实现注：此实现为非线程安全，若在多线程环境下使用需要在相关方法上添加synchronized以实现线程安全操作package
cn.lzrabbit.structure.lru;importjava.util.HashMap;/Created
byliuzhaoon14-5-12./publicclassLRUCache1{privatef
inalintMAX_CACHE_SIZE;privateEntryfirst;privateEntrylast;
privateHashMap>hashMap;publicLRUCache1(intca
cheSize){MAX_CACHE_SIZE=cacheSize;hashMap=newHashMapntry>();}publicvoidput(Kkey,Vvalue){Entryentry=
getEntry(key);if(entry==null){if(hashMap.size()>=MAX_CAC
HE_SIZE){hashMap.remove(last.key);removeLast();}entry=new
Entry();entry.key=key;}entry.value=value;moveToFirst(entr
y);hashMap.put(key,entry);}publicVget(Kkey){Entry
entry=getEntry(key);if(entry==null)returnnull;moveToFirs
t(entry);returnentry.value;}publicvoidremove(Kkey){Entry
entry=getEntry(key);if(entry!=null){if(entry.pre!=nul
l)entry.pre.next=entry.next;if(entry.next!=null)entry.nex
t.pre=entry.pre;if(entry==first)first=entry.next;if(en
try==last)last=entry.pre;}hashMap.remove(key);}privatev
oidmoveToFirst(Entryentry){if(entry==first)return;if(en
try.pre!=null)entry.pre.next=entry.next;if(entry.next!=n
ull)entry.next.pre=entry.pre;if(entry==last)last=last.p
re;if(first==null||last==null){first=last=entry;re
turn;}entry.next=first;first.pre=entry;first=entry;ent
ry.pre=null;}privatevoidremoveLast(){if(last!=null){
last=last.pre;if(last==null)first=null;elselast.next=
null;}}privateEntrygetEntry(Kkey){returnhashMap.g
et(key);}@OverridepublicStringtoString(){StringBuildersb
=newStringBuilder();Entryentry=first;while(entry!=null)
{sb.append(String.format("%s:%s",entry.key,entry.value));en
try=entry.next;}returnsb.toString();}classEntry{p
ublicEntrypre;publicEntrynext;publicKkey;publicVvalue;
}}LinkedHashMap的FIFO实现FIFO是FirstInputFirstOutput的缩写，也就是常说的先入先
出，默认情况下LinkedHashMap就是按照添加顺序保存，我们只需重写下removeEldestEntry方法即可轻松实现一个
FIFO缓存，简化版的实现代码如下finalintcacheSize=5;LinkedHashMaptring>lru=newLinkedHashMap(){@Overridepro
tectedbooleanremoveEldestEntry(Map.Entryeldes
t){returnsize()>cacheSize;}};调用示例测试代码ViewCode运行结果ViewCode
短址(shortURL)原理及其实现前言：最近看了一些关于短址（shortURL）方面的一些博客，有些博客说到一些好的东西，但
是，也不是很全，所以，这篇博客算是对其它博客的一个总结吧。介绍：短址，顾名思义，就是把长的URL转成短的URL,现在提供这
种服务的有很多公司，我们以google家的URLshortener服务：http://goo.gl/http://goo.
gl/为例。首先我们到http://goo.gl/http://goo.gl/，然后把本文博客的地址http://blog.c
sdn.net/beiyeqinghttp://blog.csdn.net/beiyetengqingteng输入进去，最后它会
返回一个更短的URL，http://goo.gl/Jfs6q。如下图所示：URL解析：当我们在浏览器里输入http://go
o.gl/Jfs6qhttp://goo.gl/Jfs6q时，DNS首先解析获得http://goo.gl/的IP地址。当DNS
获得IP地址以后（比如：74.125.225.72），会向这个地址发送HTTPGET请求，查询Jfs6q，这个时候，http
://goo.gl/Jfs6qhttp://goo.gl/服务器会把请求通过HTTP301转到对应的长URLhttp://bl
og.csdn.net/beiyetengqinghttp://blog.csdn.net/beiyeqinghttp://blo
g.csdn.net/beiyetengqingteng。后面的解析过程就和平常网址解析是一样的了。短址本质：短址本质上是实现了
一个映射函数f:X->Y。而这个映射函数必须同时具有两个特点：1.如果x1!=x2,则f(x1)!=f
(x2);2.对于每一个y,能够找到唯一的一个x使得f(x)=y;对于任何的线性函数，比如f(x)=2x，都
满足这样的条件。好了，如果了解了短址的本质，我们再来看它是如何实现的。注明：在googleURLshortener服务中，它
允许一个长url对应多个短的url。这可能是出于安全上的考虑。在本文中，我们不考虑这种情况。实现：短址的长度一般设为6位，
而每一位是由[a-z,A-Z,0-9]总共62个字母组成的，所以6位的话，总共会有62^6~=568
亿种组合，基本上够用了。在googleURLshortener服务中，短址长度为5，大概有9亿多种组合.假设我们用数据库
来保存长地址和短地址的映射，那么，在表LongtoShortURL中，我们会有三列：1.ID，int,自动增长；2.LU
RL，varchar,//长URL；3.SURL,varchar,//短URL。现在我们考虑通过如何长URL得到唯一的
短URL。在讲具体算法以前，先提一个问题：10进制数和16进制数之间的转换是否满足刚刚提到的映射函数f:X->Y中的两个条
件？答案：是。本文的思路也是利用进制之间的转换。因为我们总共有62个字母，我们可以自创一种进制，叫做62进制。其规则如下：0→a1→b25→z52→061→9所以，对于每一个长地址，我们可以根据它的ID，得到一个6位的62进制数，这个6位的62进制数就是我们的短址。具体实现如下：publicArrayListbase62(intid){ArrayListvalue=newArrayList();while(id>0){intremainder=id%62;value.add(remainder);id=id/62;}returnvalue;}举例：对于ID=138，通过base62(138),我们得到value=[14,2]。根据上面的对应规则表，我们可以得到其对应的短址为：aaaabn。(由value得到具体的短址，可以通过switch语句得到，因为代码太长，在此略过。)当我们想通过短址找到所对应的长地址，方法也很简单，就是把62进制数转成10进制数即可，这样我们就可以得到长地址的ID了。代码如下：publicstaticintbase10(ArrayListbase62){//makesurethesizeofbase62is6for(inti=1;i<=6-base62.size();i++){base62.add(0,0);}intid=0;intsize=base62.size();for(inti=0;i
|
