Go语言LRU算法

package main
import (
  "fmt"
)
// 定义节点结构体
type node struct {
  key   string
  value string
  next  *node
  prev  *node
}
// 定义lru结构体
type lru struct {
  //缓存最大数量
  k int
  // 存放节点数据
  cache map[string]*node
  //头节点
  head *node
  // 尾节点
  tail *node
}
// 工厂方法，构造一个LRU缓存对象
func NewLRUCache(k int) *lru {
  return &lru{k: k}
}
// 对外开放的Get方法
func (lru *lru) Get(key string) string {
  if lru.cache == nil {
    return ""
  }
  n, ok := lru.cache[key]
  if ok {
    value := n.value
    //更新到头节点
    lru.moveNodeToHead(n)
    return value
  } else {
    return ""
  }
}
// 对外开放的Set方法
func (lru *lru) Set(key string, value string) {
  //初始化map
  if lru.cache == nil {
    lru.cache = make(map[string]*node)
  }
  n, ok := lru.cache[key]
  if ok {
    //更新缓存
    n.value = value
  } else {
    //创建新节点
    n = &node{key: key, value: value}
    // 添加到map中
    lru.cache[key] = n
    //如果超过缓存大小，移除最后一个节点
    if len(lru.cache) > lru.k {
      lru.removeTail()
    }
  }
  // 更新节点为头节点
  lru.moveNodeToHead(n)
}
//将指定节点移到头节点
func (lru *lru) moveNodeToHead(n *node) {
  //如果头节点和尾节点都是空，说明是第一次添加数据
  if lru.head == nil && lru.tail == nil {
    lru.head = n
    lru.tail = n
    return
  }
  // 如果是头节点，那么不动
  if lru.head == n {
    return
  }
  nextNode := n.next
  prevNode := n.prev
  // 如果是尾节点，那么要先与上一个节点断开
  if n == lru.tail {
    prevNode.next = nil
    n.prev = nil
  } else if prevNode != nil && nextNode != nil {
    //如果是中间节点，要与前后节点都断开
    nextNode.prev = prevNode
    prevNode.next = nextNode
    n.prev = nil
  }
  //把节点移到到头节点
  n.next = lru.head
  lru.head.prev = n
  lru.head = n
}
//移除最后一个节点
func (lru *lru) removeTail() {
  // 如果尾节点wei空，那么清空数据直接返回
  if lru.tail == nil {
    lru.cache = nil
    return
  }
  tailPrev := lru.tail.prev
  // 尾节点与上一个节点断开
  lru.tail.prev = nil
  if tailPrev != nil {
    tailPrev.next = nil
  }
  // 把上一个节点置为尾节点
  lru.tail = tailPrev
  // 从map中删除尾节点数据
  delete(lru.cache, lru.tail.key)
}
// 重写String方法，自定义打印结果
func (lru *lru) String() string {
  point := lru.head
  result := ""
  flag := "\t"
  for point != nil {
    if len(result) > 0 {
      result = fmt.Sprintf("%v%v[%v:%v]", result, flag, point.key, point.value)
    } else {
      result = fmt.Sprintf("[%v:%v]", point.key, point.value)
    }
    point = point.next
  }
  return result
}
func main() {
  LRUCache := NewLRUCache(5)
  LRUCache.Set("1", "1")
  LRUCache.Set("2", "2")
  LRUCache.Set("3", "3")
  LRUCache.Set("4", "4")
  LRUCache.Set("5", "5")
  //打印缓存数据，验证容量是否起作用
  fmt.Println(LRUCache)
  //设置超过最大容量的数据
  LRUCache.Set("6", "6")
  //打印缓存数据，验证超过容量是否起作用
  fmt.Println(LRUCache)
  //查询头节点数据
  fmt.Println(LRUCache.Get("6"))
  //打印缓存数据
  fmt.Println(LRUCache)
  //查询非头节点数据
  fmt.Println(LRUCache.Get("4"))
  //打印缓存数据
  fmt.Println(LRUCache)
  //查询尾节点数据
  fmt.Println(LRUCache.Get("2"))
  //打印缓存数据
  fmt.Println(LRUCache)
}
复制代码