go实现lru

原理：定义lru结构的时候主要包含一个哈希表和双向链表，哈希表便于获取指定key的数据（复杂度O(1)），把每次热点数据都更新到表头，则从表头到表尾访问热度依次递减，溢出的时候直接删除表尾数据即可。

go代码实现：

package main

import (
	"fmt"
	"log"
)

func main() {
	log.Print("zlru...")

	l := NewLruCache(5)
	l.Put(1, 11)
	l.Put(2, 22)
	l.Put(3, 33)
	l.Put(4, 44)
	l.Put(5, 55)

	log.Println("case1------------------------------->")
	log.Printf("head: %+v", l.list.head)
	log.Printf("tail: %+v", l.list.tail)
	log.Printf("len: %d", l.size)
	l.list.Range()

	log.Println("case2------------------------------->")
	l.Put(6, 66)
	log.Printf("head: %+v", l.list.head)
	log.Printf("tail: %+v", l.list.tail)
	log.Printf("len: %d", l.size)
	l.list.Range()

	log.Println("case3------------------------------->")
	l.Get(3)
	log.Printf("head: %+v", l.list.head)
	log.Printf("tail: %+v", l.list.tail)
	log.Printf("len: %d", l.size)
	l.list.Range()
}

func (l *linkList) Range() {
	for node := l.head; node != nil; node = node.next {
		fmt.Printf("key: %d, value: %d \n", node.key, node.value)
	}
}

// 双向链表节点
type linkNode struct {
	key   int
	value int
	prev  *linkNode
	next  *linkNode
}

// 双向链表
type linkList struct {
	head *linkNode
	tail *linkNode
}

// lru缓存结构
type lruCache struct {
	cap      int
	size     int
	cacheMap map[int]*linkNode
	list     *linkList
}

func newNode(k, v int) *linkNode {
	return &linkNode{
		key:   k,
		value: k,
	}
}

// NewLruCache 初始化一个新的lru
func NewLruCache(cap int) *lruCache {
	l := &lruCache{
		cap:  cap,
		size: 0,
	}
	l.cacheMap = make(map[int]*linkNode, 0)
	l.list = &linkList{
		head: nil,
		tail: nil,
	}

	return l
}

// 主要是需要实现两个操作：Get/Put
// Get 获取指定key的值：
//     1. 如果key存在，则需要将该key所在的节点：（1）从当前位置删除，（2）移动到链表头部
//     2. 如果不存在直接返回-1
// Put 新增元素：
//     1. 如果key存在，则需要将该key所在的节点：（1）更新当前节点的值，（2）从当前位置删除，（2）移动到链表头部
//     2. 如果key不存在，则需要：（1）新生成一个节点NewNode, （2）将NewNode放在链表头部，（3）链表长度加1，如果此时链表长度未超过容量cap则直接返回，（4）如果加1后的链表长度超过容量则删除链表末尾节点，删除map中的元素
// 其实归结下来有以下几个基础操作：
//  （1）删除一个已经存在的元素 （2）删除链表中末尾元素（3）将元素放在链表头部

func (l *lruCache) removeNode(node *linkNode) {
	// 如果node是最后一个元素, 并且prev元素不为空
	if node.next == nil && node.prev != nil {
		node.prev.next = nil
		l.list.tail = node.prev
		return
	}

	// 如果node是第一个元素, 并且next元素不为空
	if node.prev == nil && node.next != nil {
		node.next.prev = nil
		l.list.head = node.next
		return
	}

	// 如果只有一个元素
	if node.prev == nil && node.next == nil {
		l.list.tail = nil
		l.list.head = nil
		return
	}

	// 删除中间元素
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (l *lruCache) removeTail() {
	if l.list.tail == nil {
		return
	}
	l.removeNode(l.list.tail)
	delete(l.cacheMap, l.list.tail.key)
}

func (l *lruCache) moveHead(node *linkNode) {
	// 一个元素都没有
	if l.list.head == nil {
		l.list.head = node
		l.list.tail = node
		return
	}

	headNode := l.list.head
	// 新节点的next指向头部节点
	node.next = headNode
	// 头部节点的prev指向新节点
	headNode.prev = node
	// 新节点的prev设置为nil
	node.prev = nil
	// 双向链表的头部指向新的节点
	l.list.head = node
}

func (l *lruCache) Get(key int) int {
	// 判断key是否存在
	node, ok := l.cacheMap[key]
	if !ok {
		return -1
	}

	// 删除节点在之前的位置
	l.removeNode(node)
	// 将节点移动到头部
	l.moveHead(node)
	return node.value
}

func (l *lruCache) Put(key, value int) {
	// 判断节点是否存在
	node, ok := l.cacheMap[key]
	if !ok {
		// 如果不存在则需要新生产一个node， 并指向链表头部
		newNode := newNode(key, value)
		// 向cap里面新增一对k/v
		l.cacheMap[key] = newNode
		// 将新增的node放在链表头部
		l.moveHead(newNode)
		// 链表长度加1
		l.size++
		// 如果长度超过容量则需要删除链表末尾元素
		if l.size > l.cap {
			l.removeTail()
			l.size--
		}
		return
	}

	// 如果新增元素已经存在
	// 更新元素的值
	node.value = value
	// 将元素从当前位置删除
	l.removeNode(node)
	// 将元素移动到链表头部
	l.moveHead(node)
}