Java实现简单LRU缓存机制的方法

网友投稿 353 2022-12-06


Java实现简单LRU缓存机制的方法

一、什么是 LRU 算法

就是一种缓存淘汰策略。

计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。

LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。

二、LRU的使用

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作会使得密钥 2 作废

第一步:创建一个长度为2的LRUCache

第二步:cache.put(1, 1);放入key=1,value=1的数据

第三步:cache.put(2,2);放入key = 2,value = 2的数据

(因为2刚使用,所有把2移动到前面)

第四步:cache.get(1);获取key = 1的数据

(因为我们刚使用了1,所以把1移动到前面)

第五步:cache.put(3,3);放入key = 3,value = 3的数据

(因为3刚放进,所以放前面,又因为容量只有2,需要移除原先的1个。只因key = 2是最近最少使用的(key = 1刚get()过),所以移除2。

三、LRU的实现机制

算法:

LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

1)双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。

2)哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。

一、初始化:

二、cache.put(1,1):

三、cache.put(2,2):

四、cache.get(1):

五、cache.put(3,3):

四、代码如下

import java.io.*;

import java.util.HashMap;

public class test {

public static void main(String args[]) throws IOException {

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作会使得密钥 2 作废

http:// cache.get(2); // 返回 -1 (未找到)

cache.put(4, 4); // 该操作会使得密钥 1 作废

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

}

}

/**

* 设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put

*/

class LRUCache {

private HashMap cache = new HashMap();//方便通过key快速定位结点

private int size;

private int capacity;

private LinkedNode head,tail;

class Lhttp://inkedNode{

int key;

int value;

LinkedNode pre;

LinkedNode next;

}

public LRUCache(int capacity) {

this.size = 0;

this.capacity = capacity;

head = new LinkedNode();

tail = new LinkedNode();

head.next = tail;

tail.pre = head;

}

/**

* 移除节点

* @param node

*/

private void removeNode(LinkedNode node) {

LinkedNode preNode = node.pre;

LinkedNode nextNode = node.next;

preNode.next = nextNode;

nextNode.pre = preNode;

}

/**

* 添加节点到头部

* @param node

*/

private void addNode(LinkedNode node) {

node.pre = head;

node.next = head.next;

head.next.pre = node;

head.next = node;

}

/**

* 将节点移动到头部

* @param node

*/

private void moveToHead(LinkedNode node) {

removeNode(node);

addNode(node);

}

/**

* 获取数据

* @param key

* @return

*/

public int get(int key) {

LinkedNode node = cache.get(key);

if(node != null) {

moveToHead(node);

}else{

return -1;

}

return node.value;

}

/**

* 写入数据

* @param key

* @param value

*/

public void put(int key, int value) {

LinkedNode node = cache.get(key);

//存在

if(node != null) {

node.value = value;//可能更新数据

moveToHead(node);

}

//不存在

else{

LinkedNode newNode = new LinkedNode();

newNode.key = key;

newNode.value = value;

cache.put(key,newNode);//更新Map

addNode(newNode);//添加结点到头部

size++;//更新结点数

if(size > capacity) {//如果结点数超过容量大小

LinkedNode tailPre = tail.pre;

cache.remove(tailPre.key);//更新Map

removeNode(tailPre);//删除最后一个结点(尾结点的前一个结点)

size--;

}

}

}

}

总结:自己实现的简单LRU总归太简单了,要是想完善或者实现更真实的LRU,不妨参考一下Redis中的LRU。(◔◡◔)


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:springboot CommandLineRunner接口实现自动任务加载功能
下一篇:初学者学习Python好还是Java好
相关文章

 发表评论

暂时没有评论,来抢沙发吧~