【golang必备算法】|【golang必备算法】 Letecode 146. LRU 缓存机制【golang必备算法】Letecode146.L

力扣链接：146. LRU 缓存机制
文章图片

思路：哈希表 + 双向链表

文章图片

【【golang必备算法】|【golang必备算法】 Letecode 146. LRU 缓存机制】为什么必须要用双向链表？
因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。
为什么要在链表中同时存储 key 和 val，而不是只存储 val？
当缓存容量已满，我们不仅仅要删除最后一个节点，还要把哈希表中映射到该节点的 key 同时删除，而这个 key 只能由节点得到。如果节点结构中只存储 val，那么我们就无法得知 key 是什么，就无法删除哈希表中的键，造成错误。

代码我这里是向尾部添加数据，所以头部的是不活跃的数据值

type LRUCache struct {//LRU 缓存结构 capacity int// 容量 m map[int]*Node//哈希表 cache *NodeList//双向链表 }type Node struct{//节点结构 keyint value int prev *Node//前一个节点 next *Node//后一个节点 }func initNode(key,value int)*Node{//初始化节点 return &Node{ key:key, value:value, } }type NodeList struct{//链表结构 head *Node//链表头节点 last *Node//链表尾节点 sizeint//元素个数 }func initList ()*NodeList{//初始化链表 dil:=&NodeList{ head:initNode(0,0), last:initNode(0,0), size:0, } dil.head.next=dil.last dil.last.prev=dil.headreturn dil }func (this *NodeList)addNodeinlist(node *Node){//向链表中插入节点，向链表尾部插节点 node.prev=this.last.prev this.last.prev=node node.prev.next=node node.next=this.lastthis.size++ }func (this *NodeList)deleteNodeinlist (node *Node){//删除链表中的某一结点 node.prev.next=node.next node.next.prev=node.prev node.next=nil node.prev=nil this.size-- }func (this *NodeList)delfirstNode()*Node{//删除第一个节点，并且返回 if this.head.next==this.last{ return nil } t:=this.head.next this.deleteNodeinlist(t)return t }func Constructor(capacity int) LRUCache {//初始化 LRU 缓存 return LRUCache{ capacity:capacity, m:make(map[int]*Node,0), cache:initList(), } }func (this *LRUCache)addkey(key,value int){//添加元素 node:=initNode(key,value) //增加map映射 this.m[key]=node//在链表中添加元素 this.cache.addNodeinlist(node) }func (this *LRUCache)makekey(key int){// 将某个 key 调整为最近使用的元素 //找到节点 node:=this.m[key] //删除节点 this.cache.deleteNodeinlist(node) // 添加到链表尾部 this.cache.addNodeinlist(node) }func (this *LRUCache)deletekey(key int){//删除元素//删除链表中节点 this.cache.deleteNodeinlist(this.m[key]) //删除map映射 delete(this.m,key) }func (this *LRUCache)deletefirkey(){//删除最久未使用的元素 // 链表的第一个就是最近最少使用的元素 node:=this.cache.delfirstNode()// 删除映射 delete(this.m,node.key) }func (this *LRUCache) Get(key int) int { if _,ok:=this.m[key]; ok{ //存在 this.makekey(key) //将某个 key 调整为最近使用的元素 return this.m[key].value }else{ //不存在 return -1 }}func (this *LRUCache) Put(key int, value int){ // 检查key存不存在 if _,ok:=this.m[key]; ok{ //存在 //删除元素 this.deletekey(key)//添加元素到尾部 this.addkey(key,value)}else{ //不存在 if this.capacity==this.cache.size{ //缓存达到上限 //删除最久未使用的元素 this.deletefirkey() } //添加元素到尾部 this.addkey(key,value) } }

参考：
https://leetcode-cn.com/problems/lru-cache/solution/jian-dan-shi-li-xiang-xi-jiang-jie-lru-s-exsd/