golang实现LRU算法

永明_3c16 · · 1604 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

LRU缓存淘汰算法

LRU是最近最少使用策略的缩写。

双向链表实现LRU

将Cache的所有位置都用双链表连接起来,当一个位置被访问(get/put)之后,通过调整链表的指向,将该位置调整到链表尾的位置,新加入的Cache直接加到链表尾。

这样,在多次操作后,最近被访问(get/put)的,就会被向链表尾方向移动,而没有访问的,向链表前方移动,链表头则表示最近最少使用的Cache。

package main

import (

"fmt"

)

type Node struct{

Key interface{}

Value interface{}

pre *Node

next *Node

}

type LRUCache struct {

limit int

HashMap map[interface{}]*Node

head *Node

end *Node

}

func(l *LRUCache)removeNode(node *Node)interface{}{

if node == l.end{

l.end = l.end.pre

l.end.next = nil

} else if node == l.head{

l.head = l.head.next

l.head.pre = nil

} else {

node.pre.next = node.next

node.next.pre = node.pre

}

return node.Key

}

func (l *LRUCache)addNode(node *Node){

if l.end != nil {

l.end.next = node

node.pre = l.end

node.next = nil

}

l.end = node

if l.head == nil {

l.head = node

}

}

func (l *LRUCache)refreshNode(node *Node){

if node == l.end{

return

}

l.removeNode(node) // 从链表中的任意位置移除原来的位置

l.addNode(node) // 添加到链表的尾部

}

// 构造

func Constructor(capacity int)LRUCache{

lruCache := LRUCache{limit: capacity}

lruCache.HashMap = make(map[interface{}]*Node, capacity)

return lruCache

}

// 获取

func (l *LRUCache)Get(key interface{})interface{}{

if v, ok := l.HashMap[key]; ok {

l.refreshNode(v)

return v.Value

} else {

return -1

}

}

func (l *LRUCache)Put(key, value interface{}){

if v, ok := l.HashMap[key]; !ok{

if len(l.HashMap) >= l.limit {

oldkey := l.removeNode(l.head)

delete(l.HashMap, oldkey)

}

node := Node{Key:key, Value:value}

l.addNode(&node)

l.HashMap[key] = &node

} else {

v.Value = value

l.refreshNode(v)

}

}

func (l *LRUCache)getCache(){

for n := l.head; n != nil; n = n.next{

fmt.Println(n.Key, n.Value)

}

}

func main(){

cache := Constructor(3)

cache.Put(11, 1)

cache.Put(22, 2)

cache.Put(33, 3)

cache.Put(44, 4)

v := cache.Get(33)

fmt.Println(v)

fmt.Println("========== 获取数据之后 ===============")

cache.getCache()

}


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:永明_3c16

查看原文:golang实现LRU算法

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1604 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传