[数据结构与算法]LRU算法-golang

1.思路

? a.以内要快速访问，查找，删除，查询操作要快，首先想到的就kv存储，即map数据结构。同时要删除和插入的时间复杂度o(1),链表具有该种特性。但是缓存中需要有顺序之分，而链表也是有序的，并且为了区分最近使用跟许久未使用的情况。使用头部作为最近使用的节点，而尾部都是许久未使用的,并且设置淘汰容量，当加入新元素，发现容量满了，就将许久未使用的淘汰掉，腾出空间，再存储新的即可。

? b.使用双向链表的原因是，移动节点到头部or淘汰元素时，需要前驱节点的支撑，所有在链表中使用双向链表。

? c.map控制缓存节点的快速访问，查找与删除,双向链表设置头尾指针控制访问时的节点移动到头部分，以及淘汰时的尾部节点的的淘汰处理。

? d.新加入节点，直接头插法插入链表中。访问某个节点，并将该节点设置为最新访问的头节点。更新节点，同样需要将该节点移动到头部,设置成最新访问节点。

? e.存储的结构图形:

2.代码:

package main

import (
	"fmt"
)

type Node struct {
	Key, Val   interface{}
	Prev, Next *Node
}

type LRUCache struct {
	Size       int // 节点的数量
	Cap        int // 容量
	Cache      map[interface{}]*Node
	Head, Tail *Node // 头尾节点

}

func CreateCache(cap int) *LRUCache {
	return &LRUCache{
		Size:  0,
		Cap:   cap,
		Cache: map[interface{}]*Node{},
		Head:  nil,
		Tail:  nil,
	}
}

// 设置当前节点为新的头节点
func (l *LRUCache) SetHead(node *Node) {
	node.Next = l.Head
	node.Prev = nil
	if l.Head == nil {
		l.Head = node
	} else {
		l.Head.Prev = node
		l.Head = node
	}
	if l.Tail == nil {
		l.Tail = node
	}
}

// 移动当前节点到头节点
func (l *LRUCache) MoveNodeToHead(node *Node) {
	// 更新节点,头节点不为空,并且移动的节点非头节点
	// 如果是本身就是头节点,或者此时头尾相同,不作处理,如果是尾节点,需要移动
	if l.Head != node && l.Tail == node {
		// Tail的前缀节点跟Tail断链
		prefix := l.Tail.Prev
		l.Tail.Prev = nil
		prefix.Next = nil
		// 移动至头
		l.Tail.Next = l.Head
		l.Head.Prev = l.Tail
		l.Tail = prefix // 尾部节点上移动
	}
	// 处于中间节点
	if l.Head != node && l.Tail != node {
		// 拆出来node
		prefix := node.Prev
		prefix.Next = node.Next
		node.Next.Prev = prefix

		// 移动到头部
		node.Next = l.Head
		node.Prev = nil
		l.Head.Prev = node
		l.Head = node
	}
}

// Add Node
func (l *LRUCache) AddNode(key, val interface{}) {
	if _, ok := l.Cache[key]; ok {
		// 如果存在,直接更新
		l.Cache[key].Val = val
		// 移动该节点至头部
		l.MoveNodeToHead(l.Cache[key])
	} else {
		node := &Node{
			Key: key,
			Val: val,
		}
		// 检查容量是否超标
		if l.Size >= l.Cap {
			delNode := l.RemoveLastNode() // 链表断链
			delete(l.Cache, delNode.Key)  // Cache清理
			l.Size--                      // 节点数量递减
		}
		// map中存储节点
		l.Cache[key] = node
		// 将节点移动到头部
		l.SetHead(node)
		// 节点数量
		l.Size++
	}
}

// 移除很久没访问的节点,腾出空间
func (l *LRUCache) RemoveLastNode() *Node {
	delNode := l.Tail
	if l.Tail != nil {
		l.Tail = l.Tail.Prev   // tail指向最近没访问的倒数第二节点
		l.Tail.Next.Prev = nil // 当前节点的prev断链
		l.Tail.Next = nil
	}
	return delNode
}

// 访问某个节点,访问之后,同样将访问的节点移动到头部
func (l *LRUCache) GetNode(key interface{}) *Node {
	var retNode *Node
	if _, ok := l.Cache[key]; ok {
		retNode = l.Cache[key]
		// 移动当前节点至头部
		l.MoveNodeToHead(l.Cache[key])
	}
	return retNode
}

func (l *LRUCache) Show() {
	for k, _ := range l.Cache {
		fmt.Println(l.Cache[k].Key, "=", l.Cache[k].Val)
	}
}

func (l *LRUCache) ShowList() {
	for h := l.Head; h != nil; h = h.Next {
		fmt.Println(h.Key, "+", h.Val)
	}
}

func main() {

	// 创建一个哈希链表
	lru := CreateCache(2)

	// lru.AddNode(1, 1)
	// lru.AddNode(2, 2)
	// lru.AddNode(3, 3) // 调用淘汰
	// lru.AddNode(4, 4) // 调用淘汰

	for i := 0; i < 10; i++ {
		lru.AddNode(i, i)
	}
	// lru.Show()
	lru.ShowList()

}

运行结果:

9 + 9
8 + 8