缓存淘汰策略

Set(key string, value interface) // 写数据
Get(key string) interface{}      // 读数据

type Node struct {
	key        string // 淘汰 tail 时需在维护的哈希表中删除，不是冗余存储
	val        interface{}
	prev, next *Node // 双向指针
}

type List struct {
	head, tail *Node
	size       int // 缓存空间大小
}

func (l *List) Prepend(node *Node) *Node {
	if l.head == nil {
		l.head = node
		l.tail = node
	} else {
		node.prev = nil
		node.next = l.head
		l.head.prev = node
		l.head = node
	}
	l.size++
	return node
}

func (l *List) Remove(node *Node) *Node {
	if node == nil {
		return nil
	}
	prev, next := node.prev, node.next
	if prev == nil {
		l.head = next // 删除头结点
	} else {
		prev.next = next
	}

	if next == nil {
		l.tail = prev // 删除尾结点
	} else {
		next.prev = prev
	}

	l.size--
	node.prev, node.next = nil, nil
	return node
}

// 封装数据已存在缓存的后续操作
func (l *List) MoveToHead(node *Node) *Node {
	if node == nil {
		return nil
	}
	n := l.Remove(node)
	return l.Prepend(n)
}

func (l *List) Tail() *Node {
	return l.tail
}

func (l *List) Size() int {
	return l.size
}

type LRUCache struct {
	capacity int // 缓存空间大小
	items    map[string]*Node
	list     *List
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		items:    make(map[string]*Node),
		list:     new(List),
	}
}

func (c *LRUCache) Set(k string, v interface{}) {
	// 命中
	if node, ok := c.items[k]; ok {
		node.val = v                         // 命中后更新值
		c.items[k] = c.list.MoveToHead(node) //
		return
	}

	// 未命中
	node := &Node{key: k, val: v} // 完整的 node
	if c.capacity == c.list.size {
		tail := c.list.Tail()
		delete(c.items, tail.key) // k-v 数据存储与 node 中
		c.list.Remove(tail)
	}
	c.items[k] = c.list.Prepend(node) // 更新地址
}

func (c *LRUCache) Get(k string) interface{} {
	node, ok := c.items[k]
	if ok {
		c.items[k] = c.list.MoveToHead(node)
		return node.val
	}
	return -1
}

func TestLRU(t *testing.T) {
	c := NewLRUCache(2)
	c.Set(K1, 1)
	c.Set(K2, 2)
	c.Set(K1, 100)
	fmt.Println(c.Get(K1)) // 100
	c.Set(K3, 3)
	fmt.Println(c.Get(K2)) // -1
	c.Set(K4, 4)
	fmt.Println(c.Get(K1)) // -1
	fmt.Println(c.Get(K3)) // 3
	fmt.Println(c.Get(K4)) // 4
}

Set("2", 2)
Set("1", 1)
Get(1)
Get(2)
Set("3", 3) 
Set("4", 4) // LRU 将淘汰 1，缓存链表为 4->3->2
	    // LFU 将淘汰 3，未超出容量的时段内 1 和 2 都被使用了两次，3 仅使用一次

type Node struct {
	key        string
	val        interface{}
	freq       int // 将节点从旧梯队移除时使用，非冗余存储
	prev, next *Node
}

type List struct {
	head, tail *Node
	size       int
}

type LFUCache struct {
	capacity int
	minFreq  int // 最低频率

	items map[string]*Node
	freqs map[int]*List // 不同频率梯队
}

func NewLFUCache(capacity int) *LFUCache {
	return &LFUCache{
		capacity: capacity,
		minFreq:  0,
		items:    make(map[string]*Node),
		freqs:    make(map[int]*List),
	}
}

func (c *LFUCache) Get(k string) interface{} {
	node, ok := c.items[k]
	if !ok {
		return -1
	}

	// 移到 +1 梯队中
	c.freqs[node.freq].Remove(node)
	node.freq++
	if _, ok := c.freqs[node.freq]; !ok {
		c.freqs[node.freq] = NewList()
	}
	newNode := c.freqs[node.freq].Prepend(node)
	c.items[k] = newNode // 新地址更新到 map
	if c.freqs[c.minFreq].Size() == 0 {
		c.minFreq++ // Get 的正好是当前值
	}
	return newNode.val
}

func (c *LFUCache) Set(k string, v interface{}) {
	if c.capacity <= 0 {
		return
	}

	// 命中，需要更新频率
	if val := c.Get(k); val != -1 {
		c.items[k].val = v // 直接更新值即可
		return
	}

	node := &Node{key: k, val: v, freq: 1}

	// 未命中
	// 缓存已满
	if c.capacity == len(c.items) {
		old := c.freqs[c.minFreq].Tail() // 最低最旧
		c.freqs[c.minFreq].Remove(old)
		delete(c.items, old.key)
	}

	// 缓存未满，放入第 1 梯队
	c.items[k] = node
	if _, ok := c.freqs[1]; !ok {
		c.freqs[1] = NewList()
	}
	c.freqs[1].Prepend(node)
	c.minFreq = 1
}

func TestLFU(t *testing.T) {
	c := NewLFUCache(2)
	c.Set(K1, 1)           // 1:K1
	c.Set(K2, 2)           // 1:K2->K1	
	fmt.Println(c.Get(K1)) // 1:K2 2:K1 // 1
	c.Set(K3, 3)           // 1:K3 2:K1
	fmt.Println(c.Get(K2)) // -1
	fmt.Println(c.Get(K3)) // 2:k3->k1  // 3
	c.Set(K4, 4)           // 1:K4 2:K3
	fmt.Println(c.Get(K1)) // -1
	fmt.Println(c.Get(K3)) // 1:K4 3:K3 // 3
}