0
0

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

缓存淘汰算法

在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。

第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。

但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。

常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。

FIFO

FIFO，First In First Out，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰。简单地说，先存入缓存的数据，先被淘汰。

最早存入缓存的数据，其不再被使用的可能性比刚存入缓存的可能性大。建立一个FIFO队列，记录所有在缓存中的数据。当一条数据被存入缓存时，就把它插在队尾上。需要被淘汰的数据一直在队列头。这种算法只是在按线性顺序访问数据时才是理想的，否则效率不高。因为那些常被访问的数据，往往在缓存中也停留得最久，结果它们却因变“老”而不得不被淘汰出去。

FIFO算法用队列实现就可以了，这里就不做代码实现了。

LRU

LRU，Least Recently Used，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰。简单地说，LRU 的淘汰规则是基于访问时间。

如果一个数据在最近一段时间没有被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当缓存空间满时，最久没有使用的数据最先被淘汰。

在Java中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造函数第三个参数传入true，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。

  1. packageone.more;importjava.util.LinkedHashMap;importjava.util.Map;publicclassLruCache<K,V>extendsLinkedHashMap<K,V>{/**
  2.      * 容量限制
  3.      */privateint capacity;LruCache(int capacity){// 初始大小，0.75是装载因子，true是表示按照访问时间排序super(capacity,0.75f,true);//缓存最大容量this.capacity = capacity;}/**
  4.      * 重写removeEldestEntry方法，如果缓存满了，则把链表头部第一个节点和对应的数据删除。
  5.      */@OverrideprotectedbooleanremoveEldestEntry(Map.Entry<K,V> eldest){returnsize()> capacity;}}

我写一个简单的程序测试一下：

  1. packageone.more;publicclassTestApp{publicstaticvoidmain(String[] args){LruCache<String,String> cache =newLruCache(3);
  2.         cache.put("keyA","valueA");System.out.println("put keyA");System.out.println(cache);System.out.println("=========================");
  4.         cache.put("keyB","valueB");System.out.println("put keyB");System.out.println(cache);System.out.println("=========================");
  6.         cache.put("keyC","valueC");System.out.println("put keyC");System.out.println(cache);System.out.println("=========================");
  8.         cache.get("keyA");System.out.println("get keyA");System.out.println(cache);System.out.println("=========================");
  10.         cache.put("keyD","valueD");System.out.println("put keyD");System.out.println(cache);}}

运行结果如下：

  1. put keyA
  2. {keyA=valueA}
  3. =========================
  4. put keyB
  5. {keyA=valueA, keyB=valueB}
  6. =========================
  7. put keyC
  8. {keyA=valueA, keyB=valueB, keyC=valueC}
  9. =========================
  10. get keyA
  11. {keyB=valueB, keyC=valueC, keyA=valueA}
  12. =========================
  13. put keyD
  14. {keyC=valueC, keyA=valueA, keyD=valueD}

当然，这个不是面试官想要的，也不是我们想要的。我们可以使用双向链表和哈希表进行实现，哈希表用于存储对应的数据，双向链表用于数据被使用的时间先后顺序。

在访问数据时，如果数据已存在缓存中，则把该数据的对应节点移到链表尾部。如此操作，在链表头部的节点则是最近最少使用的数据。

当需要添加新的数据到缓存时，如果该数据已存在缓存中，则把该数据对应的节点移到链表尾部；如果不存在，则新建一个对应的节点，放到链表尾部；如果缓存满了，则把链表头部第一个节点和对应的数据删除。

  1. packageone.more;importjava.util.HashMap;importjava.util.Map;publicclassLruCache<K,V>{/**
  2.      * 头结点
  3.      */privateNode head;/**
  4.      * 尾结点
  5.      */privateNode tail;/**
  6.      * 容量限制
  7.      */privateint capacity;/**
  8.      * key和数据的映射
  9.      */privateMap<K,Node> map;LruCache(int capacity){this.capacity = capacity;this.map =newHashMap<>();}publicVput(K key,V value){Node node = map.get(key);// 数据存在，将节点移动到队尾if(node !=null){V oldValue = node.value;//更新数据
  10.             node.value = value;moveToTail(node);return oldValue;}else{Node newNode =newNode(key, value);// 数据不存在，判断链表是否满if(map.size()== capacity){// 如果满，则删除队首节点，更新哈希表
  11.                 map.remove(removeHead().key);}// 放入队尾节点addToTail(newNode);
  12.             map.put(key, newNode);returnnull;}}publicVget(K key){Node node = map.get(key);if(node !=null){moveToTail(node);return node.value;}returnnull;}@OverridepublicStringtoString(){StringBuilder sb =newStringBuilder();
  13.         sb.append("LruCache{");Node curr =this.head;while(curr !=null){if(curr !=this.head){
  14.                 sb.append(',').append(' ');}
  15.             sb.append(curr.key);
  16.             sb.append('=');
  17.             sb.append(curr.value);
  18.             curr = curr.next;}return sb.append('}').toString();}privatevoidaddToTail(Node newNode){if(newNode ==null){return;}if(head ==null){
  19.             head = newNode;
  20.             tail = newNode;}else{//连接新节点
  21.             tail.next = newNode;
  22.             newNode.pre = tail;//更新尾节点指针为新节点
  23.             tail = newNode;}}privatevoidmoveToTail(Node node){if(tail == node){return;}if(head == node){
  24.             head = node.next;
  25.             head.pre =null;}else{//调整双向链表指针
  26.             node.pre.next = node.next;
  27.             node.next.pre = node.pre;}
  28.         node.pre = tail;
  29.         node.next =null;
  30.         tail.next = node;
  31.         tail = node;}privateNoderemoveHead(){if(head ==null){returnnull;}Node res = head;if(head == tail){
  32.             head =null;
  33.             tail =null;}else{
  34.             head = res.next;
  35.             head.pre =null;
  36.             res.next =null;}return res;}classNode{K key;V value;Node pre;Node next;Node(K key,V value){this.key = key;this.value = value;}}}

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

  1. put keyA
  2. LruCache{keyA=valueA}
  3. =========================
  4. put keyB
  5. LruCache{keyA=valueA, keyB=valueB}
  6. =========================
  7. put keyC
  8. LruCache{keyA=valueA, keyB=valueB, keyC=valueC}
  9. =========================
  10. get keyA
  11. LruCache{keyB=valueB, keyC=valueC, keyA=valueA}
  12. =========================
  13. put keyD
  14. LruCache{keyC=valueC, keyA=valueA, keyD=valueD}

