如果要说计算机系统中最能体现tradeoff的技术，那非缓存莫属。为了协调高速组件和低速组件之间的速度差异，增加一个中间缓存层是解决这种冲突最有效的方法。其中JVM堆内缓存是缓存系统的重要组成部分，最常用的算法有FIFO/LRU/LFU。FIFO是一个简单的队列，先进先出。LRU是最近最少使用，最久未使用的数据先被移除。是时间维度。LFU是最近最少使用的，访问次数最少的数据先被移除。是统计维度。因为过期也是缓存的一个重要特性。在设计这三种缓存算法时，都需要额外的存储空间来存储过期时间。下面分别讨论这三种缓存算法的运行和设计要点，暂不考虑高并发环境。FIFO是先进先出的。如果缓存容量已满，最早加入缓存的数据将被优先移除；它可以通过使用队列在内部实现。OperationObjectget(key):获取保存的数据，如果数据不存在或者已经过期，返回null。voidput(key,value,expireTime)：加入缓存。不管这个key是否已经存在，都会被当作一个新的key（移除旧的key）；如果空间不足，则删除过期的key，如果空间不足，则删除最先加入缓存的key。如果不指定过期时间，则表示永远不会自动过期。注意我们允许key有过期时间，这和普通的FIFO不同，所以设计这道题的时候需要注意一下。（也是面试考察的重点，重在设计而不是算法。）普通的FIFO可能大家写的很简单。加入过期时间的考虑后，设计中需要更多的考虑。下面的例子是一个没有考虑并发环境的FIFO设计。设计思路1）使用普通的hashMap保存缓存数据。2）需要额外的映射来保存密钥的过期特征。例子中使用了一个TreeMap，以“剩余生存时间”为key，利用了TreeMap的排序特性。publicclassFIFOCache{//按访问时间排序，保存所有key-valueprivatefinalMapCACHE=newLinkedHashMap<>();//过期数据，只保存有过期时间的key//暂不考虑并发，我们认为same时间段内没有重复的key。如果修改了，可以用setprivatefinalTreeMapEXPIRED=newTreeMap<>();privatefinalintcapacity;publicFIFOCache(intcapacity){this.capacity=capacity;}publicObjectget(Stringkey){//Valuevalue=CACHE替换值。get(key);if(value==null){returnnull;}//如果不包括过期时间longexpired=value.expired;longnow=System.nanoTime();//过期if(expired>0&&expired<=now){CACHE.remove(key);EXPIRED.remove(expired);returnnull;}returnvalue.value;}publicvoidput(Stringkey,Objectvalue){put(key,value,-1);}publicvoidput(Stringkey,Objectvalue,intseconds){//如果容量不足，移除过期数据if(capacityiterator=EXPIRED.keySet().iterator();while(iterator.hasNext()){long_key=iterator.next();//如果已经过期，或者容量还在溢出，删除if(_key>now){break;}//一次性移除所有过期的keyString_value=EXPIRED。get(_key);CACHE.remove(_value);iterator.remove();}}//如果容量还不够，则移除最早访问的数据if(capacityiterator=CACHE.keySet().iterator();while(iterator.hasNext()&&capacity0){EXPIRED.remove(expired);}iterator.remove();}}//如果这个key已经存在，移除旧数据Valuecurrent=CACHE.remove(key);if(current!=null&¤t.expired>0){EXPIRED.remove(current.expired);}//如果指定过期时间if(seconds>0){longexpireTime=expiredTime(seconds);EXPIRED.put(expireTime,key);CACHE.put(key,newValue(expireTime,value));}else{CACHE.put(key,newValue(-1,value));}}privatelongexpiredTime(intexpired){returnSystem.nanoTime()+TimeUnit.SECONDS.toNanos(过期);}publicvoidremove(Stringkey){Valuevalue=CACHE.remove(key);if(value==null){return;}longexpired=value.expired;if(expired>0){EXPIRED.remove(expired);}}classValue{longexpired;//过期时间，纳秒Objectvalue;价值(longexpired,Objectvalue){this.expired=expired;this.value=value;}}}LRUleastrecentlyused，最近最少使用，是目前最常用的缓存算法和设计方案之一，其去除策略为“当缓存（页）满时，先剔除最近一段时间未使用的数据”，优点是易于设计和使用，适用场景广泛的算法可以参考leetcode146(LRUCache)操作Objectget(key)：从缓存中获取key对应的数据，如果key已经过期，则移除key并返回nullvoidput(key,value,expired)：设置k-v，如果容量不足，按照LRU替换算法移除“最长未使用的key”，需要注意的是先按照LRU移除过期的key，如果不够，则根据LRU移除未过期的keyLRU，如果没有设置过期时间，则认为永远不会自动过期。这里设计的关键是过期时间特性，这与传统的LRU不同。设计思路LRU的基本算法需要了解；每次put和get都需要更新key对应的访问时间，我们需要一个可以保存key最新访问时间并且可以排序的数据结构。由于包含了过期时间特性，因此需要将具有过期时间的密钥保存在一个额外的数据结构中。暂时不考虑并发操作；尝试同时考虑空间复杂性和时间复杂性。这道题还是偏向于设计题，而不是纯算法题。这道题的代码和FIFO基本一样，唯一不同的是get()方法。对于LRU，get方法需要重新设置访问时间（即调整缓存中的顺序）publicObjectget(Stringkey){//Valuevalue=CACHE.get(key);if(value==null){returnnull;}//如果不包括过期时间longexpired=value.expired;longnow=System.nanoTime();//过期if(expired>0&&expired<=now){CACHE.remove(key);EXPIRED.remove(expired);returnnull;}//相比FIFO，增加顺序resetCACHE.remove(key);CACHE.put(key,value);returnvalue.value;}LFU最近不常用，当缓存容量满了，移除元素访问次数最少的，如果有多个访问次数相同的元素，则去掉访问时间最长的元素。见leetcode460(LFUCache)publicclassLFUCache{//主要保存容器k-vprivateMapkeyToValue=newHashMap<>();//记录每个k的访问次数privateMapkeyToCount=newHashMap<>();//访问相同次数的key列表，按访问次数排序，value为访问相同次数的key列表。privateTreeMap>countToLRUKeys=newTreeMap<>();privateintcapacity;publicLFUCache(intcapacity){this.capacity=capacity;//初始化，默认访问一次，主要解决下面}publicObjectget(Stringkey){if(!keyToValue.containsKey(key)){returnnull;}touch(key);returnkeyToValue.get(key);}/***如果一个key被访问，那么它的访问次数应该被调整。*@paramkey*/privatevoidtouch(Stringkey){intcount=keyToCount.get(key);keyToCount.put(key,count+1);//增加访问次数//把countToLRUKeys.get从原来的访问计数列表中去掉（count).remove(key);//如果满足最小调用次数直到key统计列表为空，则移除调用次数统计if(countToLRUKeys.get(count).size()==0){countToLRUKeys。remove(count);}//然后将这个key的统计信息添加到管理列表LinkedHashSetcountKeys=countToLRUKeys.get(count+1);if(countKeys==null){countKeys=newLinkedHashSet<>();countToLRUKeys.put(count+1,countKeys);}countKeys.add(key);}publicvoidput(Stringkey,Objectvalue){if(capacity<=0){return;}if(keyToValue.containsKey(key)){keyToValue.put(key,value);touch(key);return;}//超过容量后，移除访问次数最少的元素if(keyToValue.size()>=capacity){Map.Entry>entry=countToLRUKeys.firstEntry();Iteratorit=entry.getValue().iterator();StringevictKey=it.next();it.remove();if(!it.hasNext()){countToLRUKeys.remove(entry.getKey());}keyToCount.remove(evictKey);keyToValue.remove(evictKey);}keyToValue.put(key,value);keyToCount.put(key,1);LinkedHashSetkeys=countToLRUKeys.get(1);if(keys==null){keys=newLinkedHashSet<>();countToLRUKeys.put(1,keys);}keys.add(key);}}End本文力图比较三种基本的缓存算法，为缓存构建之路提供更通用、更易用的缓存。可以参考guava的实现。希望这三个代码模板能对你有所帮助。作者简介：品味小姐姐（xjjdog），一个不允许程序员走弯路的公众号。专注于基础架构和Linux。十年架构，每天百亿流量，与你探讨高并发世界，给你不一样的滋味。
