LRU

LRU（Least Recently Used）是一种常见的缓存替换算法，主要用于管理缓存中的数据。当缓存达到容量限制时，LRU算法会选择最久未被访问的数据进行淘汰，从而为新数据腾出空间。

工作原理

LRU算法基于“最近最少使用”策略，通过跟踪数据的访问顺序来判断哪些数据最不常用。每当数据被访问时，它就会被移动到缓存的最前面或标记为最近使用。缓存满时，LRU会删除最久没有被访问的数据。

实现方式

LRU缓存通常通过双向链表和哈希表结合实现，具体步骤如下：

1. 哈希表：通过哈希表快速查找缓存中的数据。

2. 双向链表：通过双向链表保持数据的访问顺序。链表的尾部表示最近使用的数据，头部表示最久未使用的数据。

• 增加虚拟头节点和虚拟尾节点，不存储数据。

• 当数据被访问时，将该数据节点移动到链表的尾部。（本文代码将被访问的数据移动至尾部）

• 当缓存满时，删除链表头部的节点。

• LRU缓存：通过Golang中的map和自定义的双向链表实现。

• 访问数据判断数据是否存在

• 存在，覆盖数据，将数据移动到链表尾部，表示最近访问。

• 不存在，返回错误

• 插入数据判断数据是否存在

• 存在，删除旧数据，创建新数据

• 不存在，创建新数据

节点结构

// 节点结构
type Node struct {
	key, val   int
	next, prev *Node
}

func NewNode(k, v int) *Node {
	return &Node{key: k, val: v}
}

双向链表结构及对应方法

// 双链表
type DoubleList struct {
	head, tail *Node
	size       int
}

func NewDoubleList() *DoubleList {
	head := &Node{key: 0, val: 0}
	tail := &Node{key: 0, val: 0}
	head.next, tail.prev = tail, head
	return &DoubleList{head: head, tail: tail, size: 0}
}

// 在链表尾部添加节点x, 时间O(1)
// 将x插入尾节点之前
func (this *DoubleList) AddLast(x *Node) {
	x.prev = this.tail.prev
	x.next = this.tail
	this.tail.prev.next = x
	this.tail.prev = x
	this.size++
}

// 删除链表中的x节点（x一定存在）
func (this *DoubleList) Remove(x *Node) {
	x.prev.next = x.next
	x.next.prev = x.prev
	this.size--
}

// 删除链表中的第一个节点，并返回该节点，时间O(1)
func (this *DoubleList) RemoveFirst() *Node {
	if this.head.next == this.tail {
		return nil
	}
	first := this.head.next
	this.Remove(first)
	return first
}

// 返回链表长度
func (this *DoubleList) Size() int {
	return this.size
}

LRU缓存及方法

// 构建缓存结构体
type LRUCache struct {
	_map  map[int]*Node
	cache *DoubleList
	// 最大容量
	cap int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		_map:  make(map[int]*Node),
		cache: NewDoubleList(),
		cap:   capacity,
	}
}

// 将某个key提升为最近使用的
func (this *LRUCache) makeRecently(key int) {
	x := this._map[key]
	this.cache.Remove(x)
	this.cache.AddLast(x)
}

// 添加最近使用的元素
func (this *LRUCache) addRecently(key, val int) {
	x := NewNode(key, val)
	this.cache.AddLast(x)
	this._map[key] = x
}

// 删除某个key
func (this *LRUCache) deleteKey(key int) {
	x := this._map[key]
	this.cache.Remove(x)
	delete(this._map, key)
}

// 删除最久未使用（头节点）元素
func (this *LRUCache) removeLeaseRecently() {
	x := this.cache.RemoveFirst()
	delete(this._map, x.key)
}

func (this *LRUCache) Get(key int) int {
	if _, ok := this._map[key]; !ok {
		return -1
	}
	this.makeRecently(key)
	return this._map[key].val
}

func (this *LRUCache) Put(key, val int) {
	if _, ok := this._map[key]; ok {
		// 删除旧的节点
		this.deleteKey(key)
		this.addRecently(key, val)
		return
	}

	if this.cap == this.cache.Size() {
		this.removeLeaseRecently()
	}

	this.addRecently(key, val)
}

完整代码

package main

import "fmt"

// 节点结构
type Node struct {
	key, val   int
	next, prev *Node
}

func NewNode(k, v int) *Node {
	return &Node{key: k, val: v}
}

// 双链表
type DoubleList struct {
	head, tail *Node
	size       int
}

