• 实现 LRU 缓存算法

    1 LRU 缓存介绍

    LRU 算法全称是最近最少使用算法（Least Recently Use），是一种简单的缓存策略。顾名思义，LRU 算法会选出最近最少使用的数据进行淘汰。

    那么什么是缓存呢？缓存专业点可以叫一种提高数据读取性能的技术，可以有效解决存储器性能和容量的矛盾，是一种空间换时间的设计思想，比如我们常见的内存是硬盘的缓存，Cache 是内存的缓存，浏览器本地存储是网络访问的缓存…

    LRU 有许多应用场景，例如：

    1. 操作系统底层的内存管理。
    2. 缓存服务，例如 Redis，当数据满的时候就要淘汰掉长期不使用的 key，在 Redis 中用了一个类似的 LRU 算法，而不是严格的 LRU 算法。
    3. MySQL 的 Buffer Pool，也就是缓冲池，它的目的是为了减少磁盘 IO。它是一块连续的内存，当 Buffer Pool 满的时候就要淘汰很久没有被访问过的页。

    2 Leetcode 真题

    146. LRU 缓存 [1]，请你设计并实现一个满足  LRU (最近最少使用) 缓存约束的数据结构。

    实现 LRUCache 类：

    • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。
    • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

    示例：

    输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    3 题目分析

    • 1.首先，题目中提到函数 get 和 put 必须以 O(1) 的平均时间复杂度运行，很自然地我们可以想到应该使用哈希表。
    • 2.其次，当访问数据结构中的某个 key 时，需要将这个 key 更新为最近使用；另外如果 capacity 已满，需要删除访问时间最早的那条数据。这要求数据是有序的，并且可以支持在任意位置快速插入和删除元素，链表可以满足这个要求。
    • 3.结合 1，2 两点来看，我们可以采用哈希表 + 链表的结构实现 LRU 缓存。

    如上图所示，就是哈希表 + 链表实现的 LRU 缓存数据结构，有以下几个问题解释一下：

    • 1.为什么这里要使用双向链表，而不是单向链表？
      我们在找到了节点，需要删除节点的时候，如果使用单向链表的话，后驱节点的指针是直接能拿到的，但是这里要求时间复杂度是 O(1)，要能够直接获取到前驱节点的指针，那么只能使用双向链表。
    • 2.哈希表里面已经保存了 key ，那么链表中为什么还要存储 key 和 value 呢，只存入 value 不就行了？
      当我们删除节点的时候，除了需要删除链表中的节点，还需要删除哈希表中的节点。删除哈希表中的节点需要知道 key，所以在链表的节点中需要存储 key 和 value，当删除链表节点时拿到 key，再根据 key 到哈希表中删除节点。
    • 3.虚拟头节点和虚拟尾节点有什么用？
      虚拟节点在链表中被广泛应用，又称为哨兵节点，通常不保存任何数据。使用虚拟节点我们可以统一处理链表中所有节点的插入删除操作，而不用考虑头尾两个节点的特殊情况。

    4 代码实现

    4.1 Golang

    package main

import "fmt"

// LRU 数据结构
type LRUCache struct {
	capacity   int                  // 容量
	size       int                  // 已使用空间
	head, tail *DLinkedNode         // 头节点，尾节点
	cache      map[int]*DLinkedNode // 哈希表
}

// 双向链表数据结构
type DLinkedNode struct {
	key, value int
	prev, next *DLinkedNode // 前指针，后指针
}

// 创建一个新的节点
func initDLinkedNode(key, value int) *DLinkedNode {
	return &DLinkedNode{
		key:   key,
		value: value,
	}
}

// 初始化 LRU 结构
func Constructor(capacity int) LRUCache {
	l := LRUCache{
		cache:    map[int]*DLinkedNode{}, //  哈希表
		head:     initDLinkedNode(0, 0),  // 虚拟头节点
		tail:     initDLinkedNode(0, 0),  // 虚拟尾节点
		capacity: capacity,               // 容量
	}
	// 虚拟头节点和虚拟尾节点互连
	l.head.next = l.tail
	l.tail.prev = l.head
	return l
}

// 获取元素
func (this *LRUCache) Get(key int) int {
	// 如果没有在哈希表中找到 key
	if _, ok := this.cache[key]; !ok {
		return -1
	}
	// 如果 key 存在，先通过哈希表定位，再移到头部
	node := this.cache[key]
	this.moveToHead(node)
	return node.value
}

// 插入元素
func (this *LRUCache) Put(key int, value int) {
	// 先去哈希表中查询
	// 如果 key 不存在，创建一个新的节点
	if node, ok := this.cache[key]; !ok {
		newNode := initDLinkedNode(key, value)
		// 如果达到容量限制，链表删除尾部节点，哈希表删除元素
		this.size++
		if this.size > this.capacity {
			// 得到删除的节点
			removed := this.removeTail()
			// 根据得到的 key 删除哈希表中的元素
			delete(this.cache, removed.key)
			// 减少已使用容量
			this.size--
		}
		// 插入哈希表
		this.cache[key] = newNode
		// 插入链表
		this.addToHead(newNode)
	} else { // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
		node.value = value
		this.moveToHead(node)
	}
}

