package main;import (	"container/list"	"errors"	"sync"	"fmt"	"encoding/json")//LRU(Least recently used)最近最少使用，算法根据数据的历史访问记录来进行淘汰数据//核心思想是"如果数据最近被访问过，那么将来被访问的几率也更高"//常见的实现方式是用一个链表保存数据//1. 新数据插入到链表头部//2. 每当缓存命中(即缓存数据被访问)，则将数据移到链表头部//3. 当链表满的时候，将链表尾部的数据丢弃type cacheItem struct {	Key string;	Val interface{};}type LRU struct {	//最大存储数量	maxNum int;	//当前存储数量	curNum int;	//锁，保证数据一致性	mutex  sync.Mutex;	//链表	data   *list.List;}//添加数据func (l *LRU) add(key string, value interface{}) error {	//判断key是否存在	if e, _ := l.exist(key); e {		return errors.New(key + "已存在");	}	//判断当前存储数量与最大存储数量	if l.maxNum == l.curNum {		//链表已满，则删除链表尾部元素		l.clear();	}	l.mutex.Lock();	l.curNum++;	//json序列化数据	data, _ := json.Marshal(cacheItem{key, value});	//把数据保存到链表头部	l.data.PushFront(data);	l.mutex.Unlock();	return nil;}//设置数据func (l *LRU) set(key string, value interface{}) error {	e, item := l.exist(key);	if !e {		return l.add(key, value);	}	l.mutex.Lock();	data, _ := json.Marshal(cacheItem{key, value});	//设置链表元素数据	item.Value = data;	l.mutex.Unlock();	return nil;}//清理数据func (l *LRU) clear() interface{} {	l.mutex.Lock();	l.curNum--;	//删除链表尾部元素	v := l.data.Remove(l.data.Back());	l.mutex.Unlock();	return v;}//获取数据func (l *LRU) get(key string) interface{} {	e, item := l.exist(key);	if !e {		return nil;	}	l.mutex.Lock();	//数据被访问，则把元素移动到链表头部	l.data.MoveToFront(item);	l.mutex.Unlock();	var data cacheItem;	json.Unmarshal(item.Value.([]byte), &data);	return data.Val;}//删除数据func (l *LRU) del(key string) error {	e, item := l.exist(key);	if !e {		return errors.New(key + "不存在");	}	l.mutex.Lock();	l.curNum--;	//删除链表元素	l.data.Remove(item);	l.mutex.Unlock();	return nil;}//判断是否存在func (l *LRU) exist(key string) (bool, *list.Element) {	var data cacheItem;	//循环链表，判断key是否存在	for v := l.data.Front(); v != nil; v = v.Next() {		json.Unmarshal(v.Value.([]byte), &data);		if key == data.Key {			return true, v;		}	}	return false, nil;}//返回长度func (l *LRU) len() int {	return l.curNum;}//打印链表func (l *LRU) print() {	var data cacheItem;	for v := l.data.Front(); v != nil; v = v.Next() {		json.Unmarshal(v.Value.([]byte), &data);		fmt.Println("key:", data.Key, " value:", data.Val);	}}//创建一个新的LRUfunc LRUNew(maxNum int) *LRU {	return &LRU{		maxNum: maxNum,		curNum: 0,		mutex:  sync.Mutex{},		data:   list.New(),	};}func main() {	lru := LRUNew(5);	lru.add("1111", 1111);	lru.add("2222", 2222);	lru.add("3333", 3333);	lru.add("4444", 4444);	lru.add("5555", 5555);	lru.print();	//get成功后，可以看到3333元素移动到了链表头	fmt.Println(lru.get("3333"));	lru.print();	//再次添加元素，如果超过最大数量，则删除链表尾部元素，将新元素添加到链表头	lru.add("6666", 6666);	lru.print();	lru.del("4444");	lru.print();	lru.set("2222", "242424");	lru.print();}