經(jīng)典內(nèi)存算法——LRU、LFU

姓名：譚旭東

學(xué)號：19011210016

嵌牛導(dǎo)讀：經(jīng)典算法——LRU、LFU

嵌牛鼻子：Java

嵌牛提問：內(nèi)存排除算法

轉(zhuǎn)載鏈接：http://182.92.190.128/archives/lrulfu（我的博客）


# 一、LRU算法

## 1. 題目描述

- Least Recently Used——最近最少使用

- 淘汰機制：按照上一次使用時間進(jìn)行淘汰

- 題目出處：[面試題 16.25. LRU 緩存](https://leetcode-cn.com/problems/lru-cache-lcci/)

- 關(guān)鍵實現(xiàn)：

- capacity：容量，大于容量選擇最久未使用資源淘汰

- put()：增加新資源

- get()：獲取/使用資源，會更新資源使用狀況

## 2. 思路

- 使用雙端隊列，久未使用的資源放在隊首，新加入/新使用的資源放在隊尾

- 淘汰時刪除隊首元素即可

- 數(shù)據(jù)結(jié)構(gòu)

- HashMap：用于查詢

- LinkedList：用于構(gòu)建鏈表

## 3. 代碼

### （1）使用JAVA中LinkedHashMap

- 細(xì)節(jié)：

- 刪除元素時，使用迭代器獲取隊首元素

```java

// 1. 使用JAVA自帶API：LinkedHashMap

class LRUCache {

? ? int capacity;

? ? Map<Integer, Integer> map;

? ? public LRUCache(int capacity) {

? ? ? ? this.capacity = capacity;

? ? ? ? map = new LinkedHashMap<>();

? ? }

? ? public int get(int key) {

? ? ? ? if (!map.containsKey(key)) {

? ? ? ? ? ? return -1;

? ? ? ? }

? ? ? ? // 先刪除舊的位置，再放入新位置

? ? ? ? Integer value = map.remove(key);

? ? ? ? map.put(key, value);

? ? ? ? return value;

? ? }

? ? public void put(int key, int value) {

? ? ? ? if (map.containsKey(key)) {

? ? ? ? ? ? map.remove(key);

? ? ? ? ? ? map.put(key, value);

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? map.put(key, value);

? ? ? ? // 超出capacity，刪除最久沒用的,利用迭代器刪除第一個

? ? ? ? if (map.size() > capacity) {

? ? ? ? ? ? map.remove(map.entrySet().iterator().next().getKey());

? ? ? ? }

? ? }

}

```

### （2）自建數(shù)據(jù)結(jié)構(gòu)：HashMap + LinkedList

- 代碼細(xì)節(jié)：

- ① moveToTail功能單獨封裝，put和get中都需要調(diào)用

- ② 在put中調(diào)用get實現(xiàn)復(fù)用

```java

// 2. 自己構(gòu)造 LinkedHashMap + LinkedList(雙鏈表)

class LRUCache2 {

? ? private int capacity;

? ? private Map<Integer, ListNode> map;

? ? private ListNode head;

? ? private ListNode tail;

? ? public LRUCache2(int capacity) {

? ? ? ? this.capacity = capacity;

? ? ? ? this.map = new HashMap<>();

? ? ? ? this.head = new ListNode(-1, -1);

? ? ? ? this.tail = new ListNode(-1, -1);

? ? ? ? head.next = tail;

? ? ? ? tail.pre = head;

? ? }

? ? public int get(int key) {

? ? ? ? if (!map.containsKey(key))

? ? ? ? ? ? return -1;

? ? ? ? ListNode node = map.get(key);

? ? ? ? deleteNode(node);? // 鏈表中刪除節(jié)點

? ? ? ? moveToTail(node);? // 節(jié)點移動到鏈表尾部

? ? ? ? return node.val;

? ? }

? ? public void put(int key, int value) {

? ? ? ? if (get(key) != -1) {? ? ? // 已經(jīng)存在，改變值：在get內(nèi)部會移動到尾部

? ? ? ? ? ? map.get(key).val = value;

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? ListNode node = new ListNode(key, value);

? ? ? ? map.put(key, node);

? ? ? ? moveToTail(node);? ? ? // 放到尾部去

? ? ? ? if (map.size() > capacity) {

? ? ? ? ? ? map.remove(head.next.key);

? ? ? ? ? ? deleteNode(head.next);

? ? ? ? }

? ? }

? ? private void moveToTail(ListNode node) {

? ? ? ? node.next = tail;

? ? ? ? node.pre = tail.pre;

? ? ? ? tail.pre.next = node;

? ? ? ? tail.pre = node;

? ? }

? ? private void deleteNode(ListNode node) {

? ? ? ? node.pre.next = node.next;

? ? ? ? node.next.pre = node.pre;

? ? }

? ? class ListNode {

? ? ? ? int key;

? ? ? ? int val;

? ? ? ? ListNode pre;

? ? ? ? ListNode next;

? ? ? ? public ListNode(int key, int val) {

? ? ? ? ? ? this.key = key;

? ? ? ? ? ? this.val = val;

? ? ? ? ? ? this.pre = null;

? ? ? ? ? ? this.next = null;

? ? ? ? }

? ? }

}

```

# 二、LFU算法

## 1. 題目描述

- Least Frequently Used——最近使用頻次最少

- 淘汰機制：

- ① 按照使用次數(shù)

- ② 如果使用次數(shù)相同，按照使用時間淘汰

- 題目出處：[LeetCode.460. LFU 緩存](https://leetcode-cn.com/problems/lfu-cache/)

- 關(guān)鍵實現(xiàn)：

- put()

- get()

## 2. 思路

- 數(shù)據(jù)結(jié)構(gòu)：

- ① 第一張HashMap，為了查詢資源

![image.png](http://182.92.190.128/upload/2021/08/image-e4b03c91719e4d8688c06b19bc2cfb06.png)

- ② 第二張HashMap，key值按照頻次從小到大，value值為雙向鏈表，保存了同頻次的節(jié)點

![image.png](http://182.92.190.128/upload/2021/08/image-1edc13775f8d411596fac41252681de3.png)

## 3. 代碼

```java

import java.util.HashMap;

import java.util.Map;

/**

*? ? 自定義的LFU緩存類

*/

public class LFUCache {

? ? /**

? ? *? ? 雙鏈表中的鏈表節(jié)點對象

? ? */

? ? protected static class Node{

? ? ? ? //對應(yīng)輸入的key

? ? ? ? private final int key;


? ? ? ? //對應(yīng)輸入的value

? ? ? ? private int value;


? ? ? ? //被訪問的頻率

? ? ? ? private int freq;


? ? ? ? //指向前一個節(jié)點的指針

? ? ? ? protected Node pre;


? ? ? ? //指向后一個節(jié)點的指針

? ? ? ? protected Node next;


? ? ? ? public Node(int key, int value, int freq) {

? ? ? ? ? ? this.key = key;

? ? ? ? ? ? this.value = value;

? ? ? ? ? ? this.freq = freq;

? ? ? ? }


? ? ? ? public Node(int key, int value, int freq, Node pre, Node next) {

? ? ? ? ? ? this.key = key;

? ? ? ? ? ? this.value = value;

? ? ? ? ? ? this.freq = freq;

? ? ? ? ? ? this.pre = null;

? ? ? ? ? ? this.next = null;

? ? ? ? }


? ? ? ? public void updateValue(int value) {

? ? ? ? ? ? this.value = value;

? ? ? ? }


? ? ? ? public void incrFreq() {

? ? ? ? ? ? ++this.freq;

? ? ? ? }


? ? ? ? public int getKey() {

? ? ? ? ? ? return this.key;

? ? ? ? }


? ? ? ? public int getValue() {

? ? ? ? ? ? return this.value;

? ? ? ? }


? ? ? ? public int getFreq() {

? ? ? ? ? ? return this.freq;

? ? ? ? }


? ? ? ? public static final Node createEmptyNode() {

? ? ? ? ? ? return new Node(-1,-1,-1,null,null);

? ? ? ? }

? ? }

? ? /**

? ? *? 自定義的雙向鏈表類

? ? */

? ? protected static class LinkedList {

? ? ? ? //雙向鏈表的頭結(jié)點

? ? ? ? private final Node head;


? ? ? ? //雙向鏈表的尾節(jié)點

? ? ? ? private final Node tail;

? ? ? ? public LinkedList() {

? ? ? ? ? ? this.head = Node.createEmptyNode();

? ? ? ? ? ? this.tail = Node.createEmptyNode();

? ? ? ? ? ? this.head.next = this.tail;

? ? ? ? ? ? this.tail.pre = this.head;

? ? ? ? }


? ? ? ? /**

? ? ? ? * 將指定的節(jié)點插入到鏈表的第一個位置

? ? ? ? * @param node 將要插入的節(jié)點

? ? ? ? */

? ? ? ? public void insertFirst(Node node) {

? ? ? ? ? ? if(node==null) {

? ? ? ? ? ? ? ? throw new IllegalArgumentException();

? ? ? ? ? ? }

? ? ? ? ? ? node.next = this.head.next;

? ? ? ? ? ? this.head.next.pre = node;

? ? ? ? ? ? node.pre = this.head;

? ? ? ? ? ? this.head.next = node;

? ? ? ? }


? ? ? ? /**

? ? ? ? * 從鏈表中刪除指定的節(jié)點

? ? ? ? * @param node 將要刪除的節(jié)點

? ? ? ? */

? ? ? ? public void deleteNode(Node node) {

? ? ? ? ? ? if(node==null) {

? ? ? ? ? ? ? ? throw new IllegalArgumentException();

? ? ? ? ? ? }

? ? ? ? ? ? node.pre.next = node.next;

? ? ? ? ? ? node.next.pre = node.pre;

? ? ? ? ? ? node.pre = null;

? ? ? ? ? ? node.next = null;

? ? ? ? }


? ? ? ? /**

? ? ? ? * 從鏈表中獲取最后一個節(jié)點

? ? ? ? * @return 雙向鏈表中的最后一個節(jié)點，如果是空鏈表則返回None

? ? ? ? */

? ? ? ? public Node getLastNode() {

? ? ? ? ? ? if(this.head.next==this.tail) {

? ? ? ? ? ? ? ? return Node.createEmptyNode();

? ? ? ? ? ? }

? ? ? ? ? ? return this.tail.pre;

? ? ? ? }


? ? ? ? /**

? ? ? ? * 判斷鏈表是否為空，除了head和tail沒有其他節(jié)點即為空鏈表

? ? ? ? * @return 鏈表不空返回True，否則返回False

? ? ? ? */

? ? ? ? public boolean isEmpty() {

? ? ? ? ? ? return this.head.next==this.tail;

? ? ? ? }

? ? }

? ? //key->Node 這種結(jié)構(gòu)的哈希表

? ? private final Map<Integer,Node> keyMap = new HashMap<Integer,Node>();

? ? //freq->LinkedList 這種結(jié)構(gòu)的哈希表

? ? private final Map<Integer,LinkedList> freqMap = new HashMap<Integer,LinkedList>();

? ? //緩存的最大容量

? ? private final int capacity;

? ? //記錄緩存中最低頻率

? ? private int minFreq = 0;

? ? public LFUCache(int capacity) {

//? if(capacity<=0) {

//? throw new IllegalArgumentException();

//? }

? ? ? ? this.capacity = capacity;

? ? }


? ? /**

? ? * 獲取一個元素，如果key不存在則返回-1，否則返回對應(yīng)的value，同時更新被訪問元素的頻率

? ? * @param key 要查找的關(guān)鍵字

? ? * @return 如果沒找到則返回-1，否則返回對應(yīng)的value

? ? */

? ? public int get(int key) {

? ? ? ? if(!this.keyMap.containsKey(key)) {

? ? ? ? ? ? return -1;

? ? ? ? }

? ? ? ? Node node = this.keyMap.get(key);

? ? ? ? this.increment(node);

? ? ? ? return node.getValue();

? ? }


? ? /**

? ? * 插入指定的key和value，如果key存在則更新value，同時更新頻率，

? ? * 如果key不存并且緩存滿了，則刪除頻率最低的元素，并插入新元素。否則，直接插入新元素

? ? * @param key 要插入的關(guān)鍵字

? ? * @param value 要插入的值

? ? */

? ? public void put(int key, int value) {

? ? ? ? if(this.keyMap.containsKey(key)) {

? ? ? ? ? ? Node node = this.keyMap.get(key);

? ? ? ? ? ? node.updateValue(value);

? ? ? ? ? ? this.increment(node);

? ? ? ? }

? ? ? ? else {

? ? ? ? ? ? if(this.capacity==0) {

? ? ? ? ? ? ? ? return;

? ? ? ? ? ? }

? ? ? ? ? ? if(this.keyMap.size()==this.capacity) {

? ? ? ? ? ? ? ? this.remoteMinFreqNode();

? ? ? ? ? ? }

? ? ? ? ? ? Node node = new Node(key,value,1);

? ? ? ? ? ? this.increment(node,true);

? ? ? ? ? ? this.keyMap.put(key, node);

? ? ? ? }

? ? }


? ? /**

? ? *? 更新節(jié)點的訪問頻率

? ? * @param node 要更新的節(jié)點

? ? */

? ? private void increment(Node node) {

? ? ? ? increment(node,false);

? ? }


? ? /**

? ? * 更新節(jié)點的訪問頻率

? ? * @param node 要更新的節(jié)點

? ? * @param isNewNode 是否是新節(jié)點，新插入的節(jié)點和非新插入節(jié)點更新邏輯不同

? ? */

? ? private void increment(Node node,boolean isNewNode) {

? ? ? ? if(isNewNode) {

? ? ? ? ? ? this.minFreq = 1;

? ? ? ? ? ? this.insertToLinkedList(node);

? ? ? ? }

? ? ? ? else {

? ? ? ? ? ? this.deleteNode(node);

? ? ? ? ? ? node.incrFreq();

? ? ? ? ? ? this.insertToLinkedList(node);

? ? ? ? ? ? if(!this.freqMap.containsKey(this.minFreq)) {

? ? ? ? ? ? ? ? ++this.minFreq;

? ? ? ? ? ? }

? ? ? ? }

? ? }


? ? /**

? ? * 根據(jù)節(jié)點的頻率，插入到對應(yīng)的LinkedList中，如果LinkedList不存在則創(chuàng)建

? ? * @param node 將要插入到LinkedList的節(jié)點

? ? */

? ? private void insertToLinkedList(Node node) {

? ? ? ? if(!this.freqMap.containsKey(node.getFreq())) {

? ? ? ? ? ? this.freqMap.put(node.getFreq(), new LinkedList());

? ? ? ? }

? ? ? ? LinkedList linkedList = this.freqMap.get(node.getFreq());

? ? ? ? linkedList.insertFirst(node);

? ? }


? ? /**

? ? * 刪除指定的節(jié)點，如果節(jié)點刪除后，對應(yīng)的雙鏈表為空，則從__freqMap中刪除這個鏈表

? ? * @param node 將要刪除的節(jié)點

? ? */

? ? private void deleteNode(Node node) {

? ? ? ? LinkedList linkedList = this.freqMap.get(node.getFreq());

? ? ? ? linkedList.deleteNode(node);

? ? ? ? if(linkedList.isEmpty()) {

? ? ? ? ? ? this.freqMap.remove(node.getFreq());

? ? ? ? }

? ? }


? ? /**

? ? * 刪除頻率最低的元素，從freqMap和keyMap中都要刪除這個節(jié)點，

? ? * 如果節(jié)點刪除后對應(yīng)的鏈表為空，則要從__freqMap中刪除這個鏈表

? ? */

? ? private void remoteMinFreqNode() {

? ? ? ? LinkedList linkedList = this.freqMap.get(this.minFreq);

? ? ? ? Node node = linkedList.getLastNode();

? ? ? ? linkedList.deleteNode(node);

? ? ? ? this.keyMap.remove(node.getKey());

? ? ? ? if(linkedList.isEmpty()) {

? ? ? ? ? ? this.freqMap.remove(node.getFreq());

? ? ? ? }

? ? }

}

```

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • LRU究竟是個什么東西呢，聽上去是那么的高大上。Least Recently Used就是LRU的真面目，翻譯...
    宮若石閱讀 1,048評論 0贊 1
  • 單例定義：保證一個類僅有一個實例，并提供一個訪問它的全局訪問點。餓漢模式public class Singleto...
    小楊不想努力了閱讀 568評論 0贊 4
  • 設(shè)原始數(shù)據(jù)規(guī)模為n，需要采樣的數(shù)量為k 先選取數(shù)據(jù)流中的前k個元素，保存在集合A中； 從第j（k + 1 <= j...
    Impossible安徒生閱讀 343評論 0贊 0
  • 面試騰訊遇到的算法題。 眾所周知，LRU本質(zhì)就是一個哈希表+雙向鏈表的組合數(shù)據(jù)結(jié)構(gòu)，java中l(wèi)inkedHash...
    AspirantPeng閱讀 795評論 0贊 0
  • 第三章 Java 1.HashMap 1）HashMap的數(shù)據(jù)結(jié)構(gòu)？ 哈希表結(jié)構(gòu)(鏈表散列：數(shù)組+鏈表)實現(xiàn)，結(jié)合...
    Amy木婉清閱讀 428評論 0贊 0

友情鏈接更多精彩內(nèi)容