一、什么是 LRU 算法

就是一種緩存淘汰策略。

計(jì)算機(jī)的緩存容量有限，如果緩存滿了就要?jiǎng)h除一些內(nèi)容，給新內(nèi)容騰位置。但問(wèn)題是，刪除哪些內(nèi)容呢？我們肯定希望刪掉哪些沒(méi)什么用的緩存，而把有用的數(shù)據(jù)繼續(xù)留在緩存里，方便之后繼續(xù)使用。

LRU是Least Recently Used的縮寫(xiě)，即最近最少使用，是一種常用的頁(yè)面置換算法，選擇最近最久未使用的頁(yè)面予以淘汰。

二、LRU的使用

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 該操作會(huì)使得密鑰 2 作廢

第一步：創(chuàng)建一個(gè)長(zhǎng)度為2的LRUCache

第二步：cache.put(1, 1);放入key=1，value=1的數(shù)據(jù)

第三步：cache.put(2，2);放入key = 2，value = 2的數(shù)據(jù)(因?yàn)?剛使用，所有把2移動(dòng)到前面）

第四步：cache.get(1);獲取key = 1的數(shù)據(jù)（因?yàn)槲覀儎偸褂昧?，所以把1移動(dòng)到前面）

第五步：cache.put(3，3);放入key = 3，value = 3的數(shù)據(jù)（因?yàn)?剛放進(jìn)，所以放前面，又因?yàn)槿萘恐挥?，需要移除原先的1個(gè)。只因key = 2是最近最少使用的（key = 1剛get()過(guò))，所以移除2。

三、LRU的實(shí)現(xiàn)機(jī)制

算法：

LRU 緩存機(jī)制可以通過(guò)哈希表輔以雙向鏈表實(shí)現(xiàn)，我們用一個(gè)哈希表和一個(gè)雙向鏈表維護(hù)所有在緩存中的鍵值對(duì)。

1）雙向鏈表按照被使用的順序存儲(chǔ)了這些鍵值對(duì)，靠近頭部的鍵值對(duì)是最近使用的，而靠近尾部的鍵值對(duì)是最久未使用的。

2）哈希表即為普通的哈希映射（HashMap），通過(guò)緩存數(shù)據(jù)的鍵映射到其在雙向鏈表中的位置。

一、初始化：

二、cache.put(1，1)：

三、cache.put(2，2)：

四、cache.get(1)：

五、cache.put(3,3)：

四、代碼如下

import java.io.*;import java.util.HashMap;public class test { public static void main(String args[]) throws IOException { LRUCache cache = new LRUCache( 2 /* 緩存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 該操作會(huì)使得密鑰 2 作廢 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 該操作會(huì)使得密鑰 1 作廢 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4 }}/** * 設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫(xiě)入數(shù)據(jù) put */class LRUCache { private HashMap<Integer,LinkedNode> cache = new HashMap();//方便通過(guò)key快速定位結(jié)點(diǎn) private int size; private int capacity; private LinkedNode head,tail; class LinkedNode{ int key; int value; LinkedNode pre; LinkedNode next; } public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new LinkedNode(); tail = new LinkedNode(); head.next = tail; tail.pre = head; } /** * 移除節(jié)點(diǎn) * @param node */ private void removeNode(LinkedNode node) { LinkedNode preNode = node.pre; LinkedNode nextNode = node.next; preNode.next = nextNode; nextNode.pre = preNode; } /** * 添加節(jié)點(diǎn)到頭部 * @param node */ private void addNode(LinkedNode node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; } /** * 將節(jié)點(diǎn)移動(dòng)到頭部 * @param node */ private void moveToHead(LinkedNode node) { removeNode(node); addNode(node); } /** * 獲取數(shù)據(jù) * @param key * @return */ public int get(int key) { LinkedNode node = cache.get(key); if(node != null) { moveToHead(node); }else{ return -1; } return node.value; } /** * 寫(xiě)入數(shù)據(jù) * @param key * @param value */ public void put(int key, int value) { LinkedNode node = cache.get(key); //存在 if(node != null) { node.value = value;//可能更新數(shù)據(jù) moveToHead(node); } //不存在 else{ LinkedNode newNode = new LinkedNode(); newNode.key = key; newNode.value = value; cache.put(key,newNode);//更新Map addNode(newNode);//添加結(jié)點(diǎn)到頭部 size++;//更新結(jié)點(diǎn)數(shù) if(size > capacity) {//如果結(jié)點(diǎn)數(shù)超過(guò)容量大小LinkedNode tailPre = tail.pre;cache.remove(tailPre.key);//更新MapremoveNode(tailPre);//刪除最后一個(gè)結(jié)點(diǎn)（尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)）size--; } } }}

總結(jié)：自己實(shí)現(xiàn)的簡(jiǎn)單LRU總歸太簡(jiǎn)單了，要是想完善或者實(shí)現(xiàn)更真實(shí)的LRU，不妨參考一下Redis中的LRU。(◔◡◔)

到此這篇關(guān)于Java實(shí)現(xiàn)簡(jiǎn)單LRU緩存機(jī)制的方法的文章就介紹到這了,更多相關(guān)Java LRU緩存內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！