程序地带

LRU算法详解(java代码实现)


 
一、算法背景

最近最少使用算法(LRU)是⼀种缓存淘汰策略,它是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是,发生缺页中断时,选择未使用时间最长的页面置换出去。 从程序运行的原理来看,最近最少使用算法是比较接近理想的一种页面置换算法,这种算法既充分利用了内存中页面调用的历史信息,又正确反映了程序的局部问题。如下图所示:



 利用 LRU 算法对上例进行页面置换的结果如上图所示。当进程第一次对页面 2 进行访问时,由于页面 7 是最近最久未被访问的,故将它置换出去。当进程第一次对页面 3进行访问时,第 1 页成为最近最久未使用的页,将它换出。


二、数据结构

 ⾸先要接收⼀个参数作为缓存的最⼤容量, 然后实现两个 API, ⼀个是 put(key, val) ⽅法存⼊键值对, 另⼀个是 get(key) ⽅法获取 key 对应的 val, 如果 key 不存在则返回null。get 和 put ⽅法必须都是 O(1) 的时间复杂度,要让 put 和 get ⽅法的时间复杂度为 O(1), 我们可以总结出 cache 这个数据结构必要的条件: 查找快, 插⼊快, 删除快, 有顺序之分。那么, 什么数据结构同时符合上述条件呢? 哈希表查找快, 但是数据⽆固定顺序; 链表有顺序之分, 插⼊删除快, 但是查找慢。 所以结合⼀下, 形成⼀种新的数据结构: 哈希链表。如下图所示:



对LRU算法实现有一原则:对于新插入的元素或者最新查询的元素要放到链表的头部,对于长时间未访问的元素要放到链表尾部。所以每次插入或者查询都需要维护链表中元素的顺序。


使用哈希表的原因是查询时间复杂度为O(1),使用双向链表的原因是对于删除和插入操作时间复杂度为O(1)。


其中哈希表中存储的key为K,value为Node<K,V>的引用,双向链表存储的元素为Node<K,V>的引用,哈希表和双向链表的数据结构如下代码所示:


/**
* 通过与链表配合,使其查找速度在O(1)下完成
*/
private Map<K,Node<K,V>> map;
/**
* 链表优点:便于添加和删除元素,都在O(1)时间内完成
*/
private LinkedList<Node<K,V>> linkedList;

  Node<K,V>它是一个静态的内部类,数据结构如下所示:


private static class Node<K,V>{
/**
* 键
*/
K key;
/**
* 值
*/
V value;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "(" +
"key=" + key +
", value=" + value +
')';
}
}

put 方法是线程安全方法,定义如下所示


public synchronized void put(K key,V value)

对于put操作,首先判断缓存元素是否存在,如果存在,则把链表中的元素删除,map中的数据不用删除,再在链表头部插入元素,并更新map,直接返回即可 ;当缓存没有满的话,直接把元素插入链表的表头,否则移除表尾元素(最旧未访问元素),在插入表头后,注意更新map。


get 方法是线程安全方法,定义如下所示


public synchronized V get(K key)

对于get操作首先要判断map中是否存在,如果存在则把该节点删除并在链表头部插入该元素并更新map 返回当前元素即可,如果map不存在 则直接返回null;


