如何實現LRU緩存算法

小編給大家分享一下如何實現LRU緩存算法，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

一、什么是緩存

這里說的緩存是一種廣義的概念，在計算機存儲層次結構中，低一層的存儲器都可以看做是高一層的緩存。比如Cache是內存的緩存，內存是硬盤的緩存，硬盤是網絡的緩存等等。

緩存可以有效地解決存儲器性能與容量的這對矛盾，但絕非看上去那么簡單。如果緩存算法設計不當，非但不能提高訪問速度，反而會使系統變得更慢。

從本質上來說，緩存之所以有效是因為程序和數據的局部性（locality）。程序會按固定的順序執行，數據會存放在連續的內存空間并反復讀寫。這些特點使得我們可以緩存那些經常用到的數據，從而提高讀寫速度。

緩存的大小是固定的，它應該只保存最常被訪問的那些數據。然而未來不可預知，我們只能從過去的訪問序列做預測，于是就有了各種各樣的緩存替換策略。本文介紹一種簡單的緩存策略，稱為最近最少使用（LRU，Least Recently Used）算法。

二、LRU的實現

我們以內存訪問為例解釋緩存的工作原理。假設緩存的大小固定，初始狀態為空。每發生一次讀內存操作，首先查找待讀取的數據是否存在于緩存中，若是，則緩存命中，返回數據；若否，則緩存未命中，從內存中讀取數據，并把該數據添加到緩存中。向緩存添加數據時，如果緩存已滿，則需要刪除訪問時間最早的那條數據，這種更新緩存的方法就叫做LRU。

實現LRU時，我們需要關注它的讀性能和寫性能，理想的LRU應該可以在O(1)的時間內讀取一條數據或更新一條數據，也就是說讀寫的時間復雜度都是O(1)。

此時很容易想到使用HashMap，根據數據的鍵訪問數據可以達到O(1)的速度。但是更新緩存的速度卻無法達到O(1)，因為需要確定哪一條數據的訪問時間最早，這需要遍歷所有緩存才能找到。

因此，我們需要一種既按訪問時間排序，又能在常數時間內隨機訪問的數據結構。

這可以通過HashMap+雙向鏈表實現。HashMap保證通過key訪問數據的時間為O(1)，雙向鏈表則按照訪問時間的順序依次穿過每個數據。之所以選擇雙向鏈表而不是單鏈表，是為了可以從中間任意結點修改鏈表結構，而不必從頭結點開始遍歷。

如下圖所示，黑色部分為HashMap的結構，紅色箭頭則是雙向鏈表的正向連接（逆向連接未畫出）。可以清晰地看到，數據的訪問順序是1->3->5->6->10。我們只需要在每次訪問過后改變鏈表的連接順序即可。

HashMap+雙向鏈表

實現代碼如下：

每個方法和成員變量前都有中文注釋，不必過多解釋。

值得一提的是，Java API中其實已經有數據類型提供了我們需要的功能，就是LinkedHashMap這個類。該類內部也是采用HashMap+雙向鏈表實現的。使用這個類實現LRU就簡練多了。

只需要覆寫LinkedHashMap的removeEldestEntry方法，在緩存已滿的情況下返回true，內部就會自動刪除最老的元素。

以上是“如何實現LRU緩存算法”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！