思路

LRU 缓存机制可以通过哈希表辅以双向链表实现，用一个哈希表和一个双向链表维护所有在缓存中的键值对。

• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
• 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

• 对于 get 操作，首先判断 key 是否存在：

  • 如果 key 不存在，则返回 −1；
  • 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

• 对于 put 操作，首先判断 key 是否存在：

  • 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
  • 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。

代码

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/

type doubleListNode struct {
	Key int
	Val int
	Pre *doubleListNode
	Next *doubleListNode
}

type LRUCache struct {
	Capacity int                     //合法容量
	Head     *doubleListNode
	Tail     *doubleListNode
	Keys     map[int]*doubleListNode //哈希表
}

func Constructor(capacity int) LRUCache { //构造器
	return LRUCache{
		Keys: make(map[int]*doubleListNode),
		Capacity: capacity,
	}
}

func (this *LRUCache) Get(key int) int { //返回key对应的value
	if node := this.Keys[key]; node != nil { //在哈希表中找到该key
		this.deleteNode(node)  //从原先链表中删除
		this.newHead(node)     //再插入成为链表头节点
		return node.Val
	}
	return -1 //若哈希表中没有该key
}

func (this *LRUCache) Set(key int, value int)  { //把一对key,value加入LRUCache中
	if node := this.Keys[key]; node != nil { //在哈希表中找到有这key
		node.Val = value                     //更新对应节点的Val
		this.deleteNode(node)
		this.newHead(node)
		return
	} else { //在哈希表中没有找到该key
		node = &doubleListNode{Key: key, Val: value} //建立新的节点
		this.Keys[key] = node
		this.newHead(node)
		if this.Capacity > 0 { //若LRUCache中合法容量还有
			this.Capacity--
		} else {               //若LRUCache合法容量已满
			this.Keys[this.Tail.Key] = nil //删除哈希表中链表尾节点对应的key
			this.deleteNode(this.Tail)     //把链表尾节点删除
		}
	}
}

//把给定节点插入链表中作为新的头节点
func (this *LRUCache) newHead(cur *doubleListNode) { 
	cur.Pre = nil
	cur.Next = this.Head
	if this.Head != nil {    //若插入前链表不是空的，即已有头节点
		this.Head.Pre = cur
	}
	this.Head = cur         //更新给定节点为新的头节点
	if this.Tail == nil {   //若链表尾节点不存在。即链表是空的
		this.Tail = cur     //把当前给定节点置为尾节点
		this.Tail.Next = nil
	}
}

//把给定节点从链表中删除
func (this *LRUCache) deleteNode(cur *doubleListNode) {
	if cur == this.Head {    //若给定节点就是头节点
		this.Head = cur.Next
		cur.Next = nil
		return
	}
	if cur == this.Tail{    //若给定节点就是尾节点
		this.Tail = cur.Pre
		cur.Pre.Next = nil
		cur.Pre = nil
		return
	}
    //若给定节点不是头节点也不是尾节点（即前后都有节点）
	cur.Pre.Next = cur.Next
	cur.Next.Pre = cur.Pre
}

func LRU( operators [][]int ,  k int ) []int {
    res := make([]int,0)
    lru := Constructor(k)
    for i := 0 ; i < len(operators) ; i++ {
        if operators[i][0] == 1 {
            lru.Set(operators[i][1],operators[i][2])
        } else {
            val := lru.Get(operators[i][1])
            res = append(res,val)
        }
    }
    return res
}