LFU

LFU，Least Frequently Used，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰。简单地说，LFU 的淘汰规则是基于访问次数。

如果一个数据在最近一段时间很少被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当空间满时，最小频率使用的数据最先被淘汰。

我们可以使用双哈希表进行实现，一个哈希表用于存储对应的数据，另一个哈希表用于存储数据被使用次数和对应的数据。

  1. packageone.more;importjava.util.Comparator;importjava.util.HashMap;importjava.util.LinkedList;importjava.util.List;importjava.util.Map;importjava.util.stream.Collectors;publicclassLfuCache<K,V>{/**
  2.      * 容量限制
  3.      */privateint capacity;/**
  4.      * 当前最小使用次数
  5.      */privateint minUsedCount;/**
  6.      * key和数据的映射
  7.      */privateMap<K,Node> map;/**
  8.      * 数据频率和对应数据组成的链表
  9.      */privateMap<Integer,List<Node>> usedCountMap;publicLfuCache(int capacity){this.capacity = capacity;this.minUsedCount =1;this.map =newHashMap<>();this.usedCountMap =newHashMap<>();}publicVget(K key){Node node = map.get(key);if(node ==null){returnnull;}// 增加数据的访问频率addUsedCount(node);return node.value;}publicVput(K key,V value){Node node = map.get(key);if(node !=null){// 如果存在则增加该数据的访问频次V oldValue = node.value;
  10.             node.value = value;addUsedCount(node);return oldValue;}else{// 数据不存在，判断链表是否满if(map.size()== capacity){// 如果满，则删除队首节点，更新哈希表List<Node> list = usedCountMap.get(minUsedCount);Node delNode = list.get(0);
  11.                 list.remove(delNode);
  12.                 map.remove(delNode.key);}// 新增数据并放到数据频率为1的数据链表中Node newNode =newNode(key, value);
  13.             map.put(key, newNode);List<Node> list = usedCountMap.get(1);if(list ==null){
  14.                 list =newLinkedList<>();
  15.                 usedCountMap.put(1, list);}
  17.             list.add(newNode);
  18.             minUsedCount =1;returnnull;}}@OverridepublicStringtoString(){StringBuilder sb =newStringBuilder();
  19.         sb.append("LfuCache{");List<Integer> usedCountList =this.usedCountMap.keySet().stream().collect(Collectors.toList());
  20.         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){
  21.                     sb.append(',').append(' ');}
  22.                 sb.append(node.key);
  23.                 sb.append('=');
  24.                 sb.append(node.value);
  25.                 sb.append("(UsedCount:");
  26.                 sb.append(node.usedCount);
  27.                 sb.append(')');
  28.                 count++;}}return sb.append('}').toString();}privatevoidaddUsedCount(Node node){List<Node> oldList = usedCountMap.get(node.usedCount);
  29.         oldList.remove(node);// 更新最小数据频率if(minUsedCount == node.usedCount && oldList.isEmpty()){
  30.             minUsedCount++;}
  32.         node.usedCount++;List<Node> set = usedCountMap.get(node.usedCount);if(set ==null){
  33.             set =newLinkedList<>();
  34.             usedCountMap.put(node.usedCount, set);}
  35.         set.add(node);}classNode{K key;V value;int usedCount =1;Node(K key,V value){this.key = key;this.value = value;}}}

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

  1. put keyA
  2. LfuCache{keyA=valueA(UsedCount:1)}
  3. =========================
  4. put keyB
  5. LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)}
  6. =========================
  7. put keyC
  8. LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)}
  9. =========================
  10. get keyA
  11. LfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)}
  12. =========================
  13. put keyD
  14. 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，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰，可以使用双哈希表实现。
标签： 缓存 java 面试
本文转载自: https://blog.csdn.net/heihaozi/article/details/122058465
版权归原作者 万猫学社 所有， 如有侵权，请联系我们删除。
登录后发布评论

“昨天面试被问到的 缓存淘汰算法FIFO、LRU、LFU及Java实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航
没有找到文章内容分段。。。