1 先来先淘汰（FIFO）
失效算法常见于缓存系统中。因为缓存往往占据大量内存，而内存空间是相对昂贵，且空间有限的，那么针对一部分值，就要依据相应的算法进行失效或移除操作。
1.1 概述
First In First Out，先来先淘汰。这种算法在每一次新数据插入时，如果队列已满，则将最早插入的数据移除。
1.2 实现
可以方便的借助LinkedList来实现,因为新添加的元素会向后推
package com.oldlu.release; import java.util.Iterator; import java.util.LinkedList; public class FIFO { LinkedList<Integer> fifo = new LinkedList<Integer>(); int size = 3; //添加元素 public void add(int i){ //每次新数据推到首位 fifo.addFirst(i); if (fifo.size() > size){ fifo.removeLast(); } print(); } //缓存命中 public void read(int i){ Iterator<Integer> iterator = fifo.iterator(); while (iterator.hasNext()){ int j = iterator.next(); if (i == j){ System.out.println("find it!"); print(); return ; } } System.out.println("not found!"); print(); } //打印缓存 public void print(){ System.out.println(this.fifo); } //测试 public static void main(String[] args) { FIFO fifo = new FIFO(); System.out.println("add 1‐3:"); fifo.add(1); fifo.add(2); fifo.add(3); System.out.println("add 4:"); fifo.add(4); System.out.println("read 2:"); fifo.read(2); System.out.println("read 100:"); fifo.read(100); System.out.println("add 5:"); fifo.add(5); } }
1.3 结果分析
解析:
1-3按顺序放入，没有问题
4放入，那么1最早放入，被挤掉
读取2，读到，但是不会影响队列顺序（2依然是时间最老的）
读取100，读不到，也不会产生任何影响
5加入，踢掉了2，而不管2之前有没有被使用（不够理性）
1.4 优缺点
实现非常简单
不管元素的使用情况，哪怕有些数据会被频繁用到，时间最久也会被踢掉
2 最久未用淘汰（LRU）
2.1 概述
LRU全称是Least Recently Used，即淘汰最后一次使用时间最久远的数值。FIFO非常的粗暴，不管有没有用到，直接踢掉时间久的元素。而LRU认为，最近频繁使用过的数据，将来也很大程度上会被频繁用到，故而淘汰那些懒惰的数据。LinkedHashMap，数组，链表均可实现LRU，下面仍然以链表为例：新加入的数据放在头部，最近访问的，也移到头部，空间满时，将尾部元素删除。
2.2 实现
package com.oldlu.release; import java.util.Iterator; import java.util.LinkedList; public class LRU { LinkedList<Integer> lru = new LinkedList<Integer>(); int size = 3; //添加元素 public void add(int i){ lru.addFirst(i); if (lru.size() > size){ lru.removeLast(); } print(); } //缓存命中 public void read(int i){ Iterator<Integer> iterator = lru.iterator(); int index = 0; while (iterator.hasNext()){ int j = iterator.next(); //读到就放到最前 if (i == j){ System.out.println("find it!"); lru.remove(index); lru.addFirst(j); print(); return ; } index++; } System.out.println("not found!"); print(); } //打印缓存 public void print(){ System.out.println(this.lru); } //测试 public static void main(String[] args) { LRU lru = new LRU(); System.out.println("add 1‐3:"); lru.add(1); lru.add(2); lru.add(3); System.out.println("add 4:"); lru.add(4); System.out.println("read 2:"); lru.read(2); System.out.println("read 100:"); lru.read(100); System.out.println("add 5:"); lru.add(5); } }
2.3 结果分析
解析:
1-3加入，没有问题
4加入，踢掉1，没问题
读取2，读到，注意，2被移到了队首！
读取100，读不到，没影响
5加入，因为2之前被用到，不会被剔除，3和4都没人用，但是3更久，被剔除
3 最近最少使用（LFU）
3.1 概述
Least Frequently Used，即最近最少使用。它要淘汰的是最近一段时间内，使用次数最少的值。可以认为比LRU多了一重判断。LFU需要时间和次数两个维度的参考指标。需要注意的是，两个维度就可能涉及到同一时间段内，访问次数相同的情况，就必须内置一个计数器和一个队列，计数器算数，队列放置相同计数时的访问时间。
3.2 实现
package com.oldlu.release; public class Dto implements Comparable<Dto> { private Integer key; private int count; private long lastTime; public Dto(Integer key, int count, long lastTime) { this.key = key; this.count = count; this.lastTime = lastTime; } @Override public int compareTo(Dto o) { int compare = Integer.compare(this.count, o.count); return compare == 0 ? Long.compare(this.lastTime, o.lastTime) : compare; } @Override public String toString() { return String.format("[key=%s,count=%s,lastTime=%s]",key,count,lastTime); } public Integer getKey() { return key; } public void setKey(Integer key) { this.key = key; } public int getCount() { return count; } public void setCount(int count) { this.count = count; } public long getLastTime() { return lastTime; } public void setLastTime(long lastTime) { this.lastTime = lastTime; } }
package com.oldlu.release; import java.util.Collections; import java.util.HashMap; import java.util.Map; public class LFU { private final int size = 3; private Map<Integer,Integer> cache = new HashMap<>(); private Map<Integer, Dto> count = new HashMap<>(); //投放 public void put(Integer key, Integer value) { Integer v = cache.get(key); if (v == null) { if (cache.size() == size) { removeElement(); } count.put(key, new Dto(key, 1, System.currentTimeMillis())); } else { addCount(key); } cache.put(key, value); } //读取 public Integer get(Integer key) { Integer value = cache.get(key); if (value != null) { addCount(key); return value; } return null; } //淘汰元素 private void removeElement() { Dto dto = Collections.min(count.values()); cache.remove(dto.getKey()); count.remove(dto.getKey()); } //更新计数器 private void addCount(Integer key) { Dto Dto = count.get(key); Dto.setCount(Dto.getCount()+1); Dto.setLastTime(System.currentTimeMillis()); } //打印缓存结构和计数器结构 private void print(){ System.out.println("cache="+cache); System.out.println("count="+count); } public static void main(String[] args) { LFU lfu = new LFU(); //前3个容量没满，1,2,3均加入 System.out.println("add 1‐3:"); lfu.put(1, 1); lfu.put(2, 2); lfu.put(3, 3); lfu.print(); //1,2有访问，3没有，加入4，淘汰3 System.out.println("read 1,2"); lfu.get(1); lfu.get(2); lfu.print(); System.out.println("add 4:"); lfu.put(4, 4); lfu.print(); //2=3次，1,4=2次，但是4加入较晚，再加入5时淘汰1 System.out.println("read 2,4"); lfu.get(2); lfu.get(4); lfu.print(); System.out.println("add 5:"); lfu.put(5, 5); lfu.print(); } }
3.3 结果分析
解析:
1-3加入，没问题，计数器为1次
访问1，2，使用次数计数器上升为2次，3没有访问，仍然为1
4加入，3的访问次数最少（1次），所以踢掉3，剩下124
访问2，4，计数器上升，2=3次，1，4=2次，但是1时间久
5加入，踢掉1，最后剩下2，4，5
4 应用案例
redis属于缓存失效的典型应用场景，常见策略如下：
noeviction: 不删除策略, 达到最大内存限制时, 如果需要更多内存, 直接返回错误信息（ 比较危险）。
allkeys-lru：对所有key，优先删除最近最少使用的 key (LRU)。
allkeys-random： 对所有key， 随机删除一部分（听起来毫无道理）。
volatile-lru：只限于设置了 expire 的key，优先删除最近最少使用的key (LRU)。
volatile-random：只限于设置了 expire 的key，随机删除一部分。
volatile-ttl：只限于设置了 expire 的key，优先删除剩余时间(TTL) 短的key。