// 将节点添加到头部
func (this *LRUCache) addToHead(node *DLinkedNode) {
	// 新节点指向前后节点
	node.prev = this.head
	node.next = this.head.next
	
	// 前后节点指向新节点
	this.head.next.prev = node
	this.head.next = node
}

// 删除该节点
func (this *LRUCache) removeNode(node *DLinkedNode) {
	// 修改该节点前后节点的指针，不再指向该节点
	node.next.prev = node.prev
	node.prev.next = node.next
}

// 移动到头部，也就是当前位置删除，再添加到头部
func (this *LRUCache) moveToHead(node *DLinkedNode) {
	this.removeNode(node)
	this.addToHead(node)
}

// 移除尾部节点，淘汰最久未使用的
func (this *LRUCache) removeTail() *DLinkedNode {
	node := this.tail.prev // 虚拟尾节点的上一个才是真正的尾节点
	this.removeNode(node)
	return node
}

// 打印链表（解题不需要此方法，只是为了显示效果）
func (this *LRUCache) printDLinkedNode() {
	p := this.head
	for p != nil {
		fmt.Printf("key: %d, value: %d\n", p.key, p.value)
		p = p.next
	}
}
func main() {
	lru := Constructor(3)
	fmt.Println("=========================== 插入 3 个节点 ===========================")
	lru.Put(1, 100)
	lru.Put(2, 200)
	lru.Put(3, 300)
	fmt.Println("=========================== 打印当前链表 ===========================")
	lru.printDLinkedNode()

	fmt.Println("=========================== 插入第 4 个节点，LRU 缓存淘汰尾部节点 ===========================")
	lru.Put(4, 400)
	lru.printDLinkedNode()

	fmt.Println("=========================== 获取 key2 节点，更新 LRU 缓存，将会移动至链表头部 ===========================")
	lru.Get(2)
	lru.printDLinkedNode()
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135

    4.2 Java

    import java.util.HashMap;  
import java.util.Map;  
  
public class LRUCache {  
    // 双向链表  
    class DLinkedNode {  
        int key;  
        int value;  
        DLinkedNode prev;  
        DLinkedNode next;  
  
        public DLinkedNode() {  
        }  
        public DLinkedNode(int key, int value) {  
            this.key = key;  
            this.value = value;  
        }  
    }  
    // 哈希表  
    private Map<Integer, DLinkedNode> cache = new HashMap<>();  
    // 已使用空间  
    private int size;  
    // 容量  
    private int capacity;  
    // 头节点，尾节点  
    private DLinkedNode head, tail;  
  
    public LRUCache(int capacity) {  
        this.size = 0;  
        this.capacity = capacity;  
        // 使用虚拟头部和虚拟尾部节点  
        head = new DLinkedNode();  
        tail = new DLinkedNode();  
        // 虚拟头节点和虚拟尾节点互连  
        head.next = tail;  
        tail.prev = head;  
    }  
  
    // 获取元素  
    public int get(int key) {  
        DLinkedNode node = cache.get(key);  
        // 如果没有在哈希表中找到 key  
        if (node == null) {  
            return -1;  
        }  
        // 如果 key 存在，先通过哈希表定位，再移到头部  
        moveToHead(node);  
        return node.value;  
    }  
  
    // 插入元素  
    public void put(int key, int value) {  
        DLinkedNode node = cache.get(key);  
        if (node == null) {  
            // 如果 key 不存在，创建一个新的节点  
            DLinkedNode newNode = new DLinkedNode(key, value);  
            // 如果达到容量限制，链表删除尾部节点，哈希表删除元素  
            size++;  
            if (size > capacity) {  
                // 得到删除的节点  
                DLinkedNode removed = removeTail();  
                // 根据得到的 key 删除哈希表中的元素  
                cache.remove(removed.key);  
                // 减少已使用容量  
                size--;  
            }  
            // 插入哈希表  
            cache.put(key, newNode);  
            // 添加至双链表的头部  
            addToHead(newNode);  
        } else {  
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部  
            node.value = value;  
            moveToHead(node);  
        }  
    }  
    // 将节点添加到链表头部  
    private void addToHead(DLinkedNode node) {  
        // 新节点指向前后节点  
        node.prev = head;  
        node.next = head.next;  
        // 前后节点指向新节点  
        head.next.prev = node;  
        head.next = node;  
    }  
  
    // 删除节点  
    private void removeNode(DLinkedNode node) {  
        // 修改该节点前后节点的指针，不再指向该节点  
        node.prev.next = node.next;  
        node.next.prev = node.prev;  
    }  
  
    // 移动到头部，也就是当前位置删除，再添加到头部  
    private void moveToHead(DLinkedNode node) {  
        removeNode(node);  
        addToHead(node);  
    }  
  
    // 移除尾部节点，淘汰最久未使用的  
    private DLinkedNode removeTail() {  
        DLinkedNode res = tail.prev; // 虚拟尾节点，prev 才是此时真正的尾节点  
        removeNode(res);  
        return res;  
    }  
  
    // 打印链表（解题不需要此方法，只是为了显示效果）  
    private void printDLinkedNode() {  
        DLinkedNode p = this.head;  
        while (p != null) {  
            System.out.printf("key: %d, value: %d\n", p.key, p.value);  
            p = p.next;  
        }  
    }  
    public static void main(String[] args) {  
        LRUCache lru = new LRUCache(3);  
        System.out.println("=========================== 插入 3 个节点 ===========================");  
        lru.put(1, 100);  
        lru.put(2, 200);  
        lru.put(3, 300);  
        System.out.println("=========================== 打印当前链表 ===========================");  
        lru.printDLinkedNode();  
  
        System.out.println("=========================== 插入第 4 个节点，LRU 缓存淘汰尾部节点 key1 ===========================");  
        lru.put(4, 400);  
        lru.printDLinkedNode();  
  
        System.out.println("=========================== 获取 key2 的节点，更新 LRU 缓存，将会移动至链表头部 ===========================");  
        lru.get(2);  
        lru.printDLinkedNode();  
    }  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132

    4.3 运行结果

    代码运行的返回结果如下，其中头尾两个 key=0, value=0 的节点是虚拟节点，请忽略。

    =========================== 插入 3 个节点 ===========================
=========================== 打印当前链表 ===========================
key: 0, value: 0
key: 3, value: 300
key: 2, value: 200
key: 1, value: 100
key: 0, value: 0
=========================== 插入第 4 个节点，LRU 缓存淘汰尾部节点 ===========================
key: 0, value: 0
key: 4, value: 400
key: 3, value: 300
key: 2, value: 200
key: 0, value: 0
=========================== 获取 key2 节点，更新 LRU 缓存，将会移动至链表头部 ===========================
key: 0, value: 0
key: 2, value: 200
key: 4, value: 400
key: 3, value: 300
key: 0, value: 0


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    5 测试案例示意图

    第 1 步：初始化数据结构。

    第 2 步：插入节点 key1。

    第 3 步：插入节点 key2。 此时 key2 插入到链表头部。

    第 4 步：插入节点 key3。 此时 key3 插入到链表头部。

    第 5 步：插入节点 key4。当前 capacity 容量达到上限（3），分为 2 步：

    使用 removeTail() 方法删除链表尾部的节点 key1，从 removeTail() 方法的返回值得到 node，再根据 node.key 得到 key1，然后去哈希表删除节点 key1。

    然后插入节点 key4，此时 key4 在链表头部。

    第 6 步：读取 key2 的值，将 key2 移动到链表头部。

    6 参考资料

    • [1] 146. LRU 缓存: https://leetcode.cn/problems/lru-cache/
    • [2] 以Leetcode第146题为例学习LRU缓存算法: https://mp.weixin.qq.com/s/nI-rp3zTtei3TFIoBDcr5Q
    • [3] 从leetcode真题讲解手写LRU算法: http://www.xiaojieboshi.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E4%BB%8Eleetcode%E7%9C%9F%E9%A2%98%E8%AE%B2%E8%A7%A3%E6%89%8B%E5%86%99LRU%E7%AE%97%E6%B3%95.html#%E5%89%8D%E8%A8%80
    • [4] LRU缓存机制: https://leetcode.cn/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
    • [5] Java集合系列之LinkedHashMap: https://juejin.cn/post/6844903544152129550
    • [6] LinkedHashMap基本原理和用法&使用实现简单缓存： https://www.cnblogs.com/myseries/p/10774487.html
    • [7] LRU算法及其优化策略——算法篇: https://juejin.cn/post/6844904049263771662#heading-3

    7 欢迎关注

  • 相关阅读:
    java计算机毕业设计springboot+vue专业手语翻译预约系统
    【Python】pyecharts 模块 ⑥ ( 绘制柱状图 | pyecharts 绘制柱状图步骤 | 柱状图 x 轴 / y 轴 翻转 | 柱状图数据标签位置设置 )
    evnoy协议转换关键日志
    Linux开发工具之编辑器-vim
    Linux系统访问卡顿 慢
    华钜同创：亚马逊开店六个日常运营小技巧
    Spring-IoC源码分析
    Android 12 桌面去掉搜索框和 隐藏设置搜索框 隐藏应用页的搜索框
    从零开始的C++（十五）
    代码圈复杂度治理小结
  • 原文地址：https://blog.csdn.net/cr7258/article/details/124841521