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
0
投稿猜你喜欢
- android在设计View类时，为了能储存一些辅助信息，设计一个一个setTag/getTag的方法。这让我想起在Winform设计中每个
- 只需要在控件TextBox的keypress事件中写入如下代码即可满足要求：代码如下：if (e.KeyChar == '.'
1. 编写索引内容节点解释：settings：配置信息"number_of_replicas": 0 不需要备份（单节点- 前言本文的多租户是基于多数据库进行实现的，数据是通过不同数据库进行隔离。下面话不多说，来看看详细的介绍：MyCat 基本配置首先针对多租户配
- 全面总结Android Service的使用方法，具体内容如下1、Service的种类按运行地点分类：其实remote服务还是很少见的，并且
- 前言这几天听朋友说JPA很好用，根本不用写sql。我在想一个程序员不写sql还能叫程序员？而且越高级的工具封装越多的工具，可拓展性和效率就非
- 在项目中使用Maven管理jar包依赖，往往会出现以下状况：1、国内访问maven默认远程中央镜像特别慢；2、使用阿里的镜像替代远程中央镜像
- 最近开发过过成中遇到一些小问题，比如一个btn点击用户可能只点击了一次但是后台响应了多次，像一些表单的提交出现这种问题比较棘手，当然解决这种
- Collection继承、实现关系如下(说明(I)表示接口， (C)表示Java类，<--表示继承，<<——表示实现)：(
- 在开发中，我们通常需要将从数据库中查询的集合数据转换成类似文件系统一样的树形集合，比如：省市单位，部门机构，书籍分类等TreeNode对象@
- 前言最近我跟自定义View杠上了，甚至说有点上瘾到走火入魔了。身为菜鸟的我自然要查阅大量的资料，学习大神们的代码，这不，前两天正好在郭神在微
- 首先说一下最近自己遇到的一个坑：@Transactionalservice A（）{try{insert();serviceB.update
- 目录开启定时任务注解@EnableScheduling@Scheduled添加定时任务Cron表达式在线cron工具适应场景springBo
- 抽象类1.引出抽象类向上转型带来的最大的好处就是参数统一化，使用共同的父类引用，就可以接收所有的子类实例。多态非常依赖方法覆写，但是子类可以
- 一、Monkey 是什么？Monkey 就是SDK中附带的一个工具。二、Monkey 测试的目的？:该工具用于进行压力测试。 然后开发人员结
- 作者：精致码农出处：http://cnblogs.com/willick联系：liam.wang@live.com最近工作中遇到一个这样的需
- 本文实例讲述了Android手机获取root权限并实现关机重启功能的方法，是Android程序设计中非常常见的重要功能。现分享给大家，供大家
- MyBatis缓存我们知道，频繁的数据库操作是非常耗费性能的（主要是因为对于DB而言，数据是持久化在磁盘中的，因此查询操作需要通过IO，IO
- 原子数组原子数组有AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray，主要是用来
- 在早期开发的时候，我们完成的都是静态页面也就是html页面，随着时间轴的发展，慢慢的引入了jsp页面，当在后端服务查询到数据之后可以转发到j
