Golang实现LRU缓存淘汰算法

设计原则：如果一个数据在最近一段时间被访问次数最少，那么在将来它被访问的可能性也很小。

实现思路：使用map来存储键值对，借助Golang自带的双向链表来实现

原理：

添加元素时，放到链表头
缓存命中，将元素移动到链表头
缓存满了之后，将链表尾的元素删除

package main

import (
	"container/list"
	"fmt"
)

// LRU 使用双向链表结合map表实现的 LRU
type LRU struct {
	l   *list.List
	m   map[int]*list.Element
	len int
	cap int
}

// Data lru中的数据
type Data struct {
	Key int
	Val int
}

// NewLRUData 根据 key, value 新建 LRUData
func NewLRUData(key, val int) *Data {
	return &Data{Key: key, Val: val}
}

// NewLRU 返回初始化 LRU
func NewLRU(cap int) *LRU {
	if cap <= 0 {
		return nil
	}
	return &LRU{
		l:   list.New(),
		m:   make(map[int]*list.Element, cap),
		cap: cap,
	}
}

// Get 获取数据
func (lru *LRU) Get(key int) int {
	// 判断是否存在
	if e, ok := lru.m[key]; ok {
		// 移动到最左边
		lru.l.MoveToFront(e)
		return e.Value.(*Data).Val
	}
	return -1
}

// Put 设置数据
func (lru *LRU) Put(key, val int) {
	// 判断是否存在, 存在则为更新
	if e, ok := lru.m[key]; ok {
		e.Value = NewLRUData(key, val)
		lru.l.MoveToFront(e)
		return
	}
	// 缓存满了
	if lru.l.Len() >= lru.cap {
		// 删除最右边数据
		e := lru.l.Back()
		delete(lru.m, e.Value.(*Data).Key)
		lru.l.Remove(e)
	}
	// 添加值最左边
	lru.l.PushFront(NewLRUData(key, val))
	lru.m[key] = lru.l.Front()
}