如何利用Go语言实现LRU|如何利用Go语言实现LRU Cache 如何利用Go语言实现LRUCache

1基本概念
2代码实现
3测试使用

1 基本概念 LRU是一个老生常谈的问题，即最近最少使用，LRU是Least Recently Used的缩写，是一种操作系统中常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
实现LRU基本的数据结构：Map+LinkedList

文章图片

一般规则：

添加数据时，将新增数据节点放在头指针，尾结点部分大于最大长度时删除。
删除数据时，先按照Map的规则进行查找，再根据链表规则进行删除。
查找数据时，按照Map进行查找，没有则返回空，有则返回该数据的值并移动到头节点。

2 代码实现

package mainimport "fmt"var head *Nodevar end *Nodetype Node struct {KeystringValue stringpre*Nodenext*Node}func (n *Node) Init(key string, value string) {n.Key = keyn.Value = https://www.it610.com/article/value}type LRUCache struct {Capacity int//页面初始化大小Sizeint//页面实际大小Mapmap[string]*Node //具体的cache}func GetLRUCache(capacity int) *LRUCache {lruCache := LRUCache{Capacity: capacity}lruCache.Map = make(map[string]*Node, capacity)return &lruCache}func (l *LRUCache) get(key string) string {if v, ok := l.Map[key]; ok {l.refreshNode(v)return v.Value} else {return"null"}}func (l *LRUCache) put(key, value string) {if v, ok := l.Map[key]; !ok {if len(l.Map) >= l.Capacity {oldKey := l.removeNode(head)delete(l.Map, oldKey)}node := Node{Key: key, Value: value}l.addNode(&node)l.Map[key] = &node} else {v.Value = https://www.it610.com/article/valuel.refreshNode(v)}}func (l *LRUCache) refreshNode(node *Node) {if node == end {return}l.removeNode(node)l.addNode(node)}func (l *LRUCache) removeNode(node *Node) string {if node == end {end = end.pre} else if node == head {head = head.next} else {node.pre.next = node.nextnode.next.pre = node.pre}return node.Key}func (l *LRUCache) addNode(node *Node) {if end != nil {end.next = nodenode.pre = endnode.next = nil}end = nodeif head == nil {head = node}}

3 测试使用

func main() {lruCache := GetLRUCache(3)lruCache.put("001", "1")lruCache.put("002", "2")lruCache.put("003", "3")lruCache.put("004", "4")lruCache.put("005", "5")lruCache.get("002")fmt.Println(lruCache.get("001"))fmt.Println(lruCache.get("002"))fmt.Print(lruCache.Map)}

【如何利用Go语言实现LRU|如何利用Go语言实现LRU Cache】到此这篇关于如何利用Go语言实现LRU Cache的文章就介绍到这了,更多相关Go实现LRU Cache内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！