LRU算法

最近最少使用算法（LRU）是大部分操作系统为最大化页面命中率而广泛采用的一种页面置换算法。该算法的思路是，发生缺页中断时，选择未使用时间最长的页面置换出去。从程序运行的原理来看，最近最少使用算法是比较接近理想的一种页面置换算法，这种算法既充分利用了内存中页面调用的历史信息，又正确反映了程序的局部问题。下面将采用双向链表+哈希表实现。

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

思路：

• 哈希表
• 双向链表

哈希表和双向链表结合可以使得存取的时间复杂度都为O(1)

哈希表查找快，但是数据⽆固定顺序；链表有顺序之分，插⼊删除快，但是查找慢。

code：

var LRUCache = function(capacity) {
    this.capacity=capacity;
    this.count=0;
    this.head=null;
    this.tail=null;
    this.map=new Map();
};

class ListNode {
    constructor(key,val) {
        this.key=key;
        this.val=val;
        this.next=null;
        this.prev=null;
    }
}

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map.has(key)) {
        let node=this.map.get(key);
        if(node===this.head) return this.head.val;
        else if(node===this.tail) {
            this.tail=this.tail.prev;
            this.head.prev=node;
            node.next=this.head;
            this.head=node;
            return this.head.val;
        }else {
            node.next.prev=node.prev;
            node.prev.next=node.next;
            this.head.prev=node;
            node.next=this.head;
            this.head=node;
            return this.head.val;
        }
    }
    return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)) {
        this.map.get(key).val=value;
        this.get(key);
    }else {
        let node=new ListNode(key,value);
        this.map.set(key,node);
        if(this.head) {
            node.next=this.head;
            this.head.prev=node;
        }
        this.head=node;
        if(!this.tail) this.tail=node;
        if(++this.count>this.capacity) {
            let key=this.tail.key;
            this.tail=this.tail.prev;
            this.map.delete(key);
            this.count--;
        }
    }
};

/** 
 * 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)
 */