LRU（Least Recently Used，最近使用最少，最久未使用）是一种缓存淘汰算法。缓存是计算机中用来提高访问资源速度的一种方法。将从数据库、硬盘、网络或其他地方读取到的数据暂存于方便读取的地方（也就是缓存（Cache）），等再次读取时就不必重新在上述地方查找和读取一遍。通常来说，缓存的空间都是有限的，因此只应该保留经常会被读取的数据，而不常被读取的数据则该被淘汰。

LRU是众多缓存淘汰算法中的一种，在缓存容量满了时，淘汰最久没有被访问的元素。他的算法设计很简单。首先是数据结构设计。对于每个缓存中元素，可以用键值对的方式存储，读取时通过键读取对应的数据。缓存是一个优先队列，元素的优先级在运行中会不断改变。每次访问一个键，该键对应元素优先级设为最低（也就是最近访问）。每次插入一个新元素，如果键已存在，则更新其值，并设为最近使用。如果键不存在，则检查容量满了没有。如果满了，则将缓存中优先级最高的元素，也就是最久未访问的元素删除。然后再新增元素，并设为最近访问。

这个是我的伪代码，凑合着看吧

元素 键:值
缓存容量 N
缓存 [缓存元素0，缓存元素1，。。。，缓存元素N]

访问键为x的元素：

    如果x在缓存中，则将x对应的元素的值返回，并将该元素设为最近访问
    如果不在，则返回空

新增键为y，值为z的元素：
    
    如果缓存中已经存在键为y的元素
        则更新其值为z，并设为最近访问
    如果缓存中不存在键为y的元素
        检查缓存中元素数量是否达容量
            如果是则删除最久未访问的元素
        新增键为y，值为z的元素到缓存中，并将该元素设为最近访问

具体如何实现这个优先队列，一种简单的实现是，让每个缓存的元素维护一个时间变量。如果元素被访问或是新增，则元素时间置0，其余元素时间+1。当缓存满了需要淘汰内存，则将时间值最大的元素删除。这种设计很明显，时间复杂度很高，每次插入和读取都要更新所有元素的时间，淘汰时，也必须遍历找出时间最大的元素。

更高效的做法是，使用哈希表和双向链表实现。哈希表的特点是查找时间复杂度大部分时候为O(1)，但是不存在优先级，甚至不存在先后顺序。而双向链表的特点是，在头尾新增和删除高效，但是查找效率低。

所以，可以设置这样的一个缓存结构。一个哈希表用于储存键和对应元素的地址，用于快速访问和判断元素是否存在。双向链表中，每个节点存储一个元素的键值对。当某个元素被制为最优先，则将对应节点置于链表首。当缓存容量满了，则抛弃链表末尾的节点，并同时将哈希表中的键删除。

为了方便操作，链表采用的双向链表，目的是方便删除。双向链表中的头尾节点是不含有用数据的哑节点。双向链表中节点也要存值的原因是，在抛弃元素时。哈希表可从被抛弃的元素中，很方便地获取对应键。

下面是我的代码

对于双向链表数据结构，我实现了这几个操作，方便被缓存调用。

type LRUDoubleListNode struct {
    prev, next *LRUDoubleListNode
    key, value int
}

// 双向链表
type LRUDoubleList struct {
    head, tail *LRUDoubleListNode
}

// 构造一个初始双向链表
func NewLRUDoubleList() LRUDoubleList {
    l := LRUDoubleList{}
    l.head = &LRUDoubleListNode{}
    l.tail = &LRUDoubleListNode{}
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

// 将节点添加到链表首
func (l *LRUDoubleList) addToHead(node *LRUDoubleListNode) {
    headNext := l.head.next
    l.head.next = node
    headNext.prev = node
    node.next = headNext
    node.prev = l.head
}

// 移除节点
func (l *LRUDoubleList) remove(node *LRUDoubleListNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// 移除链表尾节点
func (l *LRUDoubleList) removeFromTail() *LRUDoubleListNode {
    if l.head.next == l.tail {
        return nil
    }
    node := l.tail.prev
    l.remove(node)
    return node
}

对于缓存结构，则实现了这些操作

// 缓存结构
type LRUCache struct {
    capacity  int
    keymap    map[int]*LRUDoubleListNode
    cache LRUDoubleList
}

// 构造一个缓存
func NewLRUCache(capacity int) LRUCache {
    lru := LRUCache{capacity: capacity}
    lru.keymap = make(map[int]*LRUDoubleListNode)
    lru.cache = NewLRUDoubleList()
    return lru
}

// 设某个键为最近访问
func (lru *LRUCache) setMostRecently(key int) {
    node := lru.keymap[key]
    lru.cache.remove(node)
    lru.cache.addToHead(node)
}

// 新增元素
func (lru *LRUCache) addItem(key, Value int) {
    node := &LRUDoubleListNode{key: key, value: Value}
    lru.keymap[key] = node
    lru.cache.addToHead(node)
}

// 移除元素
func (lru *LRUCache) removeItem(key int) {
    node := lru.keymap[key]
    lru.cache.remove(node)
    delete(lru.keymap, key)
}

// 移除最久未访问元素
func (lru *LRUCache) removeLeastRecently() {
    node := lru.cache.removeFromTail()
    delete(lru.keymap, node.key)
}

// 读取操作
func (lru *LRUCache) Get(key int) int {
    if item, ok := lru.keymap[key]; ok {
        lru.setMostRecently(item.key)
        return item.value
    } else {
        return -1
    }

}

// 新增操作
func (lru *LRUCache) Put(key int, value int) {
    if item, ok := lru.keymap[key]; ok {
        item.value = value
        lru.setMostRecently(item.key)
    } else {
        if len(lru.keymap) >= lru.capacity {
            lru.removeLeastRecently()
        }
        lru.addItem(key, value)
    }
}