LRU來自英文least recently used, 即最近最少使用. 開始時用于計算機(jī)系統(tǒng)的內(nèi)存管理(頁面置換算法 虛擬頁式存儲管理), 也經(jīng)常用于緩存的清理策略. 理解它, 對于理解常用的redis及memcached很有幫助.

LRU原理

待更新

實現(xiàn)一個極簡單的基于LinkedList的lru算法

后邊完善了再更新

package lru;

import java.util.LinkedList;

/**
 * @author simple_huang@foxmail.com on 2017/9/15.
 *         實現(xiàn)簡單的基于整型的Lru算法
 */
public class LruUtil {
    //使用LinkedList實現(xiàn)
    private static LinkedList<Integer> inner = new LinkedList<Integer>();
    //設(shè)置LinkedList最大長度為5, 即限定了最大容量
    private static final int maxSize = 5;

    /**
     * 私有化構(gòu)造器
     */
    private LruUtil() {
    }

    /**
     * 返回被移除的數(shù)字本身
     * 如果沒有需要移除的, 返回添加的數(shù)字本身
     *
     * @param i
     * @return
     */
    public static int LruAdd(int i) {
        //如果存在i, 說明i被重復(fù)使用了, 則將i置于first位置, 這里是最小可能被移除的位置
        if (inner.contains(i)) {
            inner.remove(inner.indexOf(i));
            inner.addFirst(i);
            return i;
        }
        //如果長度小于設(shè)定最大值, 說明容器還沒滿, 可以在不移除的情況下添加
        if (inner.size() < maxSize) {
            inner.addFirst(i);
            return i;
        }
        //如果以上兩種情況都不存在, 則將last位置元素移除, 將數(shù)字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);
        }
    }
}

執(zhí)行main方法, 可以打印結(jié)果如下

[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

可以比較直觀的看到最簡單的內(nèi)存管理是如何實現(xiàn)的

碼農(nóng)翻身群作業(yè)