資訊專欄INFORMATION COLUMN
摘要：不過其中的流程算是一個簡易的實現，可以對加深一些理解。實現二因此如何來實現一個完整的緩存呢，這次不考慮過期時間的問題。緩存數量超過閾值時移除鏈表尾部數據。
前言
LRU 是 Least Recently Used 的簡寫，字面意思則是最近最少使用。
通常用于緩存的淘汰策略實現，由于緩存的內存非常寶貴，所以需要根據某種規則來剔除數據保證內存不被撐滿。
如常用的 Redis 就有以下幾種策略：
| 策略 | 描述 |
|---|---|
| volatile-lru | 從已設置過期時間的數據集中挑選最近最少使用的數據淘汰 |
| volatile-ttl | 從已設置過期時間的數據集中挑選將要過期的數據淘汰 |
| volatile-random | 從已設置過期時間的數據集中任意選擇數據淘汰 |
| allkeys-lru | 從所有數據集中挑選最近最少使用的數據淘汰 |
| allkeys-random | 從所有數據集中任意選擇數據進行淘汰 |
| no-envicition | 禁止驅逐數據 |
摘抄自:https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Redis.md#%E5%8D%81%E4%B8%89%E6%95%B0%E6%8D%AE%E6%B7%98%E6%B1%B0%E7%AD%96%E7%95%A5實現一
之前也有接觸過一道面試題，大概需求是：
實現一個 LRU 緩存，當緩存數據達到 N 之后需要淘汰掉最近最少使用的數據。
N 小時之內沒有被訪問的數據也需要淘汰掉。
以下是我的實現：
public class LRUAbstractMap extends java.util.AbstractMap {
private final static Logger LOGGER = LoggerFactory.getLogger(LRUAbstractMap.class);
/**
* 檢查是否超期線程
*/
private ExecutorService checkTimePool ;
/**
* map 最大size
*/
private final static int MAX_SIZE = 1024 ;
private final static ArrayBlockingQueue QUEUE = new ArrayBlockingQueue<>(MAX_SIZE) ;
/**
* 默認大小
*/
private final static int DEFAULT_ARRAY_SIZE =1024 ;
/**
* 數組長度
*/
private int arraySize ;
/**
* 數組
*/
private Object[] arrays ;
/**
* 判斷是否停止 flag
*/
private volatile boolean flag = true ;
/**
* 超時時間
*/
private final static Long EXPIRE_TIME = 60 * 60 * 1000L ;
/**
* 整個 Map 的大小
*/
private volatile AtomicInteger size ;
public LRUAbstractMap() {
arraySize = DEFAULT_ARRAY_SIZE;
arrays = new Object[arraySize] ;
//開啟一個線程檢查最先放入隊列的值是否超期
executeCheckTime();
}
/**
* 開啟一個線程檢查最先放入隊列的值是否超期 設置為守護線程
*/
private void executeCheckTime() {
ThreadFactory namedThreadFactory = new ThreadFactoryBuilder()
.setNameFormat("check-thread-%d")
.setDaemon(true)
.build();
checkTimePool = new ThreadPoolExecutor(1, 1, 0L, TimeUnit.MILLISECONDS,
new ArrayBlockingQueue<>(1),namedThreadFactory,new ThreadPoolExecutor.AbortPolicy());
checkTimePool.execute(new CheckTimeThread()) ;
}
@Override
public Set entrySet() {
return super.keySet();
}
@Override
public Object put(Object key, Object value) {
int hash = hash(key);
int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ;
if (currentNode == null){
arrays[index] = new Node(null,null, key, value);
//寫入隊列
QUEUE.offer((Node) arrays[index]) ;
sizeUp();
}else {
Node cNode = currentNode ;
Node nNode = cNode ;
//存在就覆蓋
if (nNode.key == key){
cNode.val = value ;
}
while (nNode.next != null){
//key 存在 就覆蓋 簡單判斷
if (nNode.key == key){
nNode.val = value ;
break ;
}else {
//不存在就新增鏈表
sizeUp();
Node node = new Node(nNode,null,key,value) ;
//寫入隊列
QUEUE.offer(currentNode) ;
cNode.next = node ;
}
nNode = nNode.next ;
}
}
return null ;
}
@Override
public Object get(Object key) {
int hash = hash(key) ;
int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ;
if (currentNode == null){
return null ;
}
if (currentNode.next == null){
//更新時間
currentNode.setUpdateTime(System.currentTimeMillis());
//沒有沖突
return currentNode ;
}
Node nNode = currentNode ;
while (nNode.next != null){
if (nNode.key == key){
//更新時間
currentNode.setUpdateTime(System.currentTimeMillis());
return nNode ;
}
nNode = nNode.next ;
}
return super.get(key);
}
@Override
public Object remove(Object key) {
int hash = hash(key) ;
int index = hash % arraySize ;
Node currentNode = (Node) arrays[index] ;
if (currentNode == null){
return null ;
}
if (currentNode.key == key){
sizeDown();
arrays[index] = null ;
//移除隊列
QUEUE.poll();
return currentNode ;
}
Node nNode = currentNode ;
while (nNode.next != null){
if (nNode.key == key){
sizeDown();
//在鏈表中找到了 把上一個節點的 next 指向當前節點的下一個節點
nNode.pre.next = nNode.next ;
nNode = null ;
//移除隊列
QUEUE.poll();
return nNode;
}
nNode = nNode.next ;
}
return super.remove(key);
}
/**
* 增加size
*/
private void sizeUp(){
//在put值時候認為里邊已經有數據了
flag = true ;
if (size == null){
size = new AtomicInteger() ;
}
int size = this.size.incrementAndGet();
if (size >= MAX_SIZE) {
//找到隊列頭的數據
Node node = QUEUE.poll() ;
if (node == null){
throw new RuntimeException("data error") ;
}
//移除該 key
Object key = node.key ;
remove(key) ;
lruCallback() ;
}
}
/**
* 數量減小
*/
private void sizeDown(){
if (QUEUE.size() == 0){
flag = false ;
}
this.size.decrementAndGet() ;
}
@Override
public int size() {
return size.get() ;
}
/**
* 鏈表
*/
private class Node{
private Node next ;
private Node pre ;
private Object key ;
private Object val ;
private Long updateTime ;
public Node(Node pre,Node next, Object key, Object val) {
this.pre = pre ;
this.next = next;
this.key = key;
this.val = val;
this.updateTime = System.currentTimeMillis() ;
}
public void setUpdateTime(Long updateTime) {
this.updateTime = updateTime;
}
public Long getUpdateTime() {
return updateTime;
}
@Override
public String toString() {
return "Node{" +
"key=" + key +
", val=" + val +
"}";
}
}
/**
* copy HashMap 的 hash 實現
* @param key
* @return
*/
public int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
private void lruCallback(){
LOGGER.debug("lruCallback");
}
private class CheckTimeThread implements Runnable{
@Override
public void run() {
while (flag){
try {
Node node = QUEUE.poll();
if (node == null){
continue ;
}
Long updateTime = node.getUpdateTime() ;
if ((updateTime - System.currentTimeMillis()) >= EXPIRE_TIME){
remove(node.key) ;
}
} catch (Exception e) {
LOGGER.error("InterruptedException");
}
}
}
}
}
感興趣的朋友可以直接從:
https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUAbstractMap.java
下載代碼本地運行。
代碼看著比較多，其實實現的思路還是比較簡單：
采用了與 HashMap 一樣的保存數據方式，只是自己手動實現了一個簡易版。
內部采用了一個隊列來保存每次寫入的數據。
寫入的時候判斷緩存是否大于了閾值 N，如果滿足則根據隊列的 FIFO 特性將隊列頭的數據刪除。因為隊列頭的數據肯定是最先放進去的。
再開啟了一個守護線程用于判斷最先放進去的數據是否超期（因為就算超期也是最先放進去的數據最有可能滿足超期條件。）
設置為守護線程可以更好的表明其目的（最壞的情況下，如果是一個用戶線程最終有可能導致程序不能正常退出，因為該線程一直在運行，守護線程則不會有這個情況。）
以上代碼大體功能滿足了，但是有一個致命問題。
就是最近最少使用沒有滿足，刪除的數據都是最先放入的數據。
不過其中的 put get 流程算是一個簡易的 HashMap 實現，可以對 HashMap 加深一些理解。實現二
因此如何來實現一個完整的 LRU 緩存呢，這次不考慮過期時間的問題。
其實從上一個實現也能想到一些思路：
要記錄最近最少使用，那至少需要一個有序的集合來保證寫入的順序。
在使用了數據之后能夠更新它的順序。
基于以上兩點很容易想到一個常用的數據結構：鏈表。
每次寫入數據時將數據放入鏈表頭結點。
使用數據時候將數據移動到頭結點。
緩存數量超過閾值時移除鏈表尾部數據。
因此有了以下實現：
