java基础--自己动手实现一个LRU
作者：chenssy 发布时间：2023-06-25 18:21:04
标签：java,LRU
目录
LinkedHashMap 实现
继承 LinkedHashMap
组合 LinkedHashMap
链表 + HashMap 实现
LRU，即 Least Recently Use ，直译为 “最近最少使用”。它是根据数据的历史访问记录来进行数据淘汰的，淘汰掉最先访问的数据，其核心思想是 如果数据最近被访问过，那么将来被访问的几率也会更加高。
要实现 LRU，需要做到两点：
查询出最近最晚使用的项
给最近使用的项做一个标记
实现的方案有多种，这里小编主要介绍两种：
LinkedHashMap
双向链表 + HashMap
LinkedHashMap 实现
利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的，默认情况下是按照元素的添加顺序存储的，也可以调整为根据访问顺序来调整内部顺序（设置参数 accessOrder 进行调整），即最近读取的数据放在最前面，我们就是利用 LinkedHashMap 的这个特性来实现 LRU。先来一个简单的例子吧：
public static void main(String[] args){
Map<String,String> map = new LinkedHashMap(10,0.75f,true);
map.put("1","a");
map.put("2","b");
map.put("3","c");
map.put("4","d");
System.out.println("原始顺序为：");
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
System.out.println();
map.get("2");
System.out.println("访问 4 之后的顺序为：");
for(Iterator<Map.Entry<String,String>> it = map.entrySet().iterator();it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
}
运行结果：
原始顺序为：
1 2 3 4
访问 4 之后的顺序为：
1 3 4 2
LinkedHashMap 实现 LRU 有两种方式，一种是继承 LinkedHashMap，一种是利用组合的方式，下面分别演示这两种情况。
继承 LinkedHashMap
采用继承的方式实现起来是非常简单的，因为 LinkedHashMap 本身就已经具备了 LRU 的特性，我们只需要实现一点：当容器中元素个数超过我们设定的容量后，删除第一个元素即可。同时由于 LinkedHashMap 本身不具备线程安全，我们需要确保他线程安全，这个也很简单，重写 LinkedHashMap 的 get() 和 put() 方法即可，或者使用 Collections.synchronizedMap() 方法也可以。实现如下：
public class LRUCacheLinkedHashMap<K,V> extends LinkedHashMap<K,V> {
/**
* 定一缓存容量
*/
private int capacity;
LRUCacheLinkedHashMap(int capacity){
// AccessOrder = true
super(capacity,0.75f,true);
this.capacity = capacity;
}
/**
* 实现LRU的关键方法，如果 map 里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
*
* @param eldest
* @return
*/
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
@Override
public synchronized V get(Object key) {
return super.get(key);
}
@Override
public synchronized V put(K key, V value) {
return super.put(key, value);
}
}
验证
public static void main(String[] args){
LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(5);
cache.put("1","a");
cache.put("2","b");
cache.put("3","c");
cache.put("4","d");
cache.put("5","e");
System.out.println("插入 5 个元素后的顺序");
printlnCache(cache);
// 插入第 6 个元素
cache.put("6","e");
System.out.println("插入第 6 个元素后的顺序");
printlnCache(cache);
// 访问 第 3 个元素
cache.get("3");
System.out.println("访问元素 3 后的顺序");
printlnCache(cache);
}
private static void printlnCache(LRUCacheLinkedHashMap cacheMap){
for(Iterator<Map.Entry<String,String>> it = cacheMap.entrySet().iterator(); it.hasNext();){
System.out.print(it.next().getKey() + " ");
}
System.out.println();
}
运行结果：
插入 5 个元素后的顺序
1 2 3 4 5
插入第 6 个元素后的顺序
2 3 4 5 6
访问元素 3 后的顺序
2 4 5 6 3
运行结果完全符合我们的预期
组合 LinkedHashMap
使用组合的方式可能会更加优雅些，但是由于没有实现 Map 接口，所以就不能使用 Collections.synchronizedMap() 方式来保证线程安全性了，所以需要在每个方法处增加 synchronized 来确保线程安全。实现方式如下：
public class LRUCache<K,V> {
private int capacity;
private Map<K,V> cacheMap;
public LRUCache(int capacity){
this.capacity = capacity;
cacheMap = new LinkedHashMap<>(capacity,0.75f,true);
}
public synchronized void put(K k,V v){
cacheMap.put(k,v);
// 移除第一个元素
if(cacheMap.size() > capacity){
K first = this.keyIterator().next();
cacheMap.remove(first);
}
}
public synchronized V get(K k){
return cacheMap.get(k);
}
public Iterator<K> keyIterator(){
return cacheMap.keySet().iterator();
}
}
验证：
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(5);
lruCache.put("1","a");
lruCache.put("2","b");
lruCache.put("3","c");
lruCache.put("4","d");
lruCache.put("5","e");
System.out.println("插入 5 个元素后的顺序");
println(lruCache);
// 插入第 6 个元素
lruCache.put("6","e");
System.out.println("插入 第 6 个元素后的顺序");
println(lruCache);
// 访问 第 3 个元素
lruCache.get("3");
System.out.println("访问元素 3 后的顺序");
println(lruCache);
}
private static void println(LRUCache lruCache){
for(Iterator it = lruCache.keyIterator(); it.hasNext();){
System.out.print(it.next() + " ");
}
System.out.println();
}
运行结果如下：
插入 5 个元素后的顺序
1 2 3 4 5
插入 第 6 个元素后的顺序
2 3 4 5 6
访问元素 3 后的顺序
2 4 5 6 3
组合的方式也显得非常简单，有两点需要注意：
保证每个方法的线程安全
put 时，需要查看当前容量是否超过设置的容量，超过则需要删除第一个元素。当然小编这种是实现方式不是很优雅，这么做知识为了能够更加好阐述 LRU 的实现。更好的方案是在构造 LinkedHashMap 时，重写
removeEldestEntry(),如下：
cacheMap = new LinkedHashMap<K,V>(capacity,0.75f,true){
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size()>capacity;
}
};
链表 + HashMap 实现
我们想想，在不利用现存数据结构的条件（如 LinkedHashMap）如何实现一个 LRU 呢？缓存部分容易实现，我们都知道利用 HashMap 即可，但是如何实现缓存容量不足时丢弃最不常用的数据的功能？
利用时间戳。每一个访问，增加的元素我们都给其更新一个时间戳，在 put 的时候，检查，删除时间戳最小的就可以了。这种方法可以实现，但是代价较高，就是我们需要遍历整个数据，得到最小的时间戳。
我们可以换位思考，我们其实不需要关注每个节点的增加或者遍历时间，我们只需要知道那个节点是最先访问就可以了，所以我们可以利用链表记录访问记录，有新数据加入时放在链表的 head 节点，每次访问也将该数据放在 head 节点，那么链表的 tail 一定是最早访问的节点，所以每次当容量不足的时候删除 tail 节点数据并将它的前驱节点设置为 tail 就可以了。注意，这个链表是一个双向链表。代码如下：
public class LinkedLRUCache<K,V> {
private int capacity;
private Map<K,LRUNode> map;
private LRUNode head;
private LRUNode tail;
LinkedLRUCache(int capacity){
this.capacity = capacity;
this.map = new HashMap<>();
}
public synchronized void put(K k,V v){
LRUNode node = map.get(k);
// 存在该 key，将节点的设置为 head
if(node != null){
node.value = v;
remove(node,false);
}else{
/**
* 该节点不存在
* 1、将该节点加入缓存
* 2、设置该节点为 head
* 3、判断是否超出容量
*/
node = new LRUNode(k,v);
if(map.size() >= capacity){
//删除 tail 节点
remove(tail,true);
}
map.put(k,node);
setHead(node);
}
// 设置当前节点为首节点
setHead(node);
}
public Object get(String key) {
LRUNode node = map.get(key);
if (node != null) {
// 将刚操作的元素放到head
remove(node, false);
setHead(node);
return node.value;
}
return null;
}
/**
* 设置头结点
*
* @param node
*/
private void setHead(LRUNode node) {
if(head != null){
node.next = head;
head.prev = node;
}
head = node;
if(tail == null){
tail = node;
}
}
/**
* 从链表中删除此Node
*
* @param node
* @param flag 为 true 就删除该节点的 key
*/
private void remove(LRUNode node,boolean flag) {
if (node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if (node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
node.next = null;
node.prev = null;
if (flag) {
map.remove(node.key);
}
}
private Iterator iterator(){
return map.keySet().iterator();
}
private class LRUNode<K,V> {
/**
* cache 的 key
*/
private K key;
/**
* cache 的 value
*/
private V value;
private LRUNode next;
private LRUNode prev;
LRUNode(K key, V value) {
this.key = key;
this.value = value;
}
}
}
验证
public static void main(String[] args){
LRUCache lruCache = new LRUCache(5);
lruCache.put("1","a");
lruCache.put("2","b");
lruCache.put("3","c");
lruCache.put("4","d");
lruCache.put("5","e");
System.out.println("插入 5 个元素");
println(lruCache);
System.out.println("插入 3 元素");
lruCache.put("3","c");
println(lruCache);
System.out.println("插入第 6 个元素");
lruCache.put("6","f");
println(lruCache);
System.out.println("访问 4 元素");
lruCache.get("4");
println(lruCache);
}
private static void println(LRUCache lruCache){
Iterator iterator = lruCache.keyIterator();
while (iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
System.out.println();
}
执行结果：
插入 5 个元素
1 2 3 4 5
插入 3 元素
1 2 4 5 3
插入第 6 个元素
2 4 5 3 6
访问 4 元素
2 5 3 6 4
来源：https://www.cnblogs.com/chenssy/p/15164873.html
0
投稿猜你喜欢
- JAVA简单写学生信息管理系统，实现学生信息的输入、查询、修改、删除操作package Week;import jdk.internal.u
本Demo为练手小项目，主要是熟悉目前主流APP的架构模式.此项目中采用MVC设计模式,纯代码和少许XIB方式实现.主要实现了朋友圈功能和摇- Java泛型映射不同的值类型详解前言：一般来说，开发人员偶尔会遇到这样的情形： 在一个特定容器中映射任意类型的值。然而Java 集合API只
- [LeetCode] 159. Longest Substring with At Most Two Distinct Characters
- 1、动态SQL片段通过SQL片段达到代码复用 <!-- 动态条件分页查询 --> <sql i
- 工厂方法模式的定义工厂方法(Factory Method)模式的意义是定义一个创建产品对象的工厂接口，将实际创建工作推迟到子类当中。核心工厂
- 一、SpringCache介绍Spring Cache 是一个优秀的缓存组件。自Spring 3.1起，提供了类似于@Transaction
- 1.首先，八种基本数据类型分别是：int、short、float、double、long、boolean、byte、char； &
- 目录简介强引用软引用弱引用虚引用简介从JDK1.2版本开始，把对象的引用分为四种级别，从而使程序能更加灵活的控制对象的生命周期。这四种级别由
- 判断参数是否为空并作为查询条件@Override public Page<DemandEntity>
- Timer 详解Timer 和 TimerTask 用于在后台线程中调度任务的 java.
- 本文介绍了JAVA中实现原生的 socket 通信机制原理，分享给大家，具体如下：当前环境jdk == 1.8知识点socket 的连接处理
- 本文是一个 Spring 扩展支持 SPEL 的简单模式，方便第三方通过 Spring 提供额外功能。简化版方式这种方式可以在任何能获取Ap
- Spring Security中的内置过滤器顺序是怎么维护的?我想很多开发者都对这个问题感兴趣。本篇我和大家一起探讨下这个问题。HttpSe
- 栈栈（stack）又名堆栈，它是一种运算受限的线性表 。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
- 我们在学习接口的时候。能够在里面做一些方法的调用。不过今天所要讲的JDBC，虽然也是连接数据库的一种接口，不过与类接口有着很大的区别，大家要
- 话不多说，请看代码：package com.lxj.demo;import java.io.BufferedReader;import ja
- 数组的长度是固定的，无法适应数据变化的需求。为了解决这个问题，Java提供了另一个容器 java.util.ArrayList集合类,让我们
- 本文实例讲述了Android+SQLite数据库实现的生词记事本功能。分享给大家供大家参考，具体如下：主activity命名为Dict：代码
- 在网站开发中经常遇到级联数据的展示，比如选择城市的时候弹出的省市县选择界面。很多前端制作人员习惯于从JSON中而不是从数据库中获
