漫畫說什麼是 LRU 算法？

————— 兩個月前 —————

用戶信息當然是存在數據庫裡。但是由於我們對用戶系統的性能要求比較高，顯然不能每一次請求都去查詢數據庫。

所以，小灰在內存中創建了一個哈希表作為緩存，每次查找一個用戶的時候先在哈希表中查詢，以此提高訪問性能。

很快，用戶系統上線了，小灰美美地休息了幾天。

一個多月之後......

———————————————

什麼是哈希鏈表呢？

我們都知道，哈希表是由若干個Key-Value所組成。在“邏輯”上，這些Key-Value是無所謂排列順序的，誰先誰後都一樣。

在哈希鏈表當中，這些Key-Value不再是彼此無關的存在，而是被一個鏈條串了起來。每一個Key-Value都具有它的前驅Key-Value、後繼Key-Value，就像雙向鏈表中的節點一樣。

這樣一來，原本無序的哈希表擁有了固定的排列順序。

讓我們以用戶信息的需求為例，來演示一下LRU算法的基本思路：

1.假設我們使用哈希鏈表來緩存用戶信息，目前緩存了4個用戶，這4個用戶是按照時間順序依次從鏈表右端插入的。

2.此時，業務方訪問用戶5，由於哈希鏈表中沒有用戶5的數據，我們從數據庫中讀取出來，插入到緩存當中。這時候，鏈表中最右端是最新訪問到的用戶5，最左端是最近最少訪問的用戶1。

3.接下來，業務方訪問用戶2，哈希鏈表中存在用戶2的數據，我們怎麼做呢？我們把用戶2從它的前驅節點和後繼節點之間移除，重新插入到鏈表最右端。這時候，鏈表中最右端變成了最新訪問到的用戶2，最左端仍然是最近最少訪問的用戶1。

4.接下來，業務方請求修改用戶4的信息。同樣道理，我們把用戶4從原來的位置移動到鏈表最右側，並把用戶信息的值更新。這時候，鏈表中最右端是最新訪問到的用戶4，最左端仍然是最近最少訪問的用戶1。

5.後來業務方換口味了，訪問用戶6，用戶6在緩存裡沒有，需要插入到哈希鏈表。假設這時候緩存容量已經達到上限，必須先刪除最近最少訪問的數據，那麼位於哈希鏈表最左端的用戶1就會被刪除掉，然後再把用戶6插入到最右端。

以上，就是LRU算法的基本思路。

需要注意的是，這段不是線程安全的，要想做到線程安全，需要加上synchronized修飾符。