func NewDoubleList() *DoubleList {
	head := &Node{key: 0, val: 0}
	tail := &Node{key: 0, val: 0}
	head.next, tail.prev = tail, head
	return &DoubleList{head: head, tail: tail, size: 0}
}

// 在链表尾部添加节点x, 时间O(1)
// 将x插入尾节点之前
func (this *DoubleList) AddLast(x *Node) {
	x.prev = this.tail.prev
	x.next = this.tail
	this.tail.prev.next = x
	this.tail.prev = x
	this.size++
}

// 删除链表中的x节点（x一定存在）
func (this *DoubleList) Remove(x *Node) {
	x.prev.next = x.next
	x.next.prev = x.prev
	this.size--
}

// 删除链表中的第一个节点，并返回该节点，时间O(1)
func (this *DoubleList) RemoveFirst() *Node {
	if this.head.next == this.tail {
		return nil
	}
	first := this.head.next
	this.Remove(first)
	return first
}

// 返回链表长度
func (this *DoubleList) Size() int {
	return this.size
}

// 构建缓存结构体
type LRUCache struct {
	_map  map[int]*Node
	cache *DoubleList
	// 最大容量
	cap int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		_map:  make(map[int]*Node),
		cache: NewDoubleList(),
		cap:   capacity,
	}
}

// 将某个key提升为最近使用的
func (this *LRUCache) makeRecently(key int) {
	x := this._map[key]
	this.cache.Remove(x)
	this.cache.AddLast(x)
}

// 添加最近使用的元素
func (this *LRUCache) addRecently(key, val int) {
	x := NewNode(key, val)
	this.cache.AddLast(x)
	this._map[key] = x
}

// 删除某个key
func (this *LRUCache) deleteKey(key int) {
	x := this._map[key]
	this.cache.Remove(x)
	delete(this._map, key)
}

// 删除最久未使用（头节点）元素
func (this *LRUCache) removeLeaseRecently() {
	x := this.cache.RemoveFirst()
	delete(this._map, x.key)
}

func (this *LRUCache) Get(key int) int {
	if _, ok := this._map[key]; !ok {
		return -1
	}
	this.makeRecently(key)
	return this._map[key].val
}

func (this *LRUCache) Put(key, val int) {
	if _, ok := this._map[key]; ok {
		// 删除旧的节点
		this.deleteKey(key)
		this.addRecently(key, val)
		return
	}

	if this.cap == this.cache.Size() {
		this.removeLeaseRecently()
	}

	this.addRecently(key, val)
}

func main() {
	// 创建一个容量为 2 的 LRU 缓存
	cache := Constructor(2)

	// 插入数据
	cache.Put(1, 1) // 缓存: [1=1]
	cache.Put(2, 2) // 缓存: [1=1, 2=2]

	// 获取 key 1 的值，应返回 1
	fmt.Println(cache.Get(1)) // 输出 1

	// 插入数据 3，会将 key 2 删除，因为容量限制
	cache.Put(3, 3) // 缓存: [1=1, 3=3]

	// 获取 key 2 的值，应该返回 -1（因为 key 2 被删除）
	fmt.Println(cache.Get(2)) // 输出 -1

	// 插入数据 4，会将 key 1 删除，因为 key 1 是最久未使用的
	cache.Put(4, 4) // 缓存: [3=3, 4=4]

	// 获取 key 1 的值，应该返回 -1（因为 key 1 被删除）
	fmt.Println(cache.Get(1)) // 输出 -1

	// 获取 key 3 的值，应该返回 3
	fmt.Println(cache.Get(3)) // 输出 3

	// 获取 key 4 的值，应该返回 4
	fmt.Println(cache.Get(4)) // 输出 4

	// 插入数据 5，将删除最久未使用的 key 3
	cache.Put(5, 5) // 缓存: [4=4, 5=5]

	// 获取 key 3 的值，应该返回 -1（因为 key 3 被删除）
	fmt.Println(cache.Get(3)) // 输出 -1

	// 获取 key 4 和 key 5 的值
	fmt.Println(cache.Get(4)) // 输出 4
	fmt.Println(cache.Get(5)) // 输出 5
}

LFU

LFU（Least Frequently Used）算法

LFU（Least Frequently Used）是一种缓存替换算法，主要用于淘汰最少使用的数据。当缓存空间满时，LFU会选择访问频率最低的数据进行删除，从而为新数据腾出空间。不同于LRU（Least Recently Used）依赖于数据的访问顺序，LFU关注的是数据的访问频率。

