使用go语言的list实现一个简单的LRU缓存

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);
        }
}

//创建一个新的LRU
func 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();
}