go实现LRU cache
1. LRU简介1.1 概述缓存资源通常比较昂贵,通常数据量较大时,会竟可能从较少的缓存满足尽可能多访问,这里有一种假设,通常最近被访问的数据,那么它就有可能会被后续继续访问,基于这种假设,将所有的数据按访问时间进行排序,并按驱逐出旧数据,那么存在缓存的数据就为热点数据,这样既节省了内存资源,又极大的满足了访问.LRU(Least recently used)算法就是基于这种假设的一直缓存置换算法. 1.2 算法流程
假设缓存大小为4,而写入顺序为A B C D E D F.访问顺序分为写入以及读取两种操作,写入需要更新访问时间,并且当数据到达最大缓存时需要逐出数据,而读取只会更新访问时间,写入置换算法流程如上图所示. 当未到达缓存大小时,所有数据按写入存储,并记录写入次序. 2 go实现2.1思路采用go,可以使用list加map实现LRU cache,具体思路为: 读取时,从map中查询,则直接将List中该值移动到最前面,返回查询结果. 为保证并发安全,需要引入读写锁. 2.2 关键代码完整代码见: https://github.com/g4zhuj/cache
func (c *MemCache) Set(key string,value interface{}) { c.mutex.Lock() defer c.mutex.Unlock() if c.cache == nil { c.cache = make(map[interface{}]*list.Element) c.cacheList = list.New() } //判断是否在map中,如果在map中,则将value从list中移动到前面. if ele,ok := c.cache[key]; ok { c.cacheList.MoveToFront(ele) ele.Value.(*entry).value = value return } //如果不再map中,将值存到List最前面 ele := c.cacheList.PushFront(&entry{key: key,value: value}) c.cache[key] = ele //判断是否到达容量限制,到达容量限制时删除List中最后面的值. if c.maxItemSize != 0 && c.cacheList.Len() > c.maxItemSize { c.RemoveOldest() } }
func (c *MemCache) Get(key string) (interface{},bool) { c.mutex.RLock() defer c.mutex.RUnlock() c.gets.Add(1) //如果读取到值,移动在List中位置,并返回value if ele,hit := c.cache[key]; hit { c.hits.Add(1) c.cacheList.MoveToFront(ele) return ele.Value.(*entry).value,true } return nil,false } 3. 参考https://en.wikipedia.org/wiki... (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |