【死磕 Java 基礎】 — 自己動手實作一個 LRU

LRU，即 Least Recently Use ，直譯為 “最近最少使用”。它是根據資料的曆史通路記錄來進行資料淘汰的，淘汰掉最先通路的資料，其核心思想是 如果資料最近被通路過，那麼将來被通路的幾率也會更加高。

要實作 LRU，需要做到兩點：

查詢出最近最晚使用的項

給最近使用的項做一個标記

實作的方案有多種，這裡小編主要介紹兩種：

LinkedHashMap

雙向連結清單 + HashMap

利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的，預設情況下是按照元素的添加順序存儲的，也可以調整為根據通路順序來調整内部順序（設定參數 accessOrder 進行調整），即最近讀取的資料放在最前面，我們就是利用 LinkedHashMap 的這個特性來實作 LRU。先來一個簡單的例子吧：

運作結果：

更多關于 LinkedHashMap，請看這篇文章：圖解集合6：LinkedHashMap

LinkedHashMap 實作 LRU 有兩種方式，一種是繼承 LinkedHashMap，一種是利用組合的方式，下面分别示範這兩種情況。

采用繼承的方式實作起來是非常簡單的，因為 LinkedHashMap 本身就已經具備了 LRU 的特性，我們隻需要實作一點：當容器中元素個數超過我們設定的容量後，删除第一個元素即可。同時由于 LinkedHashMap 本身不具備線程安全，我們需要確定他線程安全，這個也很簡單，重寫 LinkedHashMap 的 <code>get()</code> 和 <code>put()</code> 方法即可，或者使用 Collections.synchronizedMap() 方法也可以。實作如下：

驗證

運作結果完全符合我們的預期

使用組合的方式可能會更加優雅些，但是由于沒有實作 Map 接口，是以就不能使用 <code>Collections.synchronizedMap()</code> 方式來保證線程安全性了，是以需要在每個方法處增加 synchronized 來確定線程安全。實作方式如下：

驗證：

運作結果如下：

組合的方式也顯得非常簡單，有兩點需要注意：

保證每個方法的線程安全

put 時，需要檢視目前容量是否超過設定的容量，超過則需要删除第一個元素。當然小編這種是實作方式不是很優雅，這麼做知識為了能夠更加好闡述 LRU 的實作。更好的方案是在構造 LinkedHashMap 時，重寫 <code>removeEldestEntry()</code>，如下：

我們想想，在不利用現存資料結構的條件（如 LinkedHashMap）如何實作一個 LRU 呢？緩存部分容易實作，我們都知道利用 HashMap 即可，但是如何實作緩存容量不足時丢棄最不常用的資料的功能？

利用時間戳。每一個通路，增加的元素我們都給其更新一個時間戳，在 put 的時候，檢查，删除時間戳最小的就可以了。這種方法可以實作，但是代價較高，就是我們需要周遊整個資料，得到最小的時間戳。

我們可以換位思考，我們其實不需要關注每個節點的增加或者周遊時間，我們隻需要知道那個節點是最先通路就可以了，是以我們可以利用連結清單記錄通路記錄，有新資料加入時放在連結清單的 head 節點，每次通路也将該資料放在 head 節點，那麼連結清單的 tail 一定是最早通路的節點，是以每次當容量不足的時候删除 tail 節點資料并将它的前驅節點設定為 tail 就可以了。注意，這個連結清單是一個雙向連結清單。代碼如下：

執行結果：

PS:如果你覺得文章對你有所幫助，别忘了推薦或者分享，因為有你的支援，才是我續寫下篇的動力和源泉！

作者：chenssy。一個專注于【死磕 Java】系列創作的男人

出處：https://www.cnblogs.com/chenssy/p/15164873.html

作者個人網站：https://www.cmsblogs.com/。專注于 Java 優質系列文章分享，提供一站式 Java 學習資料

目前死磕系列包括：

    1. 【死磕 Java 并發】：https://www.cmsblogs.com/category/1391296887813967872（已完成）

    2.【死磕 Spring 之 IOC】：https://www.cmsblogs.com/category/1391374860344758272（已完成）

    3.【死磕 Redis】：https://www.cmsblogs.com/category/1391389927996002304（已完成）

    4.【死磕 Java 基礎】：https://www.cmsblogs.com/category/1411518540095295488

    5.【死磕 NIO】：https://www.cmsblogs.com/article/1435620402348036096

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。