java编程
搜索
分类

Java实现常用缓存淘汰算法:FIFO、LRU、LFU

作者：万猫学社 时间：2022-08-26 21:45:19　

缓存淘汰算法

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

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

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

常用的缓存淘汰算法有：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<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 = 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<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 = 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 = 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)}

来源：https://blog.csdn.net/heihaozi/article/details/122058465

标签：Java,缓存淘汰算法,FIFO,LRU,LFU
0
投稿

猜你喜欢

  • springboot vue组件开发实现接口断言功能

    2023-11-12 10:26:53

  • SpringBoot打包发布到linux上（centos 7）的步骤

    2023-08-11 06:35:55

  • Java五种方式实现多线程循环打印问题

    2023-03-07 20:34:12

  • Android中获取资源 id 及资源 id 的动态获取

    2023-06-30 04:38:06

  • SpringBoot之如何指定配置文件启动

    2023-11-17 15:17:48

  • Java实现显示指定类型的文件

    2021-10-26 11:30:37

  • Mybatis结果生成键值对的实例代码

    2023-11-28 15:50:58

  • JAVA中数组从小到大排序的2种方法实例

    2021-10-09 09:46:18

  • flutter实现倒计时加载页面

    2023-08-18 23:30:09

  • Java并发编程之原子性-Atomic的使用

    2023-11-09 22:34:58

  • JAVA JVM面试题总结

    2021-07-12 04:55:13

  • Java 实战范例之线上婚纱摄影预定系统的实现

    2021-08-08 14:19:42

  • flutter中的资源和图片加载示例详解

    2023-08-24 13:19:39

  • 解读Spring-boot的debug调试

    2022-06-09 15:04:06

  • 网易Java程序员两轮面试 请问你能答对几个?

    2023-11-29 10:32:08

  • Java SSH 秘钥连接mysql数据库的方法

    2022-07-11 21:23:18

  • Java实现FTP上传与下载功能

    2021-09-22 18:28:51

  • Java面试题冲刺第二十三天--分布式

    2023-09-24 07:30:43

  • SpringBoot如何使用Fastjson解析Json数据

    2023-11-25 11:55:58

  • Java IO流—异常及捕获异常处理 try…catch…finally

    2023-03-14 07:35:52
    • asp之家 软件编程 m.aspxhome.com