流水的面试题，铁打的LRU算法…今天来打打铁。

LRU算法的设计

lru就是一种淘汰策略，当内存不够的时候，淘汰掉最近最少使用的内个。我们可以把整个cache看做一个队列，假设每次都是从队尾进入，那么队头的内个就是最近不使用的。
显然这个cache满足以下几个特点：

  • cache中的元素都是有序的。区分最近有没有使用，当容量满了之后删除最近没有使用的内个
  • 每次需要快速定位到内个需要背删除的元素，并找到其存储的值
  • 每次访问了cache中的某个key，需要将元素变为最近使用，也就是需要快速删除和插入元素

普通的数据结构是无法满足上述特点的，我们可以用 哈希表+双向链表 这个算法核心也是这个

哈希表：map,存储key -> value 用于快速找到对应的值
双向链表：用于快速删除插入元素，由多个node节点组成，每个node节点中元素是key-value

代码实现

首先定义node结构体

  1. //双向链表 中的每一个节点的结构体
  2. type Node struct {
  3.     key,value int
  4.     prev,next *Node
  5. }

再定义双向链表，并且实现链表的插入删除等功能

  1. //双向链表结构体
  2. type DoubleList struct {
  3.     //虚拟头尾节点
  4.     head,tail *Node
  5.     size int
  6. }
  8. //在链表尾部添加节点node
  9. func (dl *DoubleList) addLast (node *Node) {
  10.     node.prev = dl.tail.prev //新加的node节点前指针 指向 链表的尾部的前指针。
  11.     node.next = dl.tail  
  12.     dl.tail.prev.next = node
  13.     dl.tail.prev = node
  14.     dl.size++
  15. }
  17. //删除链表中的节点node 当put一个key存在value不同时，做的是先删除后添加的操作，这样新加的永远在队尾
  18. func (dl *DoubleList) remove (node *Node) {
  19.     node.prev.next = node.next
  20.     node.next.prev = node.prev
  21.     dl.size--
  22. }
  24. //删除链表第一个真实元素，并且返回该元素 这就是删除最近未使用的功能
  25. func (dl *DoubleList) removeFirst () *Node{
  26.     if dl.head.next == dl.tail {
  27.         return nil
  28.     }
  29.     first := dl.head.next
  30.     remove(first)
  31.     return first
  32. }

前置的双向链表准备完毕了，链表功能也都实现了，现在我们要定义LRU的核心的结构 “哈希表+双向链表”

  1. type LRUcache struct {
  2.     //map 用于快速找到精确的key对应的value 
  3.     cacheMap map[int]*Node
  4.     //双向链表
  5.     cacheList *DoubleList
  6.     //最大容量
  7.     capacity int
  8. }

至此，就可以完成功能代码了

  1. func Constructor(capacity int) LRUCache {
  2.     lru := LRUCache{
  3.         cacheMap : map[int]*Node{},
  4.         cacheList: &DoubleList{
  5.             head: &Node{key: 0,value: 0}, //虚拟一个头节点
  6.             tail: &Node{key: 0,value: 0}, //虚拟一个尾结点
  7.         },
  8.         capacity:capacity,
  9.     }
  10.     //把双向链表虚拟头尾节点 链接起来
  11.     lru.cacheList.head.next = lru.cacheList.tail
  12.     lru.cacheList.tail.prev = lru.cacheList.head
  13.     return lru
  14. }
  17. func (this *LRUCache) Get(key int) int {
  18.     //判断map中是否存在key
  19.     if node,ok := this.cacheMap[key]; ok {
  20.         //存在的话，将这个节点变成最近使用过，也就是先删除，在放到队尾
  21.         this.cacheList.remove(node)
  22.         this.cacheList.addLast(node)
  23.         return node.value
  24.     }
  25.     return -1
  26. }
  29. func (this *LRUCache) Put(key int, value int)  {
  30.     //put复杂很多，如果key存在，那就删除之前的，将现在的放入队尾。如果不存在，需要插入队尾并判断容量
  31.     if node,ok := this.cacheMap[key]; ok {
  32.         this.cacheList.remove(node)
  33.     }
  35.     if this.capacity == this.cacheList.size {
  36.         first := this.cacheList.removeFirst()
  37.         delete(this.cacheMap,first.key)
  38.     }
  39.     newNode := &Node{key:key,value:value}
  40.     this.cacheList.addLast(newNode)
  41.     this.cacheMap[key] = newNode
  42. }