golang-LRU算法学习

golang-LRU算法学习

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”

package main

import (
	"container/list"
	"sync"
)

//定义结构体
type LruCache struct{
	Clock sync.Mutex
	ListMap sync.Map
	List *list.List
	MaxLength int
}
//初始化
func NewLruCache(maxLength int) *LruCache{
	lCache := &LruCache{
		List:list.New(),
		MaxLength:maxLength,
	}
	return lCache
}

//存储数据
func (l *LruCache)Set(key string,val interface{}){
	l.Clock.Lock()
	defer l.Clock.Unlock()

	//判断值是否存在,存在则返回
	if _,ok := l.ListMap.Load(key);ok{
		return
	}
	//添加到链表后边,并返回添加的值
	e := l.List.PushBack(val)
	//设置map键值关系
	l.ListMap.Store(key,e)
	//判断总数是否大于设置的最大长度
	if l.List.Len() > l.MaxLength{
		//返回列表最后一个元素,并删除
		e := l.List.Back()
		l.List.Remove(e)
		l.ListMap.Delete(key)
	}
}

//获取数据
func (l *LruCache)Get(key string) interface{}{
	if v,ok := l.ListMap.Load(key);ok{
		//判断元素是否是列表元素
		if ev,ok := v.(*list.Element);ok{
			//将元素移动到列表前边
			l.List.MoveToFront(ev)
			return ev.Value
		}
	}
	return nil
}

//删除数据
func (l *LruCache)Del(key string){
	l.Clock.Lock()
	defer l.Clock.Unlock()

	if v,ok := l.ListMap.Load(key);ok{
		if ev,ok := v.(*list.Element);ok{
			l.List.Remove(ev)
		}
		l.ListMap.Delete(key)
	}
}