手撕LRU代码

原理

LRU（Least Recently Used）最近最少使用，用于缓存淘汰策略，就是把最近最少使用的数据移除内存，以加载其他数据

1. 添加元素时，放到链表头
2. 缓存命中将元素移动到链表中
3. 缓存满了之后，将链表尾的元素删除

原理清楚了，代码其实就是双向链表和map，然后根据需求写代码即可

代码

package main

import (
	"container/list"
	"fmt"
	"sync"
)

type LRU struct {
	max   int                                      //存储key的最大数量
	list  *list.List                               //双向链表
	Call  func(key interface{}, value interface{}) //淘汰kv时的回调函数
	cache map[interface{}]*list.Element            //缓存
	mu    *sync.Mutex                              //互斥锁
}

type Node struct {
	Key interface{}
	Val interface{}
}

// NewLRU 返回一个LRU的实例
func NewLRU(len int) *LRU {
	return &LRU{
		max:   len,
		list:  list.New(),
		Call:  nil,
		cache: make(map[interface{}]*list.Element),
		mu:    new(sync.Mutex),
	}
}

// Add 添加一个kv到缓存中
func (lru *LRU) Add(key, val interface{}) error {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	//如果存在则更新，并将结点移到最前面
	if e, ok := lru.cache[key]; ok {
		e.Value.(*Node).Val = val
		lru.list.MoveToFront(e)
		return nil
	}
	//如果不存在则头插到双向链表中
	e := lru.list.PushFront(&Node{
		Key: key,
		Val: val,
	})
	//添加至缓存中
	lru.cache[key] = e
	//如果元素的数量超过最大值了，那么把末端的淘汰
	if lru.max != 0 && lru.list.Len() > lru.max {
		if e := lru.list.Back(); e != nil {
			lru.list.Remove(e)
			node := e.Value.(*Node)
			delete(lru.cache, node.Key)
			if lru.Call != nil {
				lru.Call(node.Key, node.Val)
			}
		}
	}
	return nil
}
func (lru *LRU) Get(key interface{}) (val interface{}, ok bool) {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	//如果存在，先把该kv移到链表头部再返回
	if e, ok := lru.cache[key]; ok {
		lru.list.MoveToFront(e)
		return e.Value.(*Node).Val, true
	}
	return
}
func (lru *LRU) GetAll() (data []*Node) {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	for _, v := range lru.cache {
		data = append(data, v.Value.(*Node))
	}
	return data
}
func (lru *LRU) Del(key interface{}) {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	if e, ok := lru.cache[key]; ok {
		lru.list.Remove(e)
		node := e.Value.(*Node)
		delete(lru.cache, node.Key)
		if lru.Call != nil {
			lru.Call(node.Key, node.Val)
		}
	}
}
func main() {
	lru := NewLRU(3)
	lru.Add("w", "1")
	lru.Add("x", "2")
	lru.Add("f", "3")
	lru.Add("c", "4")
	lru.Add("s", "5")
	for _, node := range lru.GetAll() {
		fmt.Println(node)
	}
	fmt.Println("~~~分割线~~~")
	lru.Del("f")
	for _, node := range lru.GetAll() {
		fmt.Println(node)
	}
	fmt.Println("~~~分割线~~~")
	lru.Add("qq", "68725032")
	for _, node := range lru.GetAll() {
		fmt.Println(node)
	}
}