lru（least recently used）算法是一种常见的缓存替换策略。在缓存达到预设上限时，缓存会自动淘汰最近最少使用的数据，以释放出空间。
在 Golang 中，我们可以使用双向链表和哈希表来实现 LRU 缓存。在本文中，我们将介绍如何使用这两种数据结构实现 LRU 缓存。
双向链表的作用在于维护缓存的数据顺序，每次插入新数据或者访问数据时，都将对该数据进行提前。同时，在缓存达到上限时，我们可以从链表的末端删除最近最少使用的数据。
哈希表的作用在于加速数据的查找，每次进行数据访问时，通过哈希表中存储的数据索引，我们可以快速地查找到相应的缓存数据。因此，我们将在实现过程中对哈希表进行操作。
接下来，我们将讲解如何实现基于双向链表和哈希表的 LRU 缓存。我们定义一个 LRUCache 结构体，并声明链表头和链表尾指针，以及哈希表 map 和缓存容量 capacity。
立即学习“go语言免费学习笔记（深入）”；
type LRUCache struct {
head, tail *entry // 链表头和链表尾指针
cache map[int]*entry // 哈希表存储缓存中的数据
capacity int // 缓存容量
}接下来，我们将定义双向链表节点的结构体。
type entry struct {
key, value int // 存储节点的键值对
prev, next *entry // 前驱和后继指针
}这里，我们使用 prev 和 next 分别表示节点的前驱和后继指针，key 和 value 分别表示该节点的键值对。
接下来，我们将定义 LRUCache 的构造函数 NewLRUCache，并传入缓存容量 capacity。
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
cache: make(map[int]*entry),
capacity: capacity,
}
}在构造函数中，我们将初始化哈希表和缓存容量。
接下来，我们将定义 LRUCache 的 Get 和 Put 方法来实现数据的访问和存储。
Get 方法的实现：
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 更新节点位置
c.moveToHead(elem)
return elem.value
}
return -1
}首先，我们从哈希表中查找是否存在相应的数据，如果存在，则将节点移到链表的头部，并返回节点存储的值。否则，返回 -1。
下面是 moveToHead 方法的实现：
func (c *LRUCache) moveToHead(elem *entry) {
if elem == c.head {
return
} else if elem == c.tail {
c.tail = elem.prev
} else {
elem.prev.next = elem.next
elem.next.prev = elem.prev
}
elem.prev = nil
elem.next = c.head
c.head.prev = elem
c.head = elem
}该方法接收一个节点指针 elem，用于将该节点移到链表头部。首先，如果该节点已经是链表头部，则返回；否则，如果该节点是链表尾部，则更新链表尾部指针 tail；否则，将该节点从链表中删除，并将该节点放到链表头部。
Put 方法的实现：
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
elem.value = value
c.moveToHead(elem)
} else {
// 创建新节点
elem := &entry{key: key, value: value}
c.cache[key] = elem
if c.head == nil {
c.head = elem
c.tail = elem
} else {
// 在链表头部插入新节点
elem.next = c.head
c.head.prev = elem
c.head = elem
}
// 判断缓存是否达到预设上限
if len(c.cache) > c.capacity {
// 删除链表尾部节点和哈希表中的数据
delete(c.cache, c.tail.key)
c.tail = c.tail.prev
c.tail.next = nil
}
}
}首先，我们从哈希表中查找是否存在相应的数据，如果存在，则更新节点存储的值，并调用 moveToHead 方法将该节点移到链表的头部。否则，创建一个新的节点，并将该节点插入到链表的头部。如果缓存达到预设上限，则删除链表的尾部节点和哈希表中的数据。
最后，我们将完整的代码整合到一起：
type LRUCache struct {
head, tail *entry
cache map[int]*entry
capacity int
}
type entry struct {
key, value int
prev, next *entry
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
cache: make(map[int]*entry),
capacity: capacity,
}
}
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 更新节点位置
c.moveToHead(elem)
return elem.value
}
return -1
}
func (c *LRUCache) moveToHead(elem *entry) {
if elem == c.head {
return
} else if elem == c.tail {
c.tail = elem.prev
} else {
elem.prev.next = elem.next
elem.next.prev = elem.prev
}
elem.prev = nil
elem.next = c.head
c.head.prev = elem
c.head = elem
}
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
elem.value = value
c.moveToHead(elem)
} else {
// 创建新节点
elem := &entry{key: key, value: value}
c.cache[key] = elem
if c.head == nil {
c.head = elem
c.tail = elem
} else {
// 在链表头部插入新节点
elem.next = c.head
c.head.prev = elem
c.head = elem
}
// 判断缓存是否达到预设上限
if len(c.cache) > c.capacity {
// 删除链表尾部节点和哈希表中的数据
delete(c.cache, c.tail.key)
c.tail = c.tail.prev
c.tail.next = nil
}
}
}在本文中，我们已经介绍了如何使用双向链表和哈希表来实现 LRU 缓存算法。通过这种算法的实现，我们可以有效地管理缓存，优化数据的访问效率。
