LRU

缓存文件置换机制是电脑处理缓存存储器的一种机制。

电脑存储器空间的大小固定，无法容纳服务器上所有的文件，所以当有新的文件要被置换入缓存时，必须根据一定的原则来取代掉适当的文件。此原则即所谓缓存文件置换机制。

缓存文件置换方法有：

• 先进先出算法（FIFO）：最先进入的内容作为替换对象
• 最近最少使用算法（LFU）：最近最少使用的内容作为替换对象
• 最久未使用算法（LRU）：最久没有访问的内容作为替换对象
• 非最近使用算法（NMRU）：在最近没有使用的内容中随机选择一个作为替换对象

用GO实现简单的LRU：

大致思路是，用一个双向链表，链表头部存储最近使用过的缓存，尾部存储最近最久未使用过的缓存。

插入的时候，如果缓存未满，直接插到链表头部即可，否则将尾部的缓存移除，再插入。

因为涉及到插入删除操作，加入头结点（dummy node）可以更方便。

双向链表速度还不够快，再引入一个map来存储链表所有的节点。

package main

import "fmt"

type LRUCache struct {
	limit   int
	hashMap map[int]*Node
	head    *Node
	tail    *Node
}

type Node struct {
	key  int
	val  int
	pre  *Node
	next *Node
}

func NewNode(k, v int) *Node {
	return &Node{
		key: k,
		val: v,
	}
}

func NewLRUCache(cap int) LRUCache {
	c := LRUCache{
		limit:   cap,
		hashMap: make(map[int]*Node),
		head:    NewNode(0, 0), // dummy node
		tail:    NewNode(0, 0), // dummy node
	}
	c.head.next = c.tail
	c.tail.pre = c.head
	return c
}

func (c *LRUCache) Get(key int) int {
	if node, ok := c.hashMap[key]; ok {
		c.moveToHead(node)
		return node.val
	}
	// if not found, return -1
	return -1
}

func (c *LRUCache) Put(k, v int) {
	if node, ok := c.hashMap[k]; !ok {
		if len(c.hashMap) >= c.limit {
			tail := c.removeTail()
			delete(c.hashMap, tail.key)
		}
		node = NewNode(k, v)
		c.hashMap[k] = node
		c.addToHead(node)
	} else {
		node.val = v
		c.moveToHead(node)
	}
}

func (c *LRUCache) moveToHead(node *Node) {
	c.removeNode(node)
	c.addToHead(node)
}

func (c *LRUCache) removeNode(node *Node) {
	node.pre.next = node.next
	node.next.pre = node.pre
}

func (c *LRUCache) removeTail() *Node {
	tail := c.tail.pre
	c.removeNode(tail)
	return tail
}

func (c *LRUCache) addToHead(node *Node) {
	node.pre = c.head
	node.next = c.head.next
	c.head.next.pre = node
	c.head.next = node
}

func main() {
	cache := NewLRUCache(3)
	cache.Put(1,1)
	cache.Put(2,2)
	cache.Put(3,3)
	cache.Put(4,4)
	fmt.Println(cache.Get(3))
}