借助go标准库container/list 双向链表，来实现LRU

    LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量满的时候，优先淘汰最近很少使用的数据。
    实现 LRU 缓存的常用方法是使用有界队列。实现 LRU 的关键是将所有最近使用的数据放在队列的开头。在每次插入之前，我们检查队列是否已满。如果队列已满，我们将删除其最后一个元素，并将新节点插入队列的开头。如果队列未满，我们只需将数据添加到队列的开头。

    LRU缓存的思想

    • 固定缓存大小，需要给缓存分配一个固定的大小。
    • 每次读取缓存都会改变缓存的使用时间，将缓存的存在时间重新刷新。
    • 需要在缓存满了后，将最近最久未使用的缓存删除，再添加最新的缓存。
      1：加入新的数据
      2：队列空间满了的时候，尾部的数据会被淘汰掉
      3：如果要访问队列中的数据，该数据会被移动到队列的头部

    缺点：频繁地访问，会造成数据被访问到的几率会下降，此外，这种normal模式也叫做LRU-1，即最近使用过1次。
    【命中率】
    当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
    【复杂度】
    实现简单。
    【代价】
    命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。

    1. package main
    3. import (
    4.     "container/list"
    5.     "errors"
    6.     "fmt"
    7. )
    9. type CacheNode struct {
    10.     Key,Value interface{}
    11. }
    13. func (cnode *CacheNode) NewCacheNode(k,v interface{})  *CacheNode {
    14.     return &CacheNode{k,v}
    15. }
    17. type  LRUCache struct {
    18.     Capacity  int
    19.     dlist *list.List
    20.     cacheMap  map[interface{}]*list.Element
    21. }
    23. func NewLRUCache(cap int) *LRUCache {
    24.     return  &LRUCache{
    25.         Capacity:cap,
    26.         dlist: list.New(),
    27.         cacheMap: make(map[interface{}]*list.Element)}
    28. }
    31. func (lru *LRUCache) Size() int {
    32.     return lru.dlist.Len()
    33. }
    35. func (lru *LRUCache) Set(k,v interface{}) error {
    36.     if lru.dlist == nil {
    37.         return errors.New("LRUcache 结构未初始化")
    38.     }
    39.     if pElement, ok := lru.cacheMap[k]; ok {
    40.         lru.dlist.MoveToFront(pElement)
    41.         pElement.Value.(*CacheNode).Value = v
    42.         return nil
    43.     }
    45.     newElement := lru.dlist.PushFront(&CacheNode{k,v})
    46.     lru.cacheMap[k] = newElement
    48.     if lru.dlist.Len() > lru.Capacity {
    49.         lastElement := lru.dlist.Back()
    50.         if lastElement == nil {
    51.             return nil
    52.         }
    53.         CacheNode := lastElement.Value.(*CacheNode)
    54.         delete(lru.cacheMap,CacheNode.Key)
    55.         lru.dlist.Remove(lastElement)
    56.     }
    57.     return nil
    58. }
    62. func (lru *LRUCache) Get(k interface{}) (v interface{}, ret bool, err error) {
    63.     if lru.cacheMap == nil {
    64.         return v,false,errors.New("LRUCache 结构体未初始化")
    65.     }
    66.     if pElement, ok := lru.cacheMap[k]; ok {
    67.         lru.dlist.MoveToFront(pElement)
    68.         return pElement.Value.(*CacheNode).Value,true,nil
    69.     }
    70.     return  v,false,nil
    71. }
    74. func (lru *LRUCache) Remove(k interface{}) bool {
    75.     if lru.cacheMap == nil {
    76.         return false
    77.     }
    79.     if pElement, ok := lru.cacheMap[k];ok {
    80.         cacheNode := pElement.Value.(*CacheNode)
    81.         delete(lru.cacheMap,cacheNode.Key)
    82.         lru.dlist.Remove(pElement)
    83.         return true
    84.     }
    85.     return false
    86. }
    88. func main() {
    89.     lru := NewLRUCache(3)
    90.     lru.Set(10,"value1")
    91.     lru.Set(20,"value2")
    92.     lru.Set(30,"value3")
    93.     lru.Set(50,"value5")
    94.     lru.Get(10)
    95.     lru.Get(20)
    96.     //lru.Set(50,"value5")
    99.     fmt.Println("LRU size", lru.Size())
    101.     v,ret,_ := lru.Get(30)
    102.     if ret {
    103.         fmt.Println("Get(30):", v)
    104.     }
    105.     //if lru.Remove(30) {
    106.     //    fmt.Println("Remove(30): true")
    107.     //} else {
    108.     //    fmt.Println("Remove(30): false")
    109.     //}
    110.     fmt.Println("LRU size", lru.Size())
    112.     fmt.Println(lru.dlist.Front().Value)
    113.     fmt.Println(lru.dlist.Back().Value)
    114. }