1. LRU算法

常見的緩存淘汰策略有三種，分別是：先進先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frequently Used）、最近最少使用策略LRU（Least Recently Used）

• 先進先出策略（FIFO）：即最先進入緩存的數據最先被淘汰。這種策略類似于隊列的工作方式，新數據加入到隊列的尾部，而最先進入隊列的數據會被淘汰。
• 最少使用策略（LFU）：即最少被訪問的數據最先被淘汰。LFU策略根據數據的訪問頻率來決定淘汰順序，訪問次數最少的數據會被優先淘汰。
• 最近最少使用策略（LRU）：即最近最少被訪問的數據最先被淘汰。LRU策略根據數據的訪問時間來決定淘汰順序，最近最久未被訪問的數據會被優先淘汰。

LRU算法的工作原理：

1. 首先，我們定義一個容量為4的整型數組來模擬緩存，初始狀態數組為空
2. 我們開始向數組中查詢數據，如果數據存在就返回，數據不存在就插入數據
   2.1 查詢數據1：由于緩存為空，將數據1插入到數組頭部（下標0）
   2.2 查詢數據2：由于緩存中已有數據1，根據LRU算法，將數據2插入到數組頭部，將原來的數據1向后位移，數組中的數據是2、1
   2.3 查詢數據3和4：類似地，數據3和4被插入到數組的頭部，數組中的數據變為4、3、2、1，此時數組達到了緩存的最大容量
3. 繼續訪問數據就有兩種方式
   3.1 訪問緩存中沒有的數據，比如5，那么由于此是數組已經滿了，所以根據LRU算法定義，我們把數組尾部的數據1剔除，然后把1之前的數據，都向右位移一位，此時數組是：null、4、3、2，然后再將數據5插入到數組的頭部，那么此時數組中的數據就是：5、4、3、2
   3.2 訪問緩存中已經有的數據，比如2，那么不管此時數組是否已經滿了，我們可以在數組中找到數據2，那么我們就先把數組中數據是2的數據刪除，然后把2之前的數據顯向右位移一位，此時數組中的數據是：null、4、3、1，然后我們再把數據2插入到數組的頭部之后，數組中的數據是：2、4、3、1

2. 基于數組實現LRU算法

import java.util.HashMap;
import java.util.Map;/*** 基于數組實現LRU算法*/
public class LRUBaseArray<T> {private static final int DEFAULT_CAPACITY = 8;private int capacity; // 緩存容量private int count; // 緩存中元素數量private T[] value; // 存放元素的數組，模擬緩存private Map<T, Integer> holder; // 存儲數據的位置public LRUBaseArray() {this(DEFAULT_CAPACITY);}public LRUBaseArray(int capacity) {this.capacity = capacity;value = (T[]) new Object[capacity];count = 0;holder = new HashMap<>(capacity);}/*** 訪問某個值，有的話更新到頭部，沒有的話嘗試插入到頭部** @param object 待插入的元素*/public void offer(T object) {if (object == null) {throw new IllegalArgumentException("緩存容器不支持null");}Integer index = holder.get(object);if (index == null) {if (isFull()) {removeAndCache(object);} else {cache(object);}} else {update(index);}}/*** 將新元素插入緩存頭部** @param object 待插入的元素*/private void cache(T object) {rightShift(count);value[0] = object;holder.put(object, 0);count++;}/*** 更新已存在元素的位置到緩存頭部** @param index 元素在緩存中的位置索引*/private void update(Integer index) {T target = value[index];rightShift(index);value[0] = target;holder.put(target, 0);}/*** 緩存滿的情況下，刪除尾部元素，并將新元素插入緩存頭部** @param object 待插入的元素*/private void removeAndCache(T object) {T key = value[--count];holder.remove(key);cache(object);}/*** 將數組中的元素向右移動一位** @param end 數組邊界*/public void rightShift(int end) {for (int i = end - 1; i >= 0; i--) {value[i + 1] = value[i];holder.put(value[i], i + 1);}}/*** 判斷緩存是否已滿** @return 緩存是否已滿*/private boolean isFull() {return count == capacity;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();for (int i = 0; i < count; i++) {sb.append(value[i]);sb.append(" ");}return sb.toString();}public static void main(String[] args) {LRUBaseArray<Integer> lru = new LRUBaseArray<>();lru.offer(1);lru.offer(2);lru.offer(3);lru.offer(4);lru.offer(5);System.out.println(lru);lru.offer(6);lru.offer(7);lru.offer(8);lru.offer(9);System.out.println(lru);}
}

執行結果

5 4 3 2 
9 8 7 6 

首先將數字1到5依次加入緩存，當緩存容量達到上限4時，數字1被替換出去，然后繼續添加數字6到9，此時數字5被替換出去，最終緩存中只剩下數字6到9。

3. 基于鏈表實現LRU算法

import java.util.HashMap;
import java.util.Map;/*** 基于單鏈表實現LRU算法* @param <T>*/
public class LRUBaseLinkedList<T> {// 默認鏈表容量private final static int DEFAULT_CAPACITY = 5;// 頭節點private Node<T> head;// 鏈表長度private int size;// 鏈表容量private int capacity;// 記錄節點的前一個節點，方便刪除操作private Map<T, Node<T>> prevNodeMap;public LRUBaseLinkedList() {this(DEFAULT_CAPACITY);}public LRUBaseLinkedList(int capacity) {this.capacity = capacity;this.size = 0;this.head = new Node<>();this.prevNodeMap = new HashMap<>();}/*** 插入元素** @param data 待插入的元素*/public void add(T data) {if (data == null) {throw new IllegalArgumentException("Data cannot be null");}Node<T> prevNode = prevNodeMap.get(data);if (prevNode != null) {deleteElem(prevNode);} else {if (size >= capacity) {deleteLastElem();}}insertElemAtHead(data);}// 刪除尾節點private void deleteLastElem() {Node<T> ptr = head;while (ptr.next.next != null) {ptr = ptr.next;}prevNodeMap.remove(ptr.next.data);ptr.next = null;size--;}// 刪除當前節點的下一個節點private void deleteElem(Node<T> prevNode) {Node<T> temp = prevNode.next;prevNode.next = temp.next;prevNodeMap.remove(temp.data);temp = null;size--;}// 插入元素到鏈表頭節點private void insertElemAtHead(T data) {Node<T> next = head.next;head.next = new Node<>(data, next);prevNodeMap.put(data, head);size++;}// 定義內部存儲結構private static class Node<T> {T data;Node<T> next;Node() {}Node(T data, Node<T> next) {this.data = data;this.next = next;}}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();Node<T> temp = head.next;while (temp != null) {sb.append(temp.data).append(" ");temp = temp.next;}return sb.toString();}public static void main(String[] args) {LRUBaseLinkedList<Integer> list = new LRUBaseLinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);list.add(6);System.out.println(list);list.add(4);System.out.println(list);}
}

執行結果

1 2 3 4 5 
6 1 2 3 4 
4 6 1 2 

在第一次插入元素時，鏈表中依次添加了1、2、3、4、5這五個元素，并打印了鏈表中的所有元素。
在第二次插入元素時，由于容量已滿，因此刪除了鏈表的尾部元素5，然后將新的元素6插入到了鏈表頭部。
在第三次插入元素時，元素4已經存在于鏈表中，因此刪除了元素4所在的位置，并將其移動到了鏈表頭部。