map 实现

设置缓存，Least Recently Used (LRU) cach，利用map实现，每次get/put之前先移除之前的设置，最近使用的元素在最后，超出容量时通过map.keys().next().value 删除

利用map的特性，map.keys() 返回的是一个迭代器，返回的顺序按照set 的顺序，因此可以通过 map.keys().next().value 获得最先被 set 的数据。

Runtime: 184 ms, faster than 92.78%
Runtime: 184 ms, faster than 92.78%

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cache = new Map()
    this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.cache.has(key)) {
        const value = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, value)
        return value
    }
    return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.cache.has(key)) {
        this.cache.delete(key)
        this.cache.set(key, value)
    } else {
        if(this.cache.size >= this.capacity) {
            this.cache.delete(this.cache.keys().next().value)
        } 
        this.cache.set(key, value)
    }
};

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

哈希表 + 双向链表

要让 put 和 get 方法的时间复杂度为 O(1)，需要查找快，插入快，删除快，有顺序之分。符合上面条件的数据结构：哈希表，查找快，数据无固定顺序；链表有顺序之分，插入删除快，查找慢。将二者进行结合。Map方法实现的便捷性在于map的插入是有顺序的。

为什么需要双向链表，因为对于删除操作，删除一个节点不仅需要该节点本身的指针，还需要操作前驱节点的指针，双向链表可以支持直接查找前驱节点，保证操作的时间复杂度为O(1)。

哈希表中已经存了key，为什么双向链表中还要存储键值对，当缓存容量满了的时候，不仅需要删除双向链表中的节点，还要把哈希表中映射到该节点的key同时删除，这个key 只能由链表中的节点得到。

Runtime: 228 ms, faster than 36.29%
Memory Usage: 52 MB, less than 37.76%

class Node {
    constructor(key, val) {
        this.key = key
        this.val = val
    }
}

class DoubleLinkedListNode {
    constructor() {
        this.head = new Node(0, 0)
        this.tail = new Node(0, 0)
        this.head.next = this.tail
        this.tail.prev = this.head
        this.size = 0
    }
    
    remove(node) { 
        node.next.prev = node.prev
        node.prev.next = node.next
        node.next = null
        node.prev = null
        this.size--
    }
    
    addHead(node) {
        node.next = this.head.next
        node.prev = this.head
        this.head.next.prev = node
        this.head.next = node
        this.size++
    }
    
    removeTail() {
        if(this.tail.prev === null) return null
        const tail = this.tail.prev
        this.remove(tail)
        return tail
    }
    getSize() {
        return this.size
    }
}

var LRUCache = function(capacity) {
    this.hashMap = {}
    this.capacity = capacity
    this.link = new DoubleLinkedListNode()
};

LRUCache.prototype.get = function(key) {
    if(!(key in this.hashMap)) return -1
    const node = this.hashMap[key]
    this.put(key, node.val)
    return node.val
};


LRUCache.prototype.put = function(key, value) {
    if(key in this.hashMap) {
        const node = this.hashMap[key]
        this.link.remove(node)
        node.val = value
        this.link.addHead(node)
    } else {
        const node = new Node(key, value)
        this.hashMap[key] = node
        if(this.link.getSize() >= this.capacity) {
            const tail = this.link.removeTail()
            delete this.hashMap[tail.key]
        }
        this.link.addHead(node)
    }
};