三、代码实现
LruCache.java内容如下所示:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
/**
* @author: hh
* @date: 2021/1/15 14:33
* @description: lru算法,线程安全
*/
public class LruCache<K,V> {
/**
* 通过与链表配合,使其查找速度在O(1)下完成
*/
private Map<K,Node<K,V>> map;
/**
* 链表优点:便于添加和删除元素,都在O(1)时间内完成
*/
private LinkedList<Node<K,V>> linkedList;
/**
* 缓存存储元素的数量
*/
private int size;
private int defaultSize = 16;
public LruCache() {
this(16);
}
public LruCache(int size) {
if(size <= 0){
this.size = 16;
}else {
this.size = size;
}
this.map = new HashMap<>(this.size);
this.linkedList = new LinkedList<>();
}
/**
* 判断缓存元素是否存在,如果存在,则把链表中的元素删除,map中的数据不用删除,再在链表头部插入元素,并更新map
* 当缓存没有满的话,直接把元素插入链表的表头,否则移除表尾元素(最旧未访问元素),在插入表头,注意更新map
*
* @param key : 键
* @param value :值
*/
public synchronized void put(K key,V value){
//待添加元素
Node<K,V> insertNode = new Node<>(key, value);
//判断元素是否存在
Node<K,V> node = map.get(key);
//如果存在,则把链表中的元素删除,map中的数据不用删除,再在链表头部插入元素
if(Objects.nonNull(node)){
linkedList.remove(node);
linkedList.addFirst(insertNode);
//更新map中的相应value
map.put(key,insertNode);
return;
}
//如果缓存已经满的话,则删除最后未访问元素
if(this.size == map.size()){
//直接删除队列尾部元素,同时更新map
linkedList.removeLast();
map.remove(key);
//在队列头部插入元素,同时更新map
linkedList.addFirst(insertNode);
map.put(key,insertNode);
return;
}
//如果缓存没满,则执行添加即可
map.put(key,insertNode);
linkedList.addFirst(insertNode);
}
/**
* 如果key存在,则返回相应value值,否者返回null
*
* @param key :键
* @return :值
*/
public synchronized V get(K key){
//先向map查询是否存在
Node<K,V> node = map.get(key);
if(Objects.isNull(node)){
return null;
}
//如果存在,则先删除后添加到队列头
linkedList.remove(node);
linkedList.addFirst(node);
return node.value;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for(Node<K,V> node : linkedList ){
stringBuilder.append(node.toString()).append(",");
}
return stringBuilder.toString().substring(0,stringBuilder.length()-1);
}
/**
* 根据key删除缓存元素
*
* @param key : 主键
*/
private void delete(K key){
//判断是否存在相应元素
Node<K,V> node = map.get(key);
//如果元素进行存在则进行删除
if(Objects.nonNull(node)){
linkedList.remove(node);
}
}
private static class Node<K,V>{
/**
* 键
*/
K key;
/**
* 值
*/
V value;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "(" +
"key=" + key +
", value=" + value +
')';
}
}
}
LruCacheTest.java内容如下所示:
public class LruCacheTest {
public static void main(String[] args){
LruCache<String,String> lruCache = new LruCache<>(3);
lruCache.put("one","one");
lruCache.put("two","two");
lruCache.put("three","three");
System.out.println(lruCache.toString());
lruCache.get("one");
System.out.println(lruCache.toString());
lruCache.put("four","four");
System.out.println(lruCache.toString());
lruCache.get("one");
System.out.println(lruCache.toString());
System.out.println(lruCache.get("five"));
lruCache.put("four","five");
System.out.println(lruCache.toString());
}
}

执行结果如下图所示:



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39559641/article/details/112689253

随机推荐

Java设计模式

一,设计原则1,找出应用中可能需要变化之处,把他们独立出来,不要和那些不需要变化的代码混在一起。2,针对接口编程,而...

WhatAre_Words 阅读(965)

NIO笔记(一)缓冲区

文章目录基本概念使用示例简单的不指定长度的读取、写入、重置、清空指定长度的读取、mark、reset、hasRemaining、remaining创建直接缓冲区方法总结关于NIO的概念网上一搜一大把资...

qq_34912889 阅读(370)

文件的读写基础知识总结

文章目录文件打开关闭文件读取文件较大文件的读取文件的写入二进制文件写入删除目录json把文件以json格式储存打开json格式的文件文件打开读…r:以只读模式打开文件,文件...

代码小风 阅读(495)

2021-01-01程序的堆栈的区别

最近在跑程序时出现核心已转储的问题,后来经过某宝技术人员的讲解发现是内存不够,为此,专门找了下malloc分配内存的相关知识,找到了一个比较详细...

猫熊语 阅读(564)

Leetcode 5618:K和数对的最大数目

题目描述给你一个整数数组nums和一个整数k。每一步操作中,你需要从数组中选出和为k的两个整数,并将它们移出数组。返回你可以对数组执行的最大操作数。 示例1:...

weixin_35338624 阅读(819)

[链表]leetcode876-链表的中间节点

[链表]–链表的中间节点题目链接leetcode876.链表的中间节点题目给定一个头结点为head的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点...

Deepcola 阅读(463)