LRU Cache "Golang Implementation"
LRU has a wide range of applications and can be found in almost any place where there is a need for caching. This includes memory paging algorithms, maintaining keys in Redis, and more.
The structure of LRU is relatively simple. In order to achieve O(1) efficiency, it uses a doubly linked list and a hash table to store data.
package lru
type Node struct {
Key string
Value interface{}
Pre *Node
Suf *Node
}
type DLink struct {
Len int
Head *Node
Tail *Node
}
func NewDLink() *DLink {
dl := &DLink{
Len: 0,
Head: &Node{},
Tail: &Node{},
}
dl.Head.Suf = dl.Tail
dl.Tail.Pre = dl.Head
return dl
}
func (dl *DLink) Show() {
curr := dl.Head
for curr != dl.Tail {
print(curr.Key, ",")
curr = curr.Suf
}
println("\n------------")
}
func (lc *LruCache) Show() {
lc.link.Show()
}
func (dl *DLink) addLast(n *Node) {
n.Pre = dl.Tail.Pre
n.Suf = dl.Tail
dl.Tail.Pre.Suf = n
dl.Tail.Pre = n
dl.Len++
}
func (dl *DLink) remove(n *Node) {
n.Suf.Pre = n.Pre
n.Pre.Suf = n.Suf
dl.Len--
}
func (dl *DLink) removeFirst() *Node {
if dl.Head.Suf == dl.Tail {
return nil
}
first := dl.Head.Suf
dl.remove(first)
dl.Len--
return first
}
func (lc *LruCache) makeFirst(key string) {
lc.link.remove(lc.CacheMap[key])
lc.link.addLast(lc.CacheMap[key])
}
func (lc *LruCache) recent(key string, value interface{}) {
n := &Node{
Key: key,
Value: value,
}
lc.link.addLast(n)
lc.CacheMap[key] = n
}
func (lc *LruCache) deleteKey(key string) {
lc.link.remove(lc.CacheMap[key])
lc.CacheMap[key] = nil
}
func (lc *LruCache) removeLRU() {
f := lc.link.removeFirst()
lc.CacheMap[f.Key] = nil
}
func (lc *LruCache) Put(key string, value interface{}) {
temp := lc.CacheMap[key]
if temp != nil {
temp.Value = value
lc.makeFirst(temp.Key)
} else {
if lc.MaxSize == lc.link.Len {
lc.removeLRU()
}
n := &Node{
Key: key,
Value: value,
}
lc.link.addLast(n)
lc.CacheMap[key] = n
}
}
func (lc *LruCache) Get(key string) interface{} {
lc.makeFirst(key)
return lc.CacheMap[key].Value
}
func New(maxSize int) *LruCache {
return &LruCache{
MaxSize: maxSize,
CacheMap: make(map[string]*Node, maxSize),
link: NewDLink(),
}
}
type LruCache struct {
MaxSize int
CacheMap map[string]*Node
link *DLink
}