分析：

题解：哈希表 + 双向链表

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

• 双向链表按照被使用的顺序存储这些 key-value ，靠近链表头部的键值对是最近使用的（最近使用包括：查询、添加），而靠近尾部的键值对是很久没有使用的。这些键值对加上后继节点和前驱节点就组成了缓存数据 cache ，以节点的形式存在 双向链表中；
• 除了双向链表，哈希表存储的就是普通的哈希映射，key 对应的 value 是双向链表的节点，即 cache 缓存数据节点。

通过 哈希表 与 双向链表 的存储结构，首先通过哈希表进行查询对应的节点信息，找出缓存数据在双向链表中的节点，随后将该节点移动到双向链表的头部（依据 LRU 规则），完成 get 或者 put 的操作，查询哈希表时间复杂度为 O(1)，移动到双向链表头部时间复杂度也为 O(1)

详细策略如下：

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

• 如果 key 不存在，直接返回 -1；
• 如果 key 存在，通过哈希表找到对应的缓存数据节点 cache，并将其移动到双向链表的头部（涉及删除节点+添加头节点两个操作），最后返回该节点的值。

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

• 如果 key 不存在，使用传入的 key 和 value 创建新的缓存节点以 key-缓存节点 的键值对形式存入哈希表中，然后将这个节点缓存数据移动到双向链表的头部，节点数 + 1。然后判断节点数 size 是否超过初始化的容量 capacity ，超过了就删除双向链表的尾部节点，并删除哈希表对应的映射关系，节点数 – 1；否则什么都不做。
• 如果 key 存在，则更新节点缓存的 value 值，并且将其移动到双向链表的头部（涉及删除节点+添加头节点两个操作）。

经上述分析，查询哈希表和双向链表添加头节点、删除尾节点时间复杂度都是 O(1)。特别注意：将一个节点移动到双向链表的头部涉及两个操作，删除节点 + 添加头节点。

在双向链表中，使用 虚拟头节点 dummyHead 和 虚拟尾节点 dummyTail 来辅助构建链表。在调用构造函数时，哈希表中初始化的 虚拟头节点 和 虚拟尾节点 如下图所示：

代码：

class LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }

    }

    //使用 哈希表 + 链表 的形式 作为缓存的数据结构
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int capacity; //用于记录缓存初始化时的大小
    private int size;//用于记录增加或减少时缓存中数据的个数
    private DLinkedNode dummyHead, dummyTail;//虚拟头节点，虚拟尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummyHead = new DLinkedNode();
        dummyTail = new DLinkedNode();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 没有缓存，直接返回 -1
            return -1;
        } else{
            // 有缓存，移动到链表头部
            removeNode(node);
            addNode(node);
            return node.value;
        }
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if(node == null) {
            // 没有缓存，要存储，且移动到链表头部
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addNode(newNode);
            size++;
            // 判断容量
            if (size > capacity) {
                // 删除最后一个节点
                DLinkedNode tempNode = dummyTail.prev;
                cache.remove(tempNode.key);
                removeNode(tempNode);
                size--;
            }
        } else {
            // 有缓存，更新 value 值，且移动到链表头部
            node.value = value;
            removeNode(node);
            addNode(node);
        }
        
    }

    // 移除节点方法
    public void removeNode(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 添加到链表首位
    public void addNode(DLinkedNode node){
        node.next = dummyHead.next;
        node.prev = dummyHead;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

抽离出两个公用方法，移除节点方法 removeNode() 、添加到链表首位方法 addNode()。

GoLang 解法

代码：

type LRUCache struct {
    // LRU缓存结构体包括容量、节点、虚拟头结点和虚拟尾结点
    size int // 当前的双向链表节点数
    capacity int // 容量
    cache map[int]*DLinkedNode
    dummyHead, dummyTail *DLinkedNode
}

// DLinkedNode 双向链表结构体
type DLinkedNode struct {
    // 包括key和value，以及前驱节点和后继结点
    key, value int
    pre, next *DLinkedNode
}

func initDLinkedNode(key, value int) *DLinkedNode {
    return &DLinkedNode{
        key: key,
        value: value,
    }
}

// 初始化
func Constructor(capacity int) LRUCache {
    l := LRUCache{
        size : 0,
        capacity: capacity,
        cache: make(map[int]*DLinkedNode, 0),
        dummyHead: initDLinkedNode(0, 0),
        dummyTail: initDLinkedNode(0, 0),
    }
    l.dummyHead.next = l.dummyTail
    l.dummyTail.pre = l.dummyHead
    return l
}


func (this *LRUCache) Get(key int) int {
    if _, ok := this.cache[key]; !ok {
        return -1
    }
    // 把查询到的节点放入双向链表首位
    node := this.cache[key]
    this.moveToHead(node)
    return node.value
}


func (this *LRUCache) Put(key int, value int)  {
    // 缓存中没有这个值
    if _, ok := this.cache[key]; !ok {
        node := initDLinkedNode(key, value)
        this.cache[key] = node
        // 添加节点到首位
        this.addToHead(node)
        // 判断size是否超过 capacity
        this.size++
        if this.size > this.capacity {
            // 移除最后一个节点（即虚拟尾结点的前一个节点）
            removed := this.removeTail()
            // 从Map中也一并移除,go的map删除还真是方便
            delete(this.cache, removed.key)
            this.size--
        }
        // 缓存中有这个值
    } else {
        // 移动原有节点到首位
        node := this.cache[key]
        node.value = value
        this.moveToHead(node)
    }
}

// moveToHead 移动原有节点到首位
func (this *LRUCache) moveToHead(node *DLinkedNode) {
    // 移除节点
    this.removeNode(node)
    // 添加节点
    this.addToHead(node)
}

// removeNode 移除节点
func (this *LRUCache) removeNode(node *DLinkedNode) {
    node.pre.next = node.next
    node.next.pre = node.pre
}

// addToHead 将节点添加到链表首位
func (this *LRUCache) addToHead(node *DLinkedNode) {
    node.pre = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.pre = node
    this.dummyHead.next = node
}

// removeTail 移除最后一个节点
func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.dummyTail.pre
    this.removeNode(node)
    return node
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

注：在 Go 语言中，删除 map 中的元素可以使用内置的 delete() 函数。这个函数接受两个参数：一个是 map 本身，另一个是要删除的键。如果指定的键在 map 中存在，它将被删除；如果不存在，则不执行任何操作。

scene := make(map[string]int)
scene["route"] = 66
scene["brazil"] = 4
scene["china"] = 960

delete(scene, "brazil") // 删除键为"brazil"的元素

for k, v := range scene {
fmt.Println(k, v) // 输出剩余的元素
}