go设计LRU算法，实现链表和淘汰
一、LRU算法
LRU（Least Recently Used，最近最少使用）算法是一种常见的页面置换算法，通常用于操作系统内存管理中，也被广泛应用在缓存系统中，如实现一个LRU Cache。该算法的核心思想是基于时间局部性原理：最近被访问的数据很有可能会在不久的将来再次被访问。
- 工作原理 ：缓存页面置换策略：LRU算法会根据数据的访问顺序来进行置换，如果需要淘汰缓存中的数据，则会将那些最久未被访问的数据移出缓存。
- 使用链表记录访问顺序：典型的实现方式是使用双向链表和哈希表。双向链表用于记录数据的访问顺序，靠近头部的节点表示最近被访问的数据，靠近尾部的节点表示最久未被访问的数据；哈希表用于快速检索数据对应的节点。
- 数据访问时的处理：当数据被访问时，若数据已经在缓存中，LRU算法会将该数据节点移动到链表头部，表示最近被访问过；若数据不在缓存中，则新数据会被插入链表头部，并检查缓存是否已满，如果缓存已满就淘汰链表尾部数据节点。
- 淘汰最久未被访问的数据：当需要淘汰数据时，LRU算法会移除链表尾部节点，最近被访问的数据节点会一直保留在链表头部。
二、源码实现
这个示例代码展示了一个基本的 LRU 缓存实现，使用双向链表（list.List）和哈希表（map）来存储数据。LruCache 结构体包含了一个固定容量的哈希表和双向链表，用于实现 LRU 缓存的基本功能。Get 方法用于获取缓存中的值，Set 方法用于插入或更新缓存，并根据 LRU 算法保持最近访问的元素在链表头部。
在这个示例中，LRU 缓存的容量为 3，当缓存中的元素个数超过容量时，会使用 LRU 策略删除最近最少使用的元素。可以根据实际需求对此基本示例进行扩展和优化。
package main
// 链表
type list struct {
key string
value string
prev *list
next *list
}
// 存储数据源
type LruCache struct {
cap int
cache map[string]*list
head *list
tail *list
}
func getLru(cap int) (lru LruCache) {
var head, tail *list
head = new(list)
tail = new(list)
head.next = tail
tail.prev = head
return LruCache{
cap: cap,
cache: make(map[string]*list),
head: head,
tail: tail,
}
}
func (t *LruCache) Set(k, v string) {
if val, ok := t.cache[k]; ok {
//存在直接更新
t.cache[k].key = k
t.cache[k].value = v
//删除当前位置
t.remove(val)
//移到最前面
t.moveToHead(val)
} else {
if len(t.cache) >= t.cap {
//超如容量需要删除最后一个
delete(t.cache, t.tail.prev.key)
t.remove(t.tail.prev)
}
newList := &list{key: k, value: v}
t.cache[k] = newList
//移到最前面
t.moveToHead(newList)
}
}
func (t *LruCache) Get(k string) string {
if val, ok := t.cache[k]; ok {
//删除当前位置
t.remove(val)
//移到最前面
t.moveToHead(val)
return val.value
}
return "-1"
}
func (t *LruCache) remove(l *list) {
//剪短上层联系
l.prev.next = l.next
//剪短下层联系
l.next.prev = l.prev
}
func (t *LruCache) moveToHead(l *list) {
//移到第一个节点
l.prev = t.head
//原有第一个节点改为当前节点的下一个
l.next = t.head.next
t.head.next.prev = l
t.head.next = l
}
func main() {
cache := getLru(3)
cache.Set("1", "1")
cache.Set("2", "2")
cache.Set("3", "3")
cache.Set("4", "4")
cache.Set("5", "5")
cache.Get("3")
cache.Get("5")
cache.Get("2")
}
