我是靠谱客的博主 明亮鸵鸟，最近开发中收集的这篇文章主要介绍最近最少使用LRU（Least Recently Used）算法java实现最近最少使用LRU（Least Recently Used）算法java实现，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
- 最近最少使用LRU（Least Recently Used）算法java实现
- 一.使用LinkedHashMap算法实现
- 二.手撸 LRU 算法实现（Hash表 + 双向链表）
- 三.总结
最近最少使用LRU（Least Recently Used）算法java实现
LRU 是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
以上是来自百度百科的介绍，通俗来说，LRU就是一个淘汰算法，例如内存相较于硬盘可以快速的读写，但是内存的空间是有限的，为了有效的利用内存空间，就需要将一些非热点数据给淘汰掉，这里就用到 LRU 算法，它会将内存中最近一段时间没有使用的数据给淘汰掉。
另外 LRU 算法在找工作面试中，经常会被问到，需要能够在短时间内写出来，大家平时还是要勤加练习，下面给出两种算法实现。
动动发财小手，关注 + 点赞 + 收藏不迷路。
一.使用LinkedHashMap算法实现
LinkedHashMap 底层采用 HashMap + 双向链表，已经实现了 LRU 算法，我们可以直接来使用 LinkedHashMap 来实现LRU算法。
以下是 LinkedHashMap 构造函数的代码
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap 构造函数前两个参数在这里就不介绍了，这儿简单介绍一下第三个参数：boolean accessOrder，true 代表按照存取顺序来排序， false 代表按照插入顺序来排序。
以下是使用 LinkedHashMap 来实现的 LRU 算法。
package algorithm.lru;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* 使用LinkedHashMap 实现的LRU
*
* @date: 2021-12-12 21:55
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int cacheSize;
public LRUCache(int cacheSize) {
super(cacheSize, 0.75f, true);
this.cacheSize = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
public static void main(String[] args) {
LRUCache lru = new LRUCache(3);
lru.put("1", 1);
lru.put("2", 2);
lru.put("3", 3);
lru.put("4", 4);
lru.printLRU(lru);
System.out.println();
lru.get("3");
lru.printLRU(lru);
}
public void printLRU(LRUCache lru) {
Iterator<Map.Entry<String, Integer>> iterator = lru.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
}
}
}
输出如下：
key = 2, value = 2
key = 3, value = 3
key = 4, value = 4
key = 2, value = 2
key = 4, value = 4
key = 3, value = 3
可以看到，执行了 lru.put(“4”, 4) 之后，key = 1 就被remove了；当执行 lru.get(“3”) 之后，key = 3被挪到了双向链表的最前面。
二.手撸 LRU 算法实现（Hash表 + 双向链表）
上面的 LRU 算法实现，有点取巧，通常在面试的时候，面试官希望看到具体的算法实现逻辑，而不是使用 LinkedHashMap 已有的功能。当然了，在工作当中，还是不要自己来实现了。
package algorithm.lru;
import java.util.concurrent.ConcurrentHashMap;
/**
* LRU (Least recently used) 最近最少使用
*
* @date: 2021/12/12 22:19
*/
public class LruCache {
private static ConcurrentHashMap<String, Node> cacheMap;
private static volatile int count;
private static int capacity;
private Node head = new Node();
private Node tail = new Node();
LruCache(int capacity) {
this.count = 0;
this.capacity = capacity;
cacheMap = new ConcurrentHashMap<>();
this.tail.pre = head;
this.head.next = tail;
}
private static class Node {
Node() {
}
Node(String key) {
this.key = key;
this.value = Integer.parseInt(key);
}
private String key;
private int value;
private Node pre;
private Node next;
public String getKey() {
return this.key;
}
}
public void put(Node node) {
Node existNode = get(node);
if (existNode != null) {
// cacheMap中node存在,先remove节点,再把节点移到链表头部
removeNode(existNode);
// 在链表头部插入node
headAdd(existNode);
} else {
// cacheMap中node不存在,则插入node
if (count == capacity) {
// 缓存已满,在链表尾部remove
tailRemove();
count--;
}
headAdd(node);
count++;
cacheMap.put(node.getKey(), node);
}
}
public void headAdd(Node node) {
node.next = head.next;
head.next.pre = node;
node.pre = head;
head.next = node;
}
public void removeNode(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
public void tailRemove() {
tail.pre.pre.next = tail;
tail.pre = tail.pre.pre;
}
public Node get(Node node) {
return cacheMap.get(node.getKey());
}
public void print() {
Node node = head;
System.out.println("========================================");
while (node.next != null && node.next != tail) {
System.out.println(node.next.key + " count = " + count);
node = node.next;
}
}
public static void main(String[] args) {
Node node1 = new Node("1");
Node node2 = new Node("2");
Node node3 = new Node("3");
Node node4 = new Node("4");
LruCache lruCache1 = new LruCache(3);
lruCache1.put(node1);
lruCache1.print();
lruCache1.put(node2);
lruCache1.print();
lruCache1.put(node3);
lruCache1.print();
lruCache1.put(node4);
lruCache1.print();
System.out.println("");
System.out.println("###################################################");
System.out.println("");
Node node5 = new Node("5");
Node node6 = new Node("6");
Node node7 = new Node("7");
LruCache lruCache3 = new LruCache(3);
lruCache3.put(node5);
lruCache3.print();
lruCache3.put(node6);
lruCache3.print();
lruCache3.put(node7);
lruCache3.print();
lruCache3.put(node5);
lruCache3.print();
System.out.println("");
System.out.println("###################################################");
System.out.println("");
Node node8 = new Node("8");
LruCache lruCache2 = new LruCache(3);
lruCache2.put(node8);
lruCache2.print();
lruCache2.put(node8);
lruCache2.print();
}
}
输出如下：
========================================
1 count = 1
========================================
2 count = 2
1 count = 2
========================================
3 count = 3
2 count = 3
1 count = 3
========================================
4 count = 3
3 count = 3
2 count = 3
###################################################
========================================
5 count = 1
========================================
6 count = 2
5 count = 2
========================================
7 count = 3
6 count = 3
5 count = 3
========================================
5 count = 3
7 count = 3
6 count = 3
###################################################
========================================
8 count = 1
========================================
8 count = 1
三.总结
最好还是能够手写第二种 LRU 的算法实现，就算不能全写出来，也可以写一个大概的思路，面试官主要考察的也就是这个，毕竟在短短的10几分钟内，手撸一个 LRU 还是有点难度的，难免会有一些小bug。
引用:
1.https://baike.baidu.com/item/LRU/1269842?fr=aladdin
最后
以上就是明亮鸵鸟为你收集整理的最近最少使用LRU（Least Recently Used）算法java实现最近最少使用LRU（Least Recently Used）算法java实现的全部内容，希望文章能够帮你解决最近最少使用LRU（Least Recently Used）算法java实现最近最少使用LRU（Least Recently Used）算法java实现所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复