LRU的java实现

2024-08-26 03:58

文章标签 java 实现 lru

本文主要是介绍LRU的java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是LRU

LRU（Least Recently Used）直译来看，就是最近最少使用，因为LRU是一个淘汰算法，所以指的是，每次都淘汰离当前时间最远的被使用到的那一个。也就是最久没有被使用到的那个。

为什么需要LRU

LRU其实大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法，是为了提高页面的命中率而使用的算法，就应用开发来说，Redis的内存淘汰策略使用的就是LRU算法，当Redis内存使用打到上限，如果采用的 allkeys-lru 删除策略，此时我们再增加key，redis就会根据LRU来挑选一个key进行删除。

LRU的使用场景

操作系统的一些内存管理，页面置换算法
redis/memcache/mysql
业务使用

LRU的实现方案

对于添加新的k-v，和删除已存在的key，我们都想达到O(1)的时间复杂度，所以我们使用双向链表+hash的实现方案。
hashmap负责定位数据位置，双向链表负责转移和增减数据。
涉及到删除的话，那我们使用的链表应该是个定长链表，当满了的时候，进行LRU的删除。
代码如下：

package com.vipkid.modelserving.web;import java.util.HashMap;
import java.util.LinkedList;public class LRUCache {private int capacity;//hashmapprivate HashMap<Integer,Integer> map;//双向链表private LinkedList<Integer> list;//初始化容量public LRUCache(int capacity) {this.capacity=capacity;map=new HashMap<>();list=new LinkedList<Integer>();}//取值，存在则将最新访问的挪到最后public int get(int key) {//key存在if (map.containsKey(key)){list.remove(key);//移到最后list.addLast(key);return map.get(key);}return -1;}//存入值，存在则将最新访问的挪到最后//不存在则存入最后，若容量满，从最开始开始删除public void put(int key, int value) {//key 已存在if (map.containsKey(key)){//删除旧的list.remove(key);//放到最后list.addLast(key);return;}//key不存在，满了if (list.size()==capacity){//从最开始开始删除int remove=list.removeFirst();map.remove(remove);map.put(key,value);list.addLast(key);}else {//key不存在，没满map.put(key,value);list.addLast(key);}}}