先进先出策略（FIFO，First In First Out）
这种策略的实现是最简单的了，我们利用链表的特性，只要将需要缓存的数据依次添加到链表中，当空间不够时，将链表末尾的数据删除即可（如果我们对队列比较熟悉的话，可以发现这种策略用队列进行实现是最方便的）
实现代码如下：
package com.study.spring.transaction.cache; import lombok.AllArgsConstructor; import java.security.InvalidParameterException; /** * @author dmz * @date Create in 20:57 2019/8/10 */ public class Main { public static void main(String[] args) { link link = new link(4); link.add(1); link.add(2); link.add(3); link.add(4); link.add(5); link.add(6); link.add(7); link.sout(); } static class link { public link(int max) { if (max > 0) { this.max = max; } else { throw new InvalidParameterException("参数不能小于0"); } } // 最大能添加的元素的个数 int max; // 链表中实际已经存储的元素的个数 int size; // 链表的头节点 Node first; // 链表的尾节点 Node last; // 链表中的每个节点 @AllArgsConstructor class Node { // 节点中保存的数据 Object item; // 指向上一个节点 Node pre; // 指向下一个节点 Node next; } public void add(Object item) { Node node = new Node(item, null, null); if (size == 0) { size++; node.pre = null; node.next = null; first = node; last = node; } else { if (size == max) { // 链表中的数据已经满了 // 策略1：先进先出,需要删除头节点 Node second = first.next; second.pre = null; first.next = null; first = second; size--; } // 将数据添加到链表尾部 size++; last.next = node; node.pre = last; last = node; } } public void sout() { Node node = first; for (int i = 0; i < max; i++) { if (size == 0) { System.out.println("链表中没有元素"); break; } else { System.out.println(node.item); node = node.next; if (node == null) { System.out.println("遍历结束"); break; } } } } } }
输出结果如下：
4 5 6 7
最少使用策略（LFU,Least Frequently Out）
根据数据的历史访问频率来淘汰数据，其核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
下面给出两种实现方式
JDK自带优先级队列进行实现
实现思路：利用PriorityQueue小顶堆的特点，关于PriorityQueue可参考我之前的文章 java读源码 之 queue源码分析（PriorityQueue，附图）。每次出队的一定是优先级最低的元素，同时我们自定义比较器，我这里是通过用实体实现Comparable接口的方式。
创建类如下：
package com.study.spring.transaction.huancun; import java.time.LocalDateTime; /** * 进行一个简单的抽象，所有实体都要通过访问时间跟访问次数进行比较 * @author dmz * @date Create in 23:45 2019/8/10 */ public interface Count extends Comparable<Count> { void setLastVisitTime(LocalDateTime localDateTime); LocalDateTime getLastVisitTime(); int getCount(); void setCount(int count); default void addCount() { setCount(getCount() + 1); } // 根据访问次数比较，次数相同的情况下比较访问时间 @Override default int compareTo(Count o2) { return this.getCount() == o2.getCount() ? this.getLastVisitTime().compareTo(o2.getLastVisitTime()) : this.getCount() - o2.getCount(); } } package com.study.spring.transaction.huancun; import lombok.Data; import java.time.LocalDateTime; /** * @author dmz * @date Create in 23:45 2019/8/10 */ @Data public class Entity implements Count, Comparable<Entity> { private int count; private Object object; private LocalDateTime lastVisitTime = LocalDateTime.now(); Entity(Object object) { this.object = object; } } package com.study.spring.transaction.huancun; import java.time.LocalDateTime; import java.util.PriorityQueue; /** * @author dmz * @date Create in 23:55 2019/8/10 */ public class LFUStrategy<T extends Count> { private int max; LFUStrategy(PriorityQueue<T> priorityQueue, int max) { this.max = max; this.priorityQueue = priorityQueue; } private PriorityQueue<T> priorityQueue; /** * 访问排列在index位置的元素 * * @param index 位置 * @return 所在元素 */ public T get(int index) { int count = 1; for (T t : priorityQueue) { if (count == index) { priorityQueue.remove(t); t.addCount(); t.setLastVisitTime(LocalDateTime.now()); // 先remove再add是为了利用其内部特性，调用add方法时会进行排序，将最小的元素置于堆顶 priorityQueue.add(t); return t; } } return null; } @Override public String toString() { return "LFUStrategy{" + "priorityQueue=" + priorityQueue + '}'; } public T remove() { return priorityQueue.poll(); } public void add(T t) { if (max == priorityQueue.size()) { T remove = remove(); System.out.println("执行LFU策略，删除的元素是：" + remove); } else { priorityQueue.offer(t); } } } package com.study.spring.transaction.huancun; import java.util.PriorityQueue; /** * @author dmz * @date Create in 0:08 2019/8/11 */ public class Main { public static void main(String[] args) { PriorityQueue<Entity> priorityQueue = new PriorityQueue<>(); for (int i = 1; i < 7; i++) { Entity entity = new Entity(i); priorityQueue.add(entity); try { // 为了将访问时间隔开 Thread.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } } // 最大容忍6个元素，元素满了后，执行LFU策略 LFUStrategy lfuStrategy = new LFUStrategy<>(priorityQueue, 6); // 对第一个元素进行访问 // lfuStrategy.get(1); lfuStrategy.add(new Entity(7)); } }
在上述代码中，如果我们不访问任何元素，直接执行 lfuStrategy.add(new Entity(7)),那么就会直接移除第一个元素，但是如果我们访问第一个元素，那么就会移除第二个元素。大家可以自己试验，我就不贴运行结果了，太占篇幅
链表实现
实现思路：相比于上一种实现方式，，这里最大的不同就是要自己去实现排序的过程。我们还是直接用JDK中的LinkedList，进行实现。
package com.study.spring.transaction.huancun; import lombok.Data; import lombok.RequiredArgsConstructor; import java.time.LocalDateTime; import java.util.Comparator; import java.util.LinkedList; /** * @author dmz * @date Create in 12:03 2019/8/11 */ @Data @AllArgsConstructor public class LFUStrategySecond<T extends Count> { private int max; private LinkedList<T> linkedList; public void add(T t) { if (linkedList.size() == max) { System.out.println("链表实现LFU策略删除元素：" + remove()); } linkedList.add(t); } public T remove() { return linkedList.removeFirst(); } public T get(int index) { T t = linkedList.get(index); t.addCount(); t.setLastVisitTime(LocalDateTime.now()); // 最小的放到链表头 linkedList.sort((Comparator<T>) (o1, o2) -> o1.getCount() == o2.getCount() ? o1.getLastVisitTime().compareTo(o2.getLastVisitTime()) : o1.getCount() - o2.getCount() ); return t; } } ackage com.study.spring.transaction.huancun; import java.util.LinkedList; /** * @author dmz * @date Create in 12:10 2019/8/11 */ public class MainSecond { public static void main(String[] args) { LinkedList<Entity> linkedList = new LinkedList<>(); linkedList.add(new Entity(1)); linkedList.add(new Entity(2)); linkedList.add(new Entity(3)); linkedList.add(new Entity(4)); linkedList.add(new Entity(5)); LFUStrategySecond<Entity> lfuStrategySecond = new LFUStrategySecond<Entity>(5, linkedList); // 可以观察，进行访问跟不进行访问，删除元素的区别 // lfuStrategySecond.get(0); lfuStrategySecond.add(new Entity(6)); } }
最近最少使用策略（LRU,Least Recently Used）
根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
实现思路：我们还是直接利用JDK的Linkedlist来进行实现，只要每次将被访问的元素置于链尾，若空间不够堆链头的数据进行删除即可。
package com.study.spring.transaction.huancun; import lombok.AllArgsConstructor; import lombok.Data; import java.util.LinkedList; /** * @author dmz * @date Create in 12:25 2019/8/11 */ @Data @AllArgsConstructor public class LRUStrategy<T> { // 不能小于1 int max; LinkedList<T> linkedList = new LinkedList<>(); public T get(int index) { // 每次获取元素时,将获取到的元素放到链尾 T t = linkedList.get(index); linkedList.remove(t); linkedList.addLast(t); return t; } public T remove() { return linkedList.removeFirst(); } public void add(T t) { if (linkedList.size() == max) { System.out.println("LRU删除的元素："+remove()); } linkedList.add(t); } }
总结：
到这里三种缓存过期策略我们就介绍完了，可能对于最后一种LRU算法介绍的不是很详细，本来是想自定义一个单链表来实现的，不过这两天写链表都写吐了，实在不想写了，偷了个懒，大家可以自己实现下，有任何问题都可以给我留言哦，一定会回复的！
/
