经典哈希表-LRU 缓存机制

哈希表 + 双向链表

146. LRU 缓存机制

• 新访问， 保存顶部
• 若存在， 先移除
• 若容量不足， 先移除底部

简单实现

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.hashTable = new Map();
    this.arr = [];
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.hashTable.has(key)) return -1;
    // hash不变， cache中移动key至顶部
    let index = this.arr.indexOf(key);
    this.arr.splice(index, 1);
    this.arr.unshift(key)
    return this.hashTable.get(key)
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    // 已存在, hash中set进行重写
    if (this.hashTable.has(key)) {
        let index = this.arr.indexOf(key);
        this.arr.splice(index, 1)
        this.arr.unshift(key)
        this.hashTable.set(key, value)
        return;
    }
    // 容量不足
    if (this.arr.length >= this.capacity) {
        let tail = this.arr.pop()
        this.hashTable.delete(tail)
    }
    this.arr.unshift(key)
    this.hashTable.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)
 */

测试用例

["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
["LRUCache","put","put","get","put","put","get"]
[[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]

哈希表+双链表实现

function DLinkedNode(key=null, value=null) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
}
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.hashTable = new Map();
    // 伪头部和伪尾部节点
    this.head = new DLinkedNode();
    this.tail = new DLinkedNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (!this.hashTable.has(key)) return -1;
    // hash不变， cache中移动key至顶部
    let node = this.hashTable.get(key);
    this.removeNode(node);
    this.addNode(node)
    return node.value;
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    // 已存在, hash中set进行重写
    if (this.hashTable.has(key)) {
        let node = this.hashTable.get(key);
        node.value = value;
        this.get(key)
        return;
    }
    // 容量不足
    if (this.size >= this.capacity) {
        let tail = this.removeTail();
        this.hashTable.delete(tail.key)
        this.size -= 1;
    }
    let node = new DLinkedNode(key, value)
    this.addNode(node)
    this.hashTable.set(key, node)
    this.size += 1;
};
LRUCache.prototype.removeNode = function (node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}
/**
 * 默认添加在顶部
 */
LRUCache.prototype.addNode = function (node) {
    node.prev = this.head;
    node.next = this.head.next;
    // head
    this.head.next.prev = node;
    this.head.next = node;
}
LRUCache.prototype.removeTail = function () {
    let node = this.tail.prev;
    this.removeNode(node)
    return node;
}
/**
 * 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)
 */