工作原理

LFU算法通过维护数据项的访问频率，来确定哪些数据是最不常用的。每个数据都会被分配一个计数器，表示该数据被访问的次数。当缓存满时，LFU会选择访问频率最小的数据进行淘汰。需要注意的是，如果有多个数据的访问频率相同，则需要根据其他标准（例如最近访问的时间）来决定哪些数据应该被淘汰。

实现方式

主要数据结构

1. keyToVal：保存每个 key 对应的值。

2. keyToFreq：保存每个 key 对应的访问频率。

3. freqToKeys：保存每个访问频率对应的 key 列表，列表维护着具有相同频率的 key，可以根据访问顺序来删除最久未使用的 key。

4. keyToNode：用于将 key 映射到频率链表中的具体位置，帮助我们在 O(1) 的时间复杂度下删除 key。

5. minFreq：记录当前缓存中的最小频率。

6. cap：缓存的最大容量。

7. size：当前缓存的大小。

type LFUCache struct {
	// key 到 val 的映射
	keyToVal map[int]int
	// key 到 freq（访问次数、频率）的映射
	keyToFreq map[int]int
	// freq 到 key的映射，返回相同freq下的key值列表，用于查找最旧的数据
	freqToKeys map[int]*list.List
	// 记录最小的频率
	minFreq int
	// 记录LFU缓存的最大容量
	cap int
	// 当前缓存的大小
	size int
	// key 到其所在列表中元素的映射，用于O(1)删除，存储list的数据，用于查询后删除，创建后添加操作
	keyToNode map[int]*list.Element
}

主要操作

1. 构造函数：初始化缓存。

2. Get操作：获取缓存的值，如果存在则返回其值并增加访问频率。如果不存在返回 -1。

3. Put操作：如果 key 存在则更新其值并增加访问频率，如果 key 不存在则插入新值，且在缓存满时进行淘汰操作。

4. removeMinFreqKey：删除最小频率的 key，当缓存已满时调用该方法来淘汰最不常用的缓存项。

5. increaseFreq：增加 key 的访问频率，并将其从当前频率的列表中移动到频率更高的列表。

// 构造LFU缓存
func Constructor(capacity int) LFUCache {
	return LFUCache{
		keyToVal:   make(map[int]int),
		keyToFreq:  make(map[int]int),
		freqToKeys: make(map[int]*list.List),
		keyToNode:  make(map[int]*list.Element),
		cap:        capacity,
		size:       0,
		minFreq:    0,
	}
}

// 删除使用最小频率的key
func (this *LFUCache) removeMinFreqKey() {
	// 获取freq最小的key列表
	keys := this.freqToKeys[this.minFreq]
	// 删除最先插入的key
	node := keys.Front()
	deleteKey := node.Value.(int)
	// 开始逐步删除
	keys.Remove(node)
	if keys.Len() == 0 {
		delete(this.freqToKeys, this.minFreq)
	}
	delete(this.keyToVal, deleteKey)
	delete(this.keyToFreq, deleteKey)
	delete(this.keyToNode, deleteKey)
	this.size--
}

// 增加key的访问次数
func (this *LFUCache) increaseFreq(key int) {
	freq := this.keyToFreq[key]
	this.keyToFreq[key] = freq + 1
	node := this.keyToNode[key]
	fmt.Println(node)
	fmt.Println("------------")
	fmt.Println(*this.freqToKeys[freq])
	this.freqToKeys[freq].Remove(node)
	if this.freqToKeys[freq].Len() == 0 {
		delete(this.freqToKeys, freq)
		if freq == this.minFreq {
			this.minFreq++
		}
	}

	if _, ok := this.freqToKeys[freq+1]; !ok {
		this.freqToKeys[freq+1] = list.New()
	}

	this.keyToNode[key] = this.freqToKeys[freq+1].PushBack(key)
}

// Get操作
func (this *LFUCache) Get(key int) int {
	if _, ok := this.keyToVal[key]; !ok {
		return -1
	}
	this.increaseFreq(key)
	return this.keyToVal[key]
}

