介绍Redis是一个内存数据库。当Redis使用的内存超过物理内存的限制时，内存数据会频繁地与磁盘进行交换，交换会导致Redis性能急剧下降。所以在生产环境中我们通过配置参数maxmemoey来限制使用的内存大小。当实际使用的内存超过maxmemoey时，Redis提供了以下可选策略。noeviction：写请求返回错误随机删除volatile-ttl：按照过期时间的顺序删除，越早过期的先删除allkeys-lru：在所有键值对中，使用lru算法删除allkeys-lfu：在所有键值对中，使用lfu算法删除所有keys-random：随机删除所有键值对。下面我们来详细了解一下lru和lfu算法，这是两种常见的缓存淘汰算法。“因为计算机缓存的容量有限，我们需要删除那些无用的数据，而两种算法的区别在于判断无用的纬度不同。”LRU算法》lru(Leastrecentlyused,leastrecentlyused)算法，即最近访问的数据以后有很大概率会被访问，这很有用。而长时间没有访问的数据应该被淘汰。”在lru算法中，数据会放在一个链表中，链表的头节点是最近访问过的数据，链表的尾节点是很久没有访问过的数据“lru算法的核心实现是哈希表加双向链表。”链表可以用来维护访问元素的顺序，而哈希表可以帮助我们在O(1)时间下访问元素complexity."至于为什么是双向链表？"?主要目的是删除元素，所以需要获取前驱节点。数据结构图如下使用双向链表+HashMap双向链表节点定义如下键=键；这个。value=value;}}PublicclassDoubleList{privateListNodehead;privateListNodetail;publicDoubleList(){head=newListNode();tail=newListNode();head.next=tail;tail.pre=head;}??publicvoidremove(ListNodenode){node.pre.next=node.next;node.next.pre=node.pre;}publicvoidaddLast(ListNodenode){node.pre=tail.pre;tail.pre=node;node.pre.next=node;node.next=tail;}publicListNoderemoveFirst(){if(head.next==tail){returnull;}ListNodefirst=head.next;remove(first);returnfirst;}}封装了一个缓存类，提供了最基本的get和放方法。“应该注意的是，这两种基本方法都涉及修改两种数据结构。”publicclassMyLruCache{privateintcapacity;privateDoubleListdoubleList;privateMapmap;publicMyLruCache(intcapacity){this.capacity=capacity;map=newHashMap<>();doubleList=newDoubleList();}publicVget(Objectkey){ListNodenode=map.get(key);if(node==null){returnnull;}//先删除节点，再连接尾部doubleList.remove(node);doubleList.addLast(node);returnnode.value;}publicvoidput(Kkey,Vvalue){//这里直接调用get方法，如果存在则移动到get里面的尾部，不用再移动，修改value即可直接if((get(key))!=null){map.get(key).value=value;return;}//如果超过容量，去掉headerif(map.size()==capacity){ListNodelistNode=doubleList.removeFirst();map.remove(listNode.key);}//如果不存在，会出来一个新的ListNodenode=newListNode(key,value);map.put(key,node);doubleList.addLast(node);}}这里我们最近访问的放在链表的尾节点，并且不常访问的放在链表的头节点进行测试，输出为链表的正序输出（代码为了简单没有贴toString方法）MyLruCachemyLruCache=newMyLruCache<>(3);//{5:5}myLruCache.put("5","5");//{5:5}{3:3}myLruCache.put("3","3";);//{5:5}{3:3}{4:4}myLruCache.put("4","4");//{3:3}{4:4}{2:2}myLruCache.put("2","2");//{4:4}{2:2}{3:3}myLruCache.get("3");“因为LinkedHashMap的底层实现是哈希表加双向链表，所以可以把HashMap和DoubleList换成LinkedHashMap重写上面的类。”我再演示一个比较风骚的操作，重写一个构造函数和removeEldestEntry方法即可。使用LinkedHashMap实现LRUpublicclassLruCacheextendsLinkedHashMap{privateintcacheSize;publicLruCache(intcacheSize){/***initialCapacity：初始容量大小*loadFactor：加载因子*accessOrder：false基于插入排序（默认），true基于Access排序*/super(cacheSize,0.75f,true);this.cacheSize=cacheSize;}/***调用put或putAll方法时会调用下面的方法，是否删除最旧的数据，默认为false*/@OverrideprotectedbooleanremoveEldestEntry(Map.Entryeldest){returnsize()>cacheSize;}}注意这个缓存不是线程安全的，可以调用Collections.synchronizedMap方法返回线程安全mapLruCachelruCache=newLruCache(3);MapsafeMap=Collections.synchronizedMap(lruCache);Collections.synchronizedMap以非常简单的方式实现线程安全，只是返回一个代理类。代理类锁住了Map接口的所有方法publicstaticMapsynchronizedMap(Mapm){returnnewSynchronizedMap<>(m);}LFU算法》LRU算法有问题，当一个长时间没有被访问的键偶尔被访问时，一个比这个键访问频率更高的键可能会被淘汰。”即LRU算法对key的热度判断可能不准确，LFU算法（LeastFrequentlyUsed）根据访问频率判断key的热度，在一个周期内删除访问频率低的数据时间段，比LRU算法更准确，用3张哈希表实现lfu算法那么我们应该如何组织数据呢，为了实现键值对的快速访问，用一个map来保存键值对privateHashMapkeyToFreq;也需要用map来保存keys的访问频率privateHashMapkeyToFreq;"当然也可以把value和访问频率封装成一个类，用map来代替上面两张图。”接下来是核心部分，删除访问频率最低的数据。为了在O(1)时间复杂度内找到访问频率最低的数据，我们需要一个变量minFreq来记录访问频率最低的数据。每个访问频率可能对应多个k眼睛。当空间不够时，我们需要删除最早访问的数据，所以需要如下数据结构，Map。每次内存不够就删除sortedset的第一个元素。而这个有序集合必须能够快速删除某个key，因为访问某个key后，需要从这个集合中删除，而freq+1对应的集合中有很多个有序集合，但是可以满足快速删除某个key的需求只有set，但是set插入的数据是无序的。”幸好Java有LinkedHashSet类，它是链表和集合的结合。链表不能快速删除元素，但可以保证插入顺序。集合内部元素是无序的，但可以快速删除元素，完美。”下面是具体实现。publicclassLfuCache{privateHashMapkeyToVal;privateHashMapkeyToFreq;privateHashMap>freqTokeys;privateintminFreq;privateintcapacity;publicLfuCache(intcapacity){keyToVal=newHashMap<>();keyToFreq=newHashMap<>();freqTokeys=newHashMap<>();this.capacity=capacity;this.minFreq=0;}publicVget(Kkey){Vv=keyToVal.get(key);if(v==null){returnnull;}increaseFrey(key);returnv;}publicvoidput(Kkey,Vvalue){//get方法会增加频率if(get(key)!=null){//重置值keyToVal.put(key,value);return;}//超出容量，删除频率最低的keyif(keyToVal.size()>=capacity){removeMinFreqKey();}keyToVal.put(key,value);keyToFreq.put（键，1）；//key对应的value存在，返回已有的key//key对应的value不存在，添加key和valuefreqTokeys.putIfAbsent(1,newLinkedHashSet<>());freqTokeys.get(1).add(key);this.minFreq=1;}//删除频率最低的keyprivatevoidremoveMinFreqKey(){LinkedHashSetkeyList=freqTokeys.get(minFreq);KdeleteKey=keyList.iterator().next();键列表。remove(deleteKey);if(keyList.isEmpty()){//这里删除元素后不需要重新设置minFreq//因为put方法会将minFreq设置为1freqTokeys.remove(keyList);}keyToVal.remove(deleteKey);keyToFreq.remove(deleteKey);}//增加频率privatevoidincreaseFrey(Kkey){intfreq=keyToFreq.get(key);keyToFreq.put(key,freq+1);freqTokeys.get(freq).remove(key);freqTokeys.putIfAbsent(freq+1,newLinkedHashSet<>());freqTokeys.get(freq+1).add(key);if(freqTokeys.get(freq).isEmpty()){freqTokeys.remove(freq);//最小频率集合为空，将key移动到minFreq+1对应的集合中//所以minFreq还需要加上1if(freq==this.minFreq){this.minFreq++;}}}}测试LfuCachelfuCache=newLfuCache(2);lfuCache.put("1","1");lfuCache.put("2","2");//1System.out.println(lfuCache.get("1"));lfuCache.put("3","3");//1的频率为2，2和3的频率为1，但是2早被访问了，所以被清空//结果为nullSystem.out。println(lfuCache.get("2"));
