昨天面试今天问结果昨天面试被问到的缓存淘汰算法FIFO、LRU、LFU及Java实现

在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。缓存淘汰算法在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。
第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。
但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。
常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。
FIFOFIFO，First In First Out，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰。简单地说，先存入缓存的数据，先被淘汰。
最早存入缓存的数据，其不再被使用的可能性比刚存入缓存的可能性大。建立一个FIFO队列，记录所有在缓存中的数据。当一条数据被存入缓存时，就把它插在队尾上。需要被淘汰的数据一直在队列头。这种算法只是在按线性顺序访问数据时才是理想的，否则效率不高。因为那些常被访问的数据，往往在缓存中也停留得最久，结果它们却因变“老”而不得不被淘汰出去。
FIFO算法用队列实现就可以了，这里就不做代码实现了。
LRULRU，Least Recently Used，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰。简单地说，LRU 的淘汰规则是基于访问时间。
如果一个数据在最近一段时间没有被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当缓存空间满时，最久没有使用的数据最先被淘汰。
在Java中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造函数第三个参数传入true，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。
package one.more;import java.util.LinkedHashMap;import java.util.Map;public class LruCache<K, V> extends LinkedHashMap<K, V> {/*** 容量限制*/private int capacity;LruCache(int capacity) {// 初始大小，0.75是装载因子，true是表示按照访问时间排序super(capacity, 0.75f, true);//缓存最大容量this.capacity = capacity;}/*** 重写removeEldestEntry方法，如果缓存满了，则把链表头部第一个节点和对应的数据删除。*/@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}}我写一个简单的程序测试一下：
package one.more;public class TestApp {public static void main(String[] args) {LruCache<String, String> 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<K, V> {/*** 头结点*/private Node head;/*** 尾结点*/private Node tail;/*** 容量限制*/private int capacity;/*** key和数据的映射*/private Map<K, Node> 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 = https://tazarkount.com/read/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;}@Overridepublic 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 = https://tazarkount.com/read/value;}}}再次运行测试程序，结果如下：
put keyALruCache{keyA=valueA}=========================put keyBLruCache{keyA=valueA, keyB=valueB}=========================put keyCLruCache{keyA=valueA, keyB=valueB, keyC=valueC}=========================get keyALruCache{keyB=valueB, keyC=valueC, keyA=valueA}=========================put keyDLruCache{keyC=valueC, keyA=valueA, keyD=valueD}LFULFU，Least Frequently Used，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰。简单地说，LFU 的淘汰规则是基于访问次数。
【昨天面试今天问结果昨天面试被问到的缓存淘汰算法FIFO、LRU、LFU及Java实现】如果一个数据在最近一段时间很少被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当空间满时，最小频率使用的数据最先被淘汰。
我们可以使用双哈希表进行实现，一个哈希表用于存储对应的数据，另一个哈希表用于存储数据被使用次数和对应的数据。
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<K, V> {/*** 容量限制*/private int capacity;/*** 当前最小使用次数*/private int minUsedCount;/*** key和数据的映射*/private Map<K, Node> map;/*** 数据频率和对应数据组成的链表*/private Map<Integer, List<Node>> 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 = https://tazarkount.com/read/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;}}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append("LfuCache{");List<Integer> usedCountList = this.usedCountMap.keySet().stream().collect(Collectors.toList());usedCountList.sort(Comparator.comparingInt(i -> i));int count = 0;for (int usedCount : usedCountList) {List<Node> 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<Node> oldList = usedCountMap.get(node.usedCount);oldList.remove(node);// 更新最小数据频率if (minUsedCount == node.usedCount && oldList.isEmpty()) {minUsedCount++;}node.usedCount++;List<Node> 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 = https://tazarkount.com/read/value;}}}再次运行测试程序，结果如下：
put keyALfuCache{keyA=valueA(UsedCount:1)}=========================put keyBLfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)}=========================put keyCLfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)}=========================get keyALfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)}=========================put keyDLfuCache{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，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰，可以使用双哈希表实现。

竟然已经看到这里了，你我定是有缘人，留下你的点赞和关注，他日必成大器。
微信公众号：万猫学社
微信扫描二维码
关注后回复「电子书」
获取12本Java必读技术书籍

昨天面试今天问结果昨天面试被问到的缓存淘汰算法FIFO、LRU、LFU及Java实现

文章插图

文章插图
作者：万猫学社
出处：http://www.cnblogs.com/heihaozi/
版权声明：本文遵循 CC 4.0 BY-NC-SA 版权协议，转载请附上原文出处链接和本声明。
微信扫描二维码，关注万猫学社，回复「电子书」，免费获取12本Java必读技术书籍。

昨天面试今天问结果 昨天面试被问到的 缓存淘汰算法FIFO、LRU、LFU及Java实现

昨天面试今天问结果昨天面试被问到的缓存淘汰算法FIFO、LRU、LFU及Java实现