146-最近使用缓存

Description

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.

---

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

---

问题描述

实现一个数据结构支持最近使用缓存。需要支持put和get操作

• get(key)-获取key对应的值(总是整数)， 如果key不存在， 返回-1
• put(key, val)-若key不存在， 插入值， 否则更新值。如果元素个数达到容量， 那么需要先移除最远使用的元素

注意， 两种操作都需要在O(1)的时间复杂度

---

问题分析

维护两个数据结构

1. value, 存储(key, val)的map
2. buckets, 存储(key, bucket)的map， bucket为双向链表

维护两个指针, mr和ml。mr指向最近使用的bucket, ml指向最远使用的bucket

有了这些数据结构就好办了， 针对get()和put()进行更新即可

---

解法1

class LRUCache {
    //存放值
    private Map<Integer, Integer> value;
    //存放双向链表
    private Map<Integer, Bucket> buckets;
    //最近使用指针
    Bucket mr;
    //最远使用指针
    Bucket ml;
    int cap;
    public LRUCache(int capacity) {
        value = new HashMap();
        buckets = new HashMap();
        cap = capacity;
    }

    public int get(int key) {
        if(!value.containsKey(key)) return -1;
        //更新双向链表
        Bucket b = buckets.get(key);
        //ml前移
        if(b == ml && ml != mr){
            ml = ml.prev;
        }
        //更新双向链表及mr
        if(b != mr){
            b.prev.next = b.next;
            if(b.next != null)  b.next.prev = b.prev;
            b.next = mr;
            mr.prev = b;
            mr = b;
        }

        return value.get(key);
    }

    public void put(int key, int value) {
        //若不包含key，那么新建bucket， 更新mr
        //若ml为空， 更新ml
        //如果元素个数大于容量， 删除ml指向的元素， 更新ml
        if(!this.value.containsKey(key)){
            this.value.put(key, value);
            Bucket b = new Bucket(key);
            if(mr == null){
                mr = b;
            }else{
                b.next = mr;
                mr.prev = b;
                mr = b;
            }
            if(ml == null){
                ml = b;
            }
            buckets.put(key, b);
            if(this.value.size() > cap){
                this.value.remove(ml.key);
                buckets.remove(ml.key);
                ml = ml.prev;
            }
        }else{
            this.value.put(key, value);
            //这里的操作直接使用get就可以了
            get(key);
        }
    }
    //双向链表类
    private class Bucket{
        Bucket prev;
        Bucket next;
        //注意这里， 存储的是键
        int key;
        public Bucket(int val){
            key = val;
        }
    }
}