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

知识的价值不在于占有，而在于使用。这篇文章主要讲述昨天面试被问到的缓存淘汰算法FIFOLRULFU及Java实现相关的知识，希望能为你提供帮助。
缓存淘汰算法
在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。
第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。
但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。

文章图片

常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。
FIFO
【昨天面试被问到的缓存淘汰算法FIFOLRULFU及Java实现】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< K, V> extends LinkedHashMap< K, V> /** * 容量限制 */ private int capacity; LruCache(int capacity) // 初始大小，0.75是装载因子，true是表示按照访问时间排序 super(capacity, 0.75f, true); //缓存最大容量 this.capacity = capacity; /** * 重写removeEldestEntry方法，如果缓存满了，则把链表头部第一个节点和对应的数据删除。 */ @Override protected 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://www.songbingjia.com/android/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 = https://www.songbingjia.com/android/value;

再次运行测试程序，结果如下：

put keyA LruCachekeyA=valueA ========================= put keyB LruCachekeyA=valueA, keyB=valueB ========================= put keyC LruCachekeyA=valueA, keyB=valueB, keyC=valueC ========================= get keyA LruCachekeyB=valueB, keyC=valueC, keyA=valueA ========================= put keyD LruCachekeyC=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< 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://www.songbingjia.com/android/node.value; node.value = value; addUsedCount(node); return oldValue; else // 数据不存在，判断链表是否满 if (map.size() == capacity) // 如果满，则删除队首节点，更新哈希表 List< Node> 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< Node> 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< 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://www.songbingjia.com/android/value;

再次运行测试程序，结果如下：

put keyA LfuCachekeyA=valueA(UsedCount:1) ========================= put keyB LfuCachekeyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1) ========================= put keyC LfuCachekeyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1) ========================= get keyA LfuCachekeyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2) ========================= put keyD LfuCachekeyC=valueC(UsedCount:1), keyD=valueD(UsedCount:1), keyA=valueA(UsedCount:2)

总结
看到这里，你已经超越了大多数人！