// Put操作
func (this *LFUCache) Put(key, val int) {
	if this.cap <= 0 {
		return
	}

	// key存在，将覆盖原来的值
	if _, ok := this.keyToVal[key]; ok {
		this.keyToVal[key] = val
		this.increaseFreq(key)
		return
	}

	// 如果key不存在
	// 1. 容量已满。删除最少访问次数的元素
	if this.cap <= this.size {
		this.removeMinFreqKey()
	}

	// 逐步插入
	this.keyToVal[key] = val
	this.keyToFreq[key] = 1
	if _, ok := this.freqToKeys[1]; !ok {
		this.freqToKeys[1] = list.New()
	}
	this.keyToNode[key] = this.freqToKeys[1].PushBack(key)
	this.minFreq = 1
	this.size++
}

完整代码

package main

import (
	"container/list"
	"fmt"
)

type LFUCache struct {
	// key 到 val 的映射
	keyToVal map[int]int
	// key 到 freq（访问次数、频率）的映射
	keyToFreq map[int]int
	// freq 到 key的映射，返回相同freq下的key值列表，用于查找最旧的数据
	freqToKeys map[int]*list.List
	// 记录最小的频率
	minFreq int
	// 记录LFU缓存的最大容量
	cap int
	// 当前缓存的大小
	size int
	// key 到其所在列表中元素的映射，用于O(1)删除
	keyToNode map[int]*list.Element
}

// 构造LFU缓存
func Constructor(capacity int) LFUCache {
	return LFUCache{
		keyToVal:   make(map[int]int),
		keyToFreq:  make(map[int]int),
		freqToKeys: make(map[int]*list.List),
		keyToNode:  make(map[int]*list.Element),
		cap:        capacity,
		size:       0,
		minFreq:    0,
	}
}

// 删除使用最小频率的key
func (this *LFUCache) removeMinFreqKey() {
	// 获取freq最小的key列表
	keys := this.freqToKeys[this.minFreq]
	// 删除最先插入的key
	node := keys.Front()
	deleteKey := node.Value.(int)
	// 开始逐步删除
	keys.Remove(node)
	if keys.Len() == 0 {
		delete(this.freqToKeys, this.minFreq)
	}
	delete(this.keyToVal, deleteKey)
	delete(this.keyToFreq, deleteKey)
	delete(this.keyToNode, deleteKey)
	this.size--
}

// 增加key的访问次数
func (this *LFUCache) increaseFreq(key int) {
	freq := this.keyToFreq[key]
	this.keyToFreq[key] = freq + 1
	node := this.keyToNode[key]
	fmt.Println(node)
	fmt.Println("------------")
	fmt.Println(*this.freqToKeys[freq])
	this.freqToKeys[freq].Remove(node)
	if this.freqToKeys[freq].Len() == 0 {
		delete(this.freqToKeys, freq)
		if freq == this.minFreq {
			this.minFreq++
		}
	}

	if _, ok := this.freqToKeys[freq+1]; !ok {
		this.freqToKeys[freq+1] = list.New()
	}

	this.keyToNode[key] = this.freqToKeys[freq+1].PushBack(key)
}

// Get操作
func (this *LFUCache) Get(key int) int {
	if _, ok := this.keyToVal[key]; !ok {
		return -1
	}
	this.increaseFreq(key)
	return this.keyToVal[key]
}

// Put操作
func (this *LFUCache) Put(key, val int) {
	if this.cap <= 0 {
		return
	}

	// key存在，将覆盖原来的值
	if _, ok := this.keyToVal[key]; ok {
		this.keyToVal[key] = val
		this.increaseFreq(key)
		return
	}

	// 如果key不存在
	// 1. 容量已满。删除最少访问次数的元素
	if this.cap <= this.size {
		this.removeMinFreqKey()
	}

	// 逐步插入
	this.keyToVal[key] = val
	this.keyToFreq[key] = 1
	if _, ok := this.freqToKeys[1]; !ok {
		this.freqToKeys[1] = list.New()
	}
	this.keyToNode[key] = this.freqToKeys[1].PushBack(key)
	this.minFreq = 1
	this.size++
}

func main() {
	cache := Constructor(2)
	cache.Put(1, 1)           // 缓存是 {1=1}
	cache.Put(2, 2)           // 缓存是 {1=1, 2=2}
	fmt.Println(cache.Get(1)) // 返回 1
	cache.Put(3, 3)           // 删除键 2，缓存是 {1=1, 3=3}
	fmt.Println(cache.Get(2)) // 返回 -1 (未找到)
	cache.Put(4, 4)           // 删除键 1，缓存是 {3=3, 4=4}
	fmt.Println(cache.Get(1)) // 返回 -1 (未找到)
	fmt.Println(cache.Get(3)) // 返回 3
	fmt.Println(cache.Get(4)) // 返回 4

}