golang实现LRU缓存淘汰算法-泛型版本

说明

之前这篇文章中的lru cache实现有很多考虑不周之处，加之golang1.18版本支持了泛型，趁这次机会对之前问题进行修正，顺便学习一下泛型的用法

和之前版本相比有如下改动:

• 存储顺序进行了修改，靠近头部的键值对是最近使用的，靠近尾部的键值对是最久未使用的
• 修复一些场景下空指针的问题
• 支持泛型

代码实现

type Node[K comparable, V any] struct {
	Key   K
	Value V
	pre   *Node[K, V]
	next  *Node[K, V]
}

type LRUCache[K comparable, V any] struct {
	limit   int
	HashMap map[K]*Node[K, V]
	head    *Node[K, V]
	end     *Node[K, V]
}

func Constructor[K comparable, V any](capacity int) LRUCache[K, V] {
	lruCache := LRUCache[K, V]{limit: capacity}
	lruCache.HashMap = make(map[K]*Node[K, V], capacity)
	return lruCache
}

func (l *LRUCache[K, V]) Get(key K) (val V, found bool) {
	if v, ok := l.HashMap[key]; ok {
		l.refreshNode(v)
		return v.Value, true
	} else {
		return
	}
}
func (l *LRUCache[K, V]) Put(key K, value V) {
	if v, ok := l.HashMap[key]; !ok {
		if len(l.HashMap) >= l.limit {
			oldKey := l.removeNode(l.end)
			delete(l.HashMap, oldKey)
		}
		node := &Node[K, V]{Key: key, Value: value}
		l.addNode(node)
		l.HashMap[key] = node
	} else {
		v.Value = value
		l.refreshNode(v)
	}
}

func (l *LRUCache[K, V]) refreshNode(node *Node[K, V]) {
	if node == l.head {
		return
	}
	l.removeNode(node)
	l.addNode(node)
}

func (l *LRUCache[K, V]) removeNode(node *Node[K, V]) K {
	if node == l.end && node == l.head {
		l.head = nil
		l.end = nil
		return node.Key
	}
	if node == l.end {
		if l.end.pre != nil {
			l.end.pre.next = nil
			l.end = l.end.pre
		}
	} else if node == l.head {
		if l.head.next != nil {
			l.head.next.pre = nil
			l.head = l.head.next
		}
	} else {
		node.pre.next = node.next
		node.next.pre = node.pre
		node.pre = nil
		node.next = nil
	}
	return node.Key
}

func (l *LRUCache[K, V]) addNode(node *Node[K, V]) {
	if l.end == nil {
		node.next = nil
		l.end = node
	}
	if l.head == nil {
		node.pre = nil
		l.head = node
	} else {
		node.next = l.head
		l.head.pre = node
		node.pre = nil
		l.head = node
	}
}