LRU缓存机制

题目描述：
  运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
  获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
  写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

解题思路：
  最近刚好在看groupcache源码，里面有实现LRU算法，参照这个算法实现了题解。
  最近最少使用淘汰策略，就是在数据量达到上限时，把这段时间内最少使用的数据删除。具体到实现，就是将最近添加和查询的数据放到队列头部，需要淘汰的时候直接删除队尾数据。使用map存储节点，可以实现O(1)时间复杂度，当然不可避免的会多占用空间。

type LRUCache struct {
    maxEntry int
    ll       *list.List
    cache    map[int]*list.Element
}

type Entry struct {
    key   int
    value int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        maxEntry: capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    if nil == this.ll {
        return -1
    }

    if ele, ok := this.cache[key]; ok {
        this.ll.MoveToFront(ele)
        return ele.Value.(*Entry).value
    }

    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if nil == this.ll {
        this.ll = list.New()
        this.cache = make(map[int]*list.Element)
    }

    if ele, exist := this.cache[key]; exist {
        ele.Value.(*Entry).value = value
        this.ll.MoveToFront(ele)
        return
    }

    if this.ll.Len()+1 > this.maxEntry {
        back := this.ll.Back()
        this.ll.Remove(back)
        delete(this.cache, back.Value.(*Entry).key)
    }

    ele := this.ll.PushFront(&Entry{key, value})
    this.cache[key] = ele
}