LRU全稱是Least?Recently Used，即最近最久未使用的意思。

LRU算法的設(shè)計(jì)原則是：如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒(méi)有被訪問(wèn)到，那么在將來(lái)它被訪問(wèn)的可能性也很小。也就是說(shuō)，當(dāng)限定的空間已存滿數(shù)據(jù)時(shí)，應(yīng)當(dāng)把最久沒(méi)有被訪問(wèn)到的數(shù)據(jù)淘汰。（這一段是找的，讓大家理解一下什么是LRU）。

?

說(shuō)一下我們什么時(shí)候見到過(guò)LRU：其實(shí)老師們肯定都給大家舉過(guò)這么個(gè)例子：你在圖書館，你把書架子里的書拿到桌子上。。但是桌子是有限的，你有時(shí)候不得不把一些書放回去。這就相當(dāng)于內(nèi)存和硬盤。這個(gè)例子都說(shuō)過(guò)吧？

LRU就是記錄你最長(zhǎng)時(shí)間沒(méi)看過(guò)的書，就把它放回去。在cache那里見過(guò)吧

?

然后最近在研究redis，又看到了這個(gè)LRU，所以就想寫一下吧。

題目：設(shè)計(jì)一個(gè)結(jié)構(gòu)，這個(gè)結(jié)構(gòu)可以查詢K-V，但是容量有限，當(dāng)存不下的時(shí)候就要把用的年代最久遠(yuǎn)的那個(gè)東西扔掉。

其實(shí)思路很簡(jiǎn)單，我們維護(hù)一個(gè)雙向鏈表即可，get也就是使用了，我們就把把它提到最安全的位置。新來(lái)的KV就依次放即可。

我們就先寫這個(gè)雙向鏈表結(jié)構(gòu)

先寫節(jié)點(diǎn)結(jié)構(gòu)：

public static class Node<V> {public V value;public Node<V> last;//前public Node<V> next;//后public Node(V value) {this.value = value;}}

然后寫雙向鏈表結(jié)構(gòu)： 我們沒(méi)必要把鏈表操作都寫了，分析一下，我們只有三個(gè)操作：

1、加節(jié)點(diǎn)

2、使用了某個(gè)節(jié)點(diǎn)就把它調(diào)到尾，代表優(yōu)先級(jí)最高

3、把優(yōu)先級(jí)最低的移除，也就是去頭部

（不會(huì)的，翻我之前的鏈表操作都有寫）

public static class NodeDoubleLinkedList<V> {private Node<V> head;//頭private Node<V> tail;//尾public NodeDoubleLinkedList() {this.head = null;this.tail = null;}public void addNode(Node<V> newNode) {if (newNode == null) {return;}if (this.head == null) {//頭空this.head = newNode;this.tail = newNode;} else {//頭不空this.tail.next = newNode;newNode.last = this.tail;//注意讓本節(jié)點(diǎn)前指針指向舊尾this.tail = newNode;//指向新尾}} /*某個(gè)點(diǎn)移到最后*/public void moveNodeToTail(Node<V> node) {if (this.tail == node) {//是尾return;}if (this.head == node) {//是頭this.head = node.next;this.head.last = null;} else {//中間node.last.next = node.next;node.next.last = node.last;}node.last = this.tail;node.next = null;this.tail.next = node;this.tail = node;} /*刪除第一個(gè)*/public Node<V> removeHead() {if (this.head == null) {return null;}Node<V> res = this.head;if (this.head == this.tail) {//就一個(gè)this.head = null;this.tail = null;} else {this.head = res.next;res.next = null;this.head.last = null;}return res;}}

鏈表操作封裝完了就要實(shí)現(xiàn)這個(gè)結(jié)構(gòu)了。

具體思路代碼注釋

public static class MyCache<K, V> {//為了kv or vk都能查private HashMap<K, Node<V>> keyNodeMap;private HashMap<Node<V>, K> nodeKeyMap;//用來(lái)做優(yōu)先級(jí)private NodeDoubleLinkedList<V> nodeList;private int capacity;//容量public MyCache(int capacity) {if (capacity < 1) {//你容量連1都不給，搗亂呢throw new RuntimeException("should be more than 0.");}this.keyNodeMap = new HashMap<K, Node<V>>();this.nodeKeyMap = new HashMap<Node<V>, K>();this.nodeList = new NodeDoubleLinkedList<V>();this.capacity = capacity;}public V get(K key) {if (this.keyNodeMap.containsKey(key)) {Node<V> res = this.keyNodeMap.get(key);this.nodeList.moveNodeToTail(res);//使用過(guò)了就放到尾部return res.value;}return null;}public void set(K key, V value) {if (this.keyNodeMap.containsKey(key)) {Node<V> node = this.keyNodeMap.get(key);node.value = value;//放新vthis.nodeList.moveNodeToTail(node);//我們認(rèn)為放入舊key也是使用過(guò)} else {Node<V> newNode = new Node<V>(value);this.keyNodeMap.put(key, newNode);this.nodeKeyMap.put(newNode, key);this.nodeList.addNode(newNode);//加進(jìn)去if (this.keyNodeMap.size() == this.capacity + 1) {this.removeMostUnusedCache();//放不下就去掉優(yōu)先級(jí)最低的}}}private void removeMostUnusedCache() {//刪除頭Node<V> removeNode = this.nodeList.removeHead();K removeKey = this.nodeKeyMap.get(removeNode);//刪除掉兩個(gè)map中的記錄this.nodeKeyMap.remove(removeNode);this.keyNodeMap.remove(removeKey);}}

?

總結(jié)

以上是生活随笔為你收集整理的LRU介绍和实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。