lru算法

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

可以比较直观的看到最简单的内存管理是如何实现的

码农翻身群作业