LRU（Least Recently Used，最近最少使用）算法是一种常用于缓存管理的算法，用于在缓存空间有限的情况下，决定哪些数据应该被移除。它的基本思想是：如果一个数据最近被访问过，那么在将来一段时间内它被再次访问的概率较高。因此，当缓存已满，需要移除数据时，优先移除那些最近最少被使用的数据。
LRU算法的基本概念
- 缓存命中（Cache Hit）：当访问的数据已经在缓存中时，称为缓存命中。
- 缓存未命中（Cache Miss）：当访问的数据不在缓存中，需要从外部存储加载数据时，称为缓存未命中。
- 缓存替换（Cache Replacement）：当缓存已满，需要替换掉某些数据以腾出空间时，称为缓存替换。
LRU算法的实现
LRU算法的实现通常需要两个数据结构：
- 哈希表（Hash Table）：用于快速访问缓存中的数据。
- 双向链表（Doubly Linked List）：用于维护数据的使用顺序，链表头部是最近使用的数据，尾部是最久未使用的数据。
LRU缓存的操作
- 访问数据：
- 如果数据在缓存中（缓存命中），将其移动到链表头部。
- 如果数据不在缓存中（缓存未命中），将数据插入到链表头部。
- 如果缓存已满，移除链表尾部的数据，以腾出空间。
- 插入数据：
- 将数据插入到链表头部。
- 更新哈希表，使其指向新节点。
- 如果缓存已满，移除链表尾部的数据，并在哈希表中删除相应的项。
Go 实现
代码语言：go复制package lru
import (
"container/list"
"sync"
)
type LRUCache struct {
mtx sync.Mutex // protects the cache
capacity int // capacity of the cache
cache map[any]*list.Element // nearly O(1) lookups
list *list.List // O(1) insert, update, delete
}
// NewLRUCache creates a new LRU cache with the given capacity.
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{
capacity: capacity,
cache: make(map[any]*list.Element),
list: list.New(),
}
}
// Contains checks if the given item is in the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Contains(item any) bool {
c.mtx.Lock()
defer c.mtx.Unlock()
node, exists := c.cache[item]
if exists {
c.list.MoveToFront(node)
}
return exists
}
// Get returns the item from the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Get(item any) any {
node, exists := c.cache[item]
if exists {
c.mtx.Lock()
c.list.MoveToFront(node)
c.mtx.Unlock()
return node.Value
} else {
c.Add(item)
return item
}
}
// Add adds the given item to the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Add(item any) {
c.mtx.Lock()
defer c.mtx.Unlock()
// if capacity is 0, nothing can be added, so just return
if c.capacity == 0 {
return
}
// check if the item is already in the cache
if node, exists := c.cache[item]; exists {
c.list.MoveToFront(node)
return
}
// if the cache is full, remove the last element
if c.list.Len() == c.capacity {
last := c.list.Back()
c.list.Remove(last)
delete(c.cache, last.Value)
}
// add the new item to the front of the list
node := c.list.PushFront(item)
c.cache[item] = node
}
// Delete removes the given item from the cache if exists.
// This function is safe for concurrent access.
func (c *LRUCache) Delete(item any) {
c.mtx.Lock()
defer c.mtx.Unlock()
// check if the item is already in the cache
if node, exists := c.cache[item]; exists {
c.list.Remove(node)
delete(c.cache, item)
}
}
// Len returns the number of items in the cache.
// This function is safe for concurrent access.
func (c *LRUCache) Len() int {
c.mtx.Lock()
defer c.mtx.Unlock()
return c.list.Len()
}我正在参与2024腾讯技术创作特训营最新征文，快来和我瓜分大奖！
