当前位置：首页 > news >正文

武汉网站服务站长工具平台

news 2025/8/6 9:24:54

武汉网站服务,站长工具平台,什么是外包,dw网站制作流程问题：使用Java完成一个简单的LRU算法什么是LRU算法LRU(Least Recently Used)，也就是最近最少使用。一种有限的空间资源管理的解决方案，会在空间资源不足的情况下移除掉最近没被使用过的数据，以保证接下来需要的空间资源。在现在通…

问题：使用Java完成一个简单的LRU算法

什么是LRU算法

LRU(Least Recently Used)，也就是最近最少使用。一种有限的空间资源管理的解决方案，会在空间资源不足的情况下移除掉最近没被使用过的数据，以保证接下来需要的空间资源。

在现在通用的操作系统中为了解决内存不足这个问题，提出了虚拟内存这种解决方案，其实虚拟内存也就是将机器的内存分为多个页面(提个小问题，一个页面包含了多少kb的空间？)，内存中只存放当前需要的页面信息，暂时不使用的内存数据就保存到磁盘中。这可以很好的解决内存不足的问题。当然了这就无故出现页面交换的情况，使得读取内存的速度降低(磁盘的读取速度远小于内存的读取速度)，这种方案肯定有利有弊，只需要我们的服务能够接受这种情况，那就完全没有问题。

Redis做为一种内存数据库，内存大小对数据库的影响更重要，所以redis也需要及时的移除掉那些过期数据。在redis中有定时清楚、惰性删除、定期删除，但是其策略主要分为两种，基于访问时间和基于访问频率。基于访问时间就是LRU算法，看看LRU算法的图解过程，如下图。

e26a2301f97b

image.png

先定义好一个定长的队列

按照FIFO的流程，依次申请一段空间

直到队列被占满了，出现内存不足的情况，淘汰策略开始工作

会淘汰队列中最先进入的数据，最先进去的数据也就是最近最久未被使用的数据，然后把其移除出队列

LRU 算法小demo

整体的算法实现没有太多的难度，维护一个有限长度的队列的进出，需要移除或者插入数据。时间复杂度可能会是个问题。

队列如果是链表，则移除数据的时间复杂度是O(1)，但是查找数据的时间复杂度是O(n)

队列如果是数组，则移除数据的时间复杂度是O(n)，而且移除数据还伴随着数组的平行移动，查找数据也是O(n)，除非另外再加一个Map存储其索引值会使得其查找的速度降低到O(1)，但是却又提高了空间复杂度

接下来写个基于数组的LRU的简单代码

