Golang实现LRU

package Cache

import (
	"container/list"
	"errors"
)

type node struct {
	key   string
	value interface{}
}

type LRUCache struct {
	Cap     int        // 容量
	dList   *list.List // 双链表
	hashMap map[string]*list.Element
}

func New(cap int) *LRUCache {
	return &LRUCache{
		Cap:     cap,
		dList:   list.New(),
		hashMap: make(map[string]*list.Element, cap),
	}
}

func (lc *LRUCache) Volume() int {
	return lc.dList.Len()
}

func (lc *LRUCache) Get(k string) (interface{}, error) {
	if lc.dList == nil {
		return nil, errors.New("LRU not initialized")
	}

	// 命中就更新到list尾
	if v, ok := lc.hashMap[k]; ok {
		lc.dList.MoveToBack(v)
		return v.Value.(*node).value, nil
	}
	return nil, nil
}

func (lc *LRUCache) Set(k string, v interface{}) error {
	if lc.dList == nil {
		return errors.New("LRU not initialized")
	}

	// 命中，直接更新
	if v, ok := lc.hashMap[k]; ok {
		lc.dList.MoveToBack(v)
		lc.hashMap[k].Value.(*node).value = v
		return nil
	}

	// 未命中
	// 超出容量需要淘汰表头
	if lc.dList.Len() >= lc.Cap {
		ft := lc.dList.Front()
		if ft == nil {
			return nil
		}
		// 移除头部 并 从map删除（remove回返回ft的value对象，所以直接取值）
		delete(lc.hashMap, lc.dList.Remove(ft).(*node).key)
	}

	// List尾部插入 并 插入map
	lc.hashMap[k] = lc.dList.PushBack(&node{key: k, value: v})
	return nil
}

func (lc *LRUCache) Del(k string) error {
	if lc.dList == nil {
		return errors.New("LRU not initialized")
	}

	if v, ok := lc.hashMap[k]; ok {
		// 从list移除 并 从map删除
		delete(lc.hashMap, lc.dList.Remove(v).(*node).key)
		return nil
	}

	return nil
}

package LRU

// 双向链表
type Node struct {
	Key   string // 键和值
	Value interface{}
	pre   *Node // 头节点
	next  *Node // 尾节点
}

// LRU缓存
type LRUCache struct {
	volume  int              // 空间大小
	HashMap map[string]*Node // 哈希表
	head    *Node            // 头节点
	end     *Node            // 尾节点
}

func New(volume int) *LRUCache {
	return &LRUCache{
		volume:  volume,
		HashMap: make(map[string]*Node, volume),
		head:    nil,
		end:     nil,
	}
}

// 取数据
func (l *LRUCache) Get(key string) interface{} {
	// 命中：放到表尾，返回值
	if v, ok := l.HashMap[key]; ok {
		l.refreshNode(v)
		return v.Value
	}
	return -1
}

func (l *LRUCache) Set(key string, value interface{}) {
	// 设置命中：放到表尾
	if v, ok := l.HashMap[key]; ok {
		v.Value = value
		l.refreshNode(v)
		return
	}

	// 未命中，添加节点
	if len(l.HashMap) >= l.volume {
		// 1. 淘汰表头
		k := l.removeNode(l.head)
		// 2. 删除Hash内节点
		delete(l.HashMap, k)
	}
	node := &Node{
		Key:   key,
		Value: value,
	}
	l.addNode(node)
	l.HashMap[key] = node
}

// 移除双链表节点，返回键值
func (l *LRUCache) removeNode(node *Node) string {
	// 尾节点
	if node == l.end {
		l.end = l.end.pre
		l.end.next = nil
		return node.Key
	}
	// 头节点
	if node == l.head {
		l.head = l.head.next
		l.head.pre = nil
		return node.Key
	}
	// 中间
	node.pre.next = node.next
	node.next.pre = node.pre
	return node.Key
}

func (l *LRUCache) addNode(node *Node) {
	if l.end != nil {
		l.end.next = node
		node.next = nil
	}
	l.end = node
	if l.head == nil {
		l.head = node
	}
}

func (l *LRUCache) refreshNode(node *Node) {
	if node == l.end {
		return
	}
	l.removeNode(node)
	l.addNode(node)
}