LRU来自英文least recently used, 即最近最少使用. 开始时用于计算机系统的内存管理(页面置换算法 虚拟页式存储管理), 也经常用于缓存的清理策略. 理解它, 对于理解常用的redis及memcached很有帮助.
LRU原理
待更新
实现一个极简单的基于LinkedList的lru算法
后边完善了再更新
package lru;
import java.util.LinkedList;
/**
* @author simple_huang@foxmail.com on 2017/9/15.
* 实现简单的基于整型的Lru算法
*/
public class LruUtil {
//使用LinkedList实现
private static LinkedList<Integer> inner = new LinkedList<Integer>();
//设置LinkedList最大长度为5, 即限定了最大容量
private static final int maxSize = 5;
/**
* 私有化构造器
*/
private LruUtil() {
}
/**
* 返回被移除的数字本身
* 如果没有需要移除的, 返回添加的数字本身
*
* @param i
* @return
*/
public static int LruAdd(int i) {
//如果存在i, 说明i被重复使用了, 则将i置于first位置, 这里是最小可能被移除的位置
if (inner.contains(i)) {
inner.remove(inner.indexOf(i));
inner.addFirst(i);
return i;
}
//如果长度小于设定最大值, 说明容器还没满, 可以在不移除的情况下添加
if (inner.size() < maxSize) {
inner.addFirst(i);
return i;
}
//如果以上两种情况都不存在, 则将last位置元素移除, 将数字i添加到first位置
int removeInt = inner.removeLast();
inner.addFirst(i);
return removeInt;
}
public static void main(String[] args) {
int[] intArray = {9, 7, 2, 1, 0, 1, 7, 0, 6, 1, 9, 4, 6};
for (int i : intArray) {
LruUtil.LruAdd(i);
System.out.println(inner + " " + "添加 " + i);
}
}
}
执行main方法, 可以打印结果如下
[9] 添加 9
[7, 9] 添加 7
[2, 7, 9] 添加 2
[1, 2, 7, 9] 添加 1
[0, 1, 2, 7, 9] 添加 0
[1, 0, 2, 7, 9] 添加 1
[7, 1, 0, 2, 9] 添加 7
[0, 7, 1, 2, 9] 添加 0
[6, 0, 7, 1, 2] 添加 6
[1, 6, 0, 7, 2] 添加 1
[9, 1, 6, 0, 7] 添加 9
[4, 9, 1, 6, 0] 添加 4
[6, 4, 9, 1, 0] 添加 6
可以比较直观的看到最简单的内存管理是如何实现的
码农翻身群作业