public class LruDemo {

private Object[] items;

private HashMap map;

private int size;

private int index;

public LruDemo() {

this(8);

}

public LruDemo(int size) {

this.size = size;

this.items = new Object[size];

this.map = new HashMap<>(16);

this.index = 0;

}

public void put(T t) {

Integer value = map.get(t);

if (value == null) {

if (index >= size) {

// 满了，需要移除第一个元素

for(int i=1; i

items[i-1] = items[i];

map.replace((T)items[i-1], i);

}

index -= 1;

}

items[index] = t;

map.put(t, index);

index += 1;

} else {

for(int i=value; i

items[i] = items[i+1];

map.replace((T)items[i], i);

}

items[index-1] = t;

map.replace(t, index-1);

}

public void getAll() {

for(int i=0;i

System.out.println(items[i]);

}

System.out.println("======");

}

public static void main(String[] args) {

LruDemo lruDemo = new LruDemo(6);

lruDemo.put("aliace");

lruDemo.put("bob");

lruDemo.put("cat");

lruDemo.put("dog");

lruDemo.put("egg");

lruDemo.getAll();

lruDemo.put("bob");

lruDemo.getAll();

lruDemo.put("fine");

lruDemo.put("good");

lruDemo.getAll();

}

输出的结果是

aliace

bob

cat

dog

egg

======

aliace

cat

dog

egg

bob

======

cat

dog

egg

bob

fine

good

======

这只是一种简单的写法，而且效率也比较低，现在就来介绍下将要学习的LinkedHashMap

LinkedHashMap

LinkedHashMap是继承自HashMap的，只是另外添加了排序相关的功能，使得其成为了有序hashmap，关于HashMap的介绍可以看看Java8的HashMap原理学习，接下来重点关注LinkedHashMap相比HashMap拓展了哪些功能呢？

Entry节点信息

static class Entry extends HashMap.Node {

Entry before, after;

Entry(int hash, K key, V value, Node next) {

super(hash, key, value, next);

}

头尾节点

transient LinkedHashMap.Entry head;

transient LinkedHashMap.Entry tail;

Entry节点就包含了前置节点和后置节点的地址信息，再加上在LinkedHashMap又中添加了head和tail头尾节点，这样就使得之前的链表+数据的数据结构基础上又加上了双向链表，通过双向链表实现有序性，并且 LinkedHashMap = Linked + HashMap。

accessOrder 值

final boolean accessOrder; 是一个非常关键的字段值，暂时按下不表，接下来会知道其真正的含义

get操作

HashMap进行get操作还是很简单的，通过hash获取index，再可能涉及到链表(红黑树)的遍历操作，在LinkedHashMap中同样重写了相关方法

public V get(Object key) {

Node e;

if ((e = getNode(hash(key), key)) == null)

return null;

if (accessOrder)

afterNodeAccess(e);

return e.value;

}

进行常规的getNode操作后在找到对应的节点e之后，当accessOrder是true时，调用afterNodeAccess方法，从其名称也可以看出来时访问节点后的操作。

void afterNodeAccess(Node e) { // move node to last

LinkedHashMap.Entry last;

if (accessOrder && (last = tail) != e) {

LinkedHashMap.Entry p =

(LinkedHashMap.Entry)e, b = p.before, a = p.after;

// b 和 a 分别是访问的节点e的前置和后置节点

p.after = null;

if (b == null)

head = a;

else

b.after = a;

if (a != null)

a.before = b;

else

last = b;

if (last == null)

head = p;

else {

p.before = last;

last.after = p;

}

// 把其移动到双向链表的尾部节点

tail = p;

++modCount;

}

也就是说当accessOrder为true时，会修改其双向链表的节点顺序，而且搜索整个类也会发现accessOrder只在这里发挥用处。顺带观察下其key、value、entry的迭代器遍历情况，可以发现都是使用了for (LinkedHashMap.Entry e = head; e != null; e = e.after) 这种条件去循环遍历。

所以accessOrder就是起到控制访问顺序的作用，设置为true之后每访问一个元素，就将该元素移动到双向链表的尾部节点，通过改变节点在双向链表的位置实现对链表顺序的控制。

put 操作

在HashMap中通过put方法插入一个新的节点数据，LinkedHashMap并没有重写该方法。在HashMap中先检查是否存在对应的key，如果不存在则会通过newNode方法创建一个新节点，然后等待插入到合适的位置，LinkedHashMap则重写了newNode方法，如下代码块：

Node newNode(int hash, K key, V value, Node e) {

LinkedHashMap.Entry p =

new LinkedHashMap.Entry(hash, key, value, e);

linkNodeLast(p);

return p;

}

// link at the end of list

private void linkNodeLast(LinkedHashMap.Entry p) {

LinkedHashMap.Entry last = tail;

tail = p;

if (last == null)

head = p;

else {

p.before = last;

last.after = p;

}

创建完一个LinkedHashMap.Entry节点p后，p节点的before, after都是null，然后调用linkNodeLast方法，采取尾插法，形成新的尾节点(这里有一种情况是最早的时候tail==head==null的情况，会使得头节点和尾节点都指向同一个节点)。

新插入一个节点后还会调用afterNodeInsertion方法，看起方法名称也知道是在node节点插入后的操作，在HashMap中是空实现，在LinkedHashMap则实现了该方法，如下代码块：

void afterNodeInsertion(boolean evict) { // possibly remove eldest

LinkedHashMap.Entry first;

if (evict && (first = head) != null && removeEldestEntry(first)) {

K key = first.key;

removeNode(hash(key), key, null, false, true);

}

protected boolean removeEldestEntry(Map.Entry eldest) {

return false;

}

默认传入的evict值是true，而removeEldestEntry方法默认返回false，也就是什么都不做。当在put一个已经存在的节点的情况，会调用afterNodeAccess方法，也会去改变在链表中的位置。重写removeEldestEntry方法并且当起返回true时，调用removeNode节点移除head节点。这个就包含了LRU最近最少使用的实现原理。

自定义LRU算法

设置accessOrder为true后，每次访问、新增的节点都会移动到尾部，当removeEldestEntry返回true时就会移除头节点，那么只需要设置一种特定的判断逻辑使得removeEldestEntry返回true就可以了。按照上面LRU算法的思想，只有当空间满了的情况下才会移除头节点数据，同理只需要判断当前map中的节点数是否达到相关的阈值即可。继承LinkedHashMap重载removeEldestEntry方法，代码如下：

public class LruMap extends LinkedHashMap {

private int maxSize;

public LruMap(int initialCapacity, float loadFactor, boolean accessOrder, int maxSize) {

super(initialCapacity, loadFactor, accessOrder);

this.maxSize = maxSize;

}

public LruMap(int maxSize) {

this(16, 0.75f, true, maxSize);

}

public LruMap(int tableSize, int maxSize) {

this(tableSize, 0.75f, true, maxSize);

}