昨天面试被问到的缓存淘汰算法FIFOLRULFU及Java实现

　　缓存淘汰算法
　　在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。
　　第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。
　　但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。
　　常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。  FIFO
　　FIFO，First In First Out，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰。简单地说，先存入缓存的数据，先被淘汰。
　　最早存入缓存的数据，其不再被使用的可能性比刚存入缓存的可能性大。建立一个FIFO队列，记录所有在缓存中的数据。当一条数据被存入缓存时，就把它插在队尾上。需要被淘汰的数据一直在队列头。这种算法只是在按线性顺序访问数据时才是理想的，否则效率不高。因为那些常被访问的数据，往往在缓存中也停留得最久，结果它们却因变＂老＂而不得不被淘汰出去。
　　FIFO算法用队列实现就可以了，这里就不做代码实现了。  LRU
　　LRU，Least Recently Used，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰。简单地说，LRU 的淘汰规则是基于访问时间。
　　如果一个数据在最近一段时间没有被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当缓存空间满时，最久没有使用的数据最先被淘汰。
　　在Java中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造函数第三个参数传入true，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。  package one.more;  import java.util.LinkedHashMap; import java.util.Map;  public class LruCache extends LinkedHashMap {      /**      * 容量限制      */     private int capacity;      LruCache(int capacity) {         // 初始大小，0.75是装载因子，true是表示按照访问时间排序         super(capacity, 0.75f, true);         //缓存最大容量         this.capacity = capacity;     }      /**      * 重写removeEldestEntry方法，如果缓存满了，则把链表头部第一个节点和对应的数据删除。      */     @Override     protected boolean removeEldestEntry(Map.Entry eldest) {         return size() > capacity;     } }
　　我写一个简单的程序测试一下：  package one.more;  public class TestApp {      public static void main(String[] args) {         LruCache cache = new LruCache(3);         cache.put(＂keyA＂, ＂valueA＂);         System.out.println(＂put keyA＂);         System.out.println(cache);         System.out.println(＂=========================＂);          cache.put(＂keyB＂, ＂valueB＂);         System.out.println(＂put keyB＂);         System.out.println(cache);         System.out.println(＂=========================＂);          cache.put(＂keyC＂, ＂valueC＂);         System.out.println(＂put keyC＂);         System.out.println(cache);         System.out.println(＂=========================＂);          cache.get(＂keyA＂);         System.out.println(＂get keyA＂);         System.out.println(cache);         System.out.println(＂=========================＂);          cache.put(＂keyD＂, ＂valueD＂);         System.out.println(＂put keyD＂);         System.out.println(cache);     } }
　　运行结果如下：  put keyA {keyA=valueA} ========================= put keyB {keyA=valueA, keyB=valueB} ========================= put keyC {keyA=valueA, keyB=valueB, keyC=valueC} ========================= get keyA {keyB=valueB, keyC=valueC, keyA=valueA} ========================= put keyD {keyC=valueC, keyA=valueA, keyD=valueD}
　　当然，这个不是面试官想要的，也不是我们想要的。我们可以使用双向链表和哈希表进行实现，哈希表用于存储对应的数据，双向链表用于数据被使用的时间先后顺序。
　　在访问数据时，如果数据已存在缓存中，则把该数据的对应节点移到链表尾部。如此操作，在链表头部的节点则是最近最少使用的数据。
　　当需要添加新的数据到缓存时，如果该数据已存在缓存中，则把该数据对应的节点移到链表尾部；如果不存在，则新建一个对应的节点，放到链表尾部；如果缓存满了，则把链表头部第一个节点和对应的数据删除。  package one.more;  import java.util.HashMap; import java.util.Map;  public class LruCache {      /**      * 头结点      */     private Node head;     /**      * 尾结点      */     private Node tail;     /**      * 容量限制      */     private int capacity;     /**      * key和数据的映射      */     private Map map;      LruCache(int capacity) {         this.capacity = capacity;         this.map = new HashMap<>();     }      public V put(K key, V value) {         Node node = map.get(key);         // 数据存在，将节点移动到队尾         if (node != null) {             V oldValue = node.value;             //更新数据             node.value = value;             moveToTail(node);             return oldValue;         } else {             Node newNode = new Node(key, value);             // 数据不存在，判断链表是否满             if (map.size() == capacity) {                 // 如果满，则删除队首节点，更新哈希表                 map.remove(removeHead().key);             }             // 放入队尾节点             addToTail(newNode);             map.put(key, newNode);             return null;         }     }      public V get(K key) {         Node node = map.get(key);         if (node != null) {             moveToTail(node);             return node.value;         }         return null;     }      @Override     public String toString() {         StringBuilder sb = new StringBuilder();         sb.append(＂LruCache{＂);         Node curr = this.head;         while (curr != null) {             if(curr != this.head){                 sb.append(＂,＂).append(＂ ＂);             }             sb.append(curr.key);             sb.append(＂=＂);             sb.append(curr.value);             curr = curr.next;         }         return sb.append(＂}＂).toString();     }      private void addToTail(Node newNode) {         if (newNode == null) {             return;         }         if (head == null) {             head = newNode;             tail = newNode;         } else {             //连接新节点             tail.next = newNode;             newNode.pre = tail;             //更新尾节点指针为新节点             tail = newNode;         }     }      private void moveToTail(Node node) {         if (tail == node) {             return;         }         if (head == node) {             head = node.next;             head.pre = null;         } else {             //调整双向链表指针             node.pre.next = node.next;             node.next.pre = node.pre;         }         node.pre = tail;         node.next = null;         tail.next = node;         tail = node;     }      private Node removeHead() {         if (head == null) {             return null;         }         Node res = head;         if (head == tail) {             head = null;             tail = null;         } else {             head = res.next;             head.pre = null;             res.next = null;         }         return res;     }      class Node {         K key;         V value;         Node pre;         Node next;          Node(K key, V value) {             this.key = key;             this.value = value;         }     } }
　　再次运行测试程序，结果如下：  put keyA LruCache{keyA=valueA} ========================= put keyB LruCache{keyA=valueA, keyB=valueB} ========================= put keyC LruCache{keyA=valueA, keyB=valueB, keyC=valueC} ========================= get keyA LruCache{keyB=valueB, keyC=valueC, keyA=valueA} ========================= put keyD LruCache{keyC=valueC, keyA=valueA, keyD=valueD}LFU
　　LFU，Least Frequently Used，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰。简单地说，LFU 的淘汰规则是基于访问次数。
　　如果一个数据在最近一段时间很少被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当空间满时，最小频率使用的数据最先被淘汰。
　　我们可以使用双哈希表进行实现，一个哈希表用于存储对应的数据，另一个哈希表用于存储数据被使用次数和对应的数据。  package one.more;  import java.util.Comparator; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.stream.Collectors;  public class LfuCache {      /**      * 容量限制      */     private int capacity;      /**      * 当前最小使用次数      */     private int minUsedCount;      /**      * key和数据的映射      */     private Map map;     /**      * 数据频率和对应数据组成的链表      */     private Map> usedCountMap;      public LfuCache(int capacity) {         this.capacity = capacity;         this.minUsedCount = 1;         this.map = new HashMap<>();         this.usedCountMap = new HashMap<>();     }      public V get(K key) {          Node node = map.get(key);         if (node == null) {             return null;         }         // 增加数据的访问频率         addUsedCount(node);         return node.value;     }      public V put(K key, V value) {         Node node = map.get(key);         if (node != null) {             // 如果存在则增加该数据的访问频次             V oldValue = node.value;             node.value = value;             addUsedCount(node);             return oldValue;         } else {             // 数据不存在，判断链表是否满             if (map.size() == capacity) {                 // 如果满，则删除队首节点，更新哈希表                 List list = usedCountMap.get(minUsedCount);                 Node delNode = list.get(0);                 list.remove(delNode);                 map.remove(delNode.key);             }             // 新增数据并放到数据频率为1的数据链表中             Node newNode = new Node(key, value);             map.put(key, newNode);             List list = usedCountMap.get(1);             if (list == null) {                 list = new LinkedList<>();                 usedCountMap.put(1, list);             }              list.add(newNode);             minUsedCount = 1;             return null;         }     }      @Override     public String toString() {         StringBuilder sb = new StringBuilder();         sb.append(＂LfuCache{＂);         List usedCountList = this.usedCountMap.keySet().stream().collect(Collectors.toList());         usedCountList.sort(Comparator.comparingInt(i -> i));         int count = 0;         for (int usedCount : usedCountList) {             List list = this.usedCountMap.get(usedCount);             if (list == null) {                 continue;             }             for (Node node : list) {                 if (count > 0) {                     sb.append(＂,＂).append(＂ ＂);                 }                 sb.append(node.key);                 sb.append(＂=＂);                 sb.append(node.value);                 sb.append(＂(UsedCount:＂);                 sb.append(node.usedCount);                 sb.append(＂)＂);                 count++;             }         }         return sb.append(＂}＂).toString();     }      private void addUsedCount(Node node) {         List oldList = usedCountMap.get(node.usedCount);         oldList.remove(node);          // 更新最小数据频率         if (minUsedCount == node.usedCount && oldList.isEmpty()) {             minUsedCount++;         }          node.usedCount++;         List set = usedCountMap.get(node.usedCount);         if (set == null) {             set = new LinkedList<>();             usedCountMap.put(node.usedCount, set);         }         set.add(node);     }      class Node {          K key;         V value;         int usedCount = 1;          Node(K key, V value) {             this.key = key;             this.value = value;         }     } }
　　再次运行测试程序，结果如下：  put keyA LfuCache{keyA=valueA(UsedCount:1)} ========================= put keyB LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)} ========================= put keyC LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)} ========================= get keyA LfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)} ========================= put keyD LfuCache{keyC=valueC(UsedCount:1), keyD=valueD(UsedCount:1), keyA=valueA(UsedCount:2)}总结
　　看到这里，你已经超越了大多数人！  FIFO，First In First Out，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰，可以使用队列实现。  LRU，Least Recently Used，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰，可以使用双向链表和哈希表实现。  LFU，Least Frequently Used，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰，可以使用双哈希表实现。
　　原文链接：https://www.cnblogs.com/heihaozi/p/15944685.html?utm_source=tuicool&utm_medium=referral