什麼是LRU算法？
redis大家都玩過吧，你們好奇redis記憶體資料存滿之後會發生什麼嗎？抛出異常？禁止使用？還是删除資料？其實redis設計了一種内潤淘汰機制。
noeviction(預設政策)：屏蔽寫操作，傳回錯誤（特殊的寫操作除外），但是支援删除操作
volatile-lru：使用LRU算法對設定了過期時間的key進行删除。
allkeys-lru：使用LRU算法對所有key進行删除。
allkeys-random：在所有的key中随即淘汰一部分資料。
volatile-ttl：根據過期時間删除key，越快過期，就會被優先執行删除操作。
volatile-random：在設定了過期時間的key中随機淘汰一部分資料。
使用指令檢視redis的淘汰機制：
config get maxmemory-policy
看到沒有，其中就有一種LRU算法，那LRU到底是什麼呢？最近最少使用的就被淘汰（删除），這樣說比較抽象，我舉個現實中的例子：假如你買了一個衣櫃，用來存放衣服，又因為你平時比較喜歡剁手，買着買着發現衣服太多了，衣櫃放不下了，房間有沒有其他空間存放，這個時候是不是就需要将衣櫃裡面的某些衣服送給朋友或者丢掉呢？那你處理哪些衣服呢？你是不是會處理掉不怎麼穿，并且買了很久的衣服，不會将你昨天買的就處理掉吧，LRU也是這樣，他會保留最近被使用的，删除之前最少被使用的資料。
數組實作一個簡單的LRU算法
實作思路：
1.建立一個指定長度的數組。
2.判斷數組是否已被完全使用，如果沒有直接将資料添加數組末尾。
3.如果數組已經被完全使用，判斷此資料在數組中書否存在，如存在：将此資料移到數組末尾，其他資料往前移一位；如不存在，删除數組第一位，然後将數組後面的資料往前移一位，最後将資料添加到數組的末尾。
請看代碼：
/**
* 判斷資料是否存在數組中
* @param arr
* @param length
* @param str
* @return
*/
public static Integer getIndex(String[] arr, int length, String str) {
for (int i = 0; i < length; i++) {
if (str.equals(arr[i])) {
return i;
}
}
return null;
}
/**
* 使用數組實作LRU算法
*
* @param args
*/
public static void main(String[] args) {
String[] arr = new String[5];
String[] newArr;
int length = arr.length;
Scanner input = new Scanner(System.in);
while (true) {
System.out.println("");
System.out.println("請輸入資料:");
String str = input.next();
if ("n".equals(str)) {
System.exit(0);
}
newArr = arr.clone();
if(null == arr[length - 1]){
loop:
for (int i = 0; i < length; i++) {
if (null == arr[i]) {
arr[i] = str;
break loop;
}
}
}else{
Integer index = getIndex(arr, length, str);
if (null == index) {
// System.out.println("沒有在數組中找到資料");
//數組中找不到資料
//所有資料左移一位
for (int i = 1; i < length; i++) {
arr[i - 1] = newArr[i];
}
arr[length - 1] = str;
} else {
//System.out.println("在數組中找到了資料，下标在："+index);
int newArrLength = newArr.length;
for (int i = 0; i < newArrLength - 1; i++) {
if (index > i) {
arr[i] = newArr[i];
} else {
arr[i] = newArr[i + 1];
}
}
arr[length - 1] = str;
}
}
//列印結果
for (int i = 0; i < length; i++) {
if (i == (length - 1)) {
System.out.print(arr[i]);
} else {
System.out.print(arr[i] + ",");
}
}
}
}
請看結果：
這樣，用數組實作一個簡單的LRU就完成了，當然，你可以使用集合，還會更簡單。
使用連結清單的集合實作LRU算法
思路：
1.判斷集合是否完全被使用，如果沒有，将資料添加到集合的末尾。
2.如果集合空間已被完全使用，判斷資料在幾何中是否出現過，若沒有：删除集合中的第一個元素，将資料添加到集合末尾；如果存在，删除存在的元素，然後再将資料添加到集合末尾。
代碼實作：
package cn.meiot.test;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
public class LinkedLRU {
public static void main(String[] args) {
Map<Object, Object> map = new LinkedHashMap<Object, Object>(5);
Scanner input = new Scanner(System.in);
System.out.println("這是用連結清單集合實作的LRU=================");
while (true){
System.out.println("");
System.out.println("請輸入資料:");
String str = input.next();
if ("n".equals(str)) {
System.exit(0);
}
if(map.size() < 5){
map.put(str,str);
}else if(null == map.get(str)){
Map.Entry<Object, Object> head = getHead(map);
map.remove(head.getKey());
map.put(str,str);
}else{
map.remove(str);
map.put(str,str);
}
System.out.println(map);
}
}
/**
* 擷取第一個元素
* @param map
* @param <K>
* @param <V>
* @return
*/
public static <K, V> Map.Entry<K, V> getHead(Map<K, V> map) {
return map.entrySet().iterator().next();
}
}
結果如下：
