数据结构之实现LRU缓存淘汰算法

接上一篇，学习极客时间《数据结构与算法之美》散列表的应用，使用动态扩容散列表结合双向链表实现 LRU 缓存淘汰算法，因为链表的查询比较缓慢，时间复杂度为 O(n)，而散列表查询速度快，用以解决链表查询缓慢的问题，点击下方链接了解下 LRU 缓存淘汰算法。

LRU 策略详解

举个🌰：

# 假设现在链表最多存储五个元素，并且已经存在下面四个元素
a b c d
# 现在插入一个 e 元素，那么数据变为
e a b c d
# 现在访问元素 b，数据变为
b e a c d

下面是使用Go语言实现的 LRU 缓存淘汰算法，仅供参考，需要结合上一篇散列表代码：

package main

import (
	"fmt"
)

func main() {
	// 新建一个 LRU 链表
	cache := &lru{
		hm: hashMap{
			capacity:   5,   // 设置散列表初始容量
			loadFactor: 0.6, // 设置散列表装载因子
		},
		maxNodeCount: 5, // 设置 LRU 链表最大容量
	}
	// 初始化散列表和链表
	cache.hm.new()
	cache.new()

	// 测试
	cache.add("a", point{"a"})
	cache.add("b", point{"b"})
	cache.add("c", point{"c"})
	cache.add("d", point{"d"})
	cache.add("e", point{"e"})
	cache.add("f", point{"f"})
	cache.add("g", point{"g"})
	cache.add("h", point{"h"})
	cache.add("i", point{"i"})
	cache.add("j", point{"j"})
	fmt.Println(cache.find("a"))
	fmt.Println(cache.find("c"))
	fmt.Println(cache.find("g"))
	fmt.Println(cache.find("j"))
	cache.remove("a")
	cache.remove("j")
	fmt.Println(cache.find("a"))
	fmt.Println(cache.find("j"))
	cache.add("a", point{"a"})
	fmt.Println(cache.find("a"))

	// 打印 lru 链表
	i := cache.head.next
	for {
		fmt.Println(i.key, i.data)
		if i.next.next == nil {
			break
		}
		i = i.next
	}
	// a {a}
	// g {g}
	// i {i}
	// h {h}
	// f {f}
}

// LRU 链表中的每个节点类型
type lruNode struct {
	prev *lruNode
	next *lruNode
	key  string
	data interface{}
}

// LRU 链表类型
type lru struct {
	hm           hashMap
	head         *lruNode
	tail         *lruNode
	maxNodeCount int
	nodeCount    int
}

// 初始化链表
func (l *lru) new() {
	l.head = &lruNode{nil, nil, "", nil}
	l.tail = &lruNode{nil, nil, "", nil}
	l.head.next = l.tail
	l.tail.prev = l.head
}

// 向链表中添加一个节点
func (l *lru) add(key string, data interface{}) {
	// 如果 key 存在，就移除此节点
	if oldLn := l.hm.getHashMap(key); oldLn != nil {
		v, _ := oldLn.(*lruNode)
		v.prev.next = v.next
		v.next.prev = v.prev
	} else {
		l.nodeCount++
	}

	// 节点数量超出容量，移除一个尾节点，并将节点从散列值中移除
	if l.nodeCount > l.maxNodeCount {
		k := l.tail.prev.key
		l.tail.prev.prev.next = l.tail
		l.tail.prev = l.tail.prev.prev
		l.nodeCount--
		l.hm.delHashMap(k)
	}

	// 将新节点放在链表头
	ln := &lruNode{l.head, l.head.next, key, data}
	ln.next.prev = ln
	ln.prev.next = ln

	// 将节点加入散列表中
	l.hm.setHashMap(key, ln)
}

// 查找节点
func (l *lru) find(key string) interface{} {
	// 查询节点
	ln := l.hm.getHashMap(key)
	if ln == nil {
		return nil
	}

	// 被访问的节点需要移动到链表头
	v, _ := ln.(*lruNode)
	v.prev.next = v.next
	v.next.prev = v.prev
	v.prev = l.head
	v.next = l.head.next
	v.next.prev = v
	v.prev.next = v
	return v.data
}

func (l *lru) remove(key string) {
	ln := l.hm.getHashMap(key)
	// 链表中不存在此节点
	if ln == nil {
		return
	}

	// 存在节点，将此节点从散列表和链表中移除
	v, _ := ln.(*lruNode)
	v.prev.next = v.next
	v.next.prev = v.prev
	l.hm.delHashMap(key)
	l.nodeCount--
}