GuilinDev

Lc0146

05 August 2008

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.

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

题意和分析

要求实现 Least Recently Used (LRU)的缓存器，这里有公众号“程序员小灰”的对LRU的讲解，非常诙谐，一看就懂，主要是对哈希链表的实现，这里就不多解释了，实现两个方法，get和put， 其中get函数是通过输入key来获得value，如果成功获得，该键值对(key, value)就升至缓存器中最常用的位置（顶部），如果key不存在，则返回-1；put函数是插入一对新的对(key, value)，如果原缓存器中有该key，则需要先删除掉原有的，将新的插入到缓存器的顶部。如果不存在，则直接插入到顶部。若加入新的值后缓存器超过了容量，则需要删掉一个最不常用的值，也就是底部的值。要求二者的操作均为O(1)。

具体实现时创建一个hashmap和一个双向链表，保存关键值key和缓存器各项的迭代器之间映射，从而可以以O(1)的时间内找到目标项；另外四个私有变量，capacity是缓存器的容量大小， count是标定目前缓存中键值对个数，和哈希链表的头尾指针。然后再来看get和put如何实现，get相对简单些，我们在hash中查找给定的key，如果存在则将此项移到顶部，并返回value，若不存在返回-1。对于put，查找给定的key，如果存在就删掉原有项，并在顶部插入新来项，然后判断是否溢出，若溢出则删掉底部项(最不常用项)。

代码

class LRUCache {
        
    /**
     * 1. 创建一个内部类Node，封装需要的key-value键值对的对象
     */
    class Node {
        private int key, value;
        private Node prev, next;
        public Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
}

    /**
     * 2. 依靠创建的 Node 类型构建一个双链表内部类，实现几个需要的 API
     *    这些操作的时间复杂度均为 O(1)，
     *    其中，如同单链表，head和tail分别是链表的头节点和尾节点，不在数据内
     */
    class DoubleList {
        private Node head, tail;
        private int size;

        public DoubleList() {
            // 创建双链表的头尾，头尾不计入双链表的size中
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail; // 双链表的head指向tail
            tail.prev = head; // 双链表的tail指向head
            size = 0;
        }

        // 在链表头部添加节点 x，时间 O(1)
        public void addFirst(Node x) {
            // 在head和第一个node之间插入
            x.next = head.next;
            x.prev = head;
            head.next.prev = x; // 插入前的第一个node
            head.next = x; // 插入前的第一个node
            size++;
        }

        // 删除链表中的 x 节点（x 一定存在），由于是双链表且给的是目标 Node 节点，时间 O(1)
        public void remove(Node x){
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }

        // 删除链表中最后一个节点，并返回该节点，时间 O(1)
        public Node removeLast(){
            if (tail.prev == head) { // 双链表目前木有元素
                return null;
            }
            Node last = tail.prev;
            remove(last); // 直接实现的调用remove方法移除最后一个元素
            return last;
        }

        // 返回链表长度，时间 O(1)
        public int size(){
            return size;
        }
    }

    /**
     * 3. 创建一个上面创建好的双链表，结合一个新建的HashMap，实现LinkedHashMap的功能
     */
    // k-v: key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        // 如果key不存在，直接返回-1
        if (!map.containsKey(key)) {
            return -1;
        }
        // 否则用put将数据(key, value)提到开头，并返回相应的值
        int value = map.get(key).value;
        put(key, value);
        return value;
    }

    public synchronized void put(int key, int value) {
        // 先把新节点做出来
        Node x = new Node(key, value);

        // 如果key已存在，把旧的数据删除，把新的数据x插入到开头
        if (map.containsKey(key)) { 
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新map中的数据
            map.put(key, x);
        } else {
            // key不存在，先检查是否有空间
            if (cap == cache.size()) {
                // 删除链表最后一个数据，腾位置
                Node last = cache.removeLast(); //设计的removeLast()返回节点
                map.remove(last.key);
            }
            // 把新节点添加到头部，map 中新建 key 对新节点 x 的映射
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}

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

如果用Java内置的LinkedHashMap，这个是对HashMap + Double LinkedList进行了封装，不需要自己实现数据结构了，就会简单很多，而且官方API经过各种优化比自己实现的数据结构的速度一般要快，但有时候面试不让用LinkedHashMap。

class LRUCache {
    
    private volatile Map<Integer, Integer> map;
    private int cacheSize;

    public LRUCache(int initSize) {
        this.cacheSize = initSize;
        // 重写removeEldestEntry()方法，只要没有位置就移除最后一个entry
        this.map = new LinkedHashMap<Integer, Integer>(initSize, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > LRUCache.this.cacheSize;
            }
        };
    }
    
    public int get(int inKey) {
        if (!map.containsKey(inKey)) {
            return -1;
        }
        int val = map.get(inKey);
        // 同样利用put方法将数据提前
        put(inKey, val);
        return val;
    }
    
    public synchronized void put(int key, int value) {
        // 直接利用Java中LinkedHashMap实现的put方法
        map.put(key, value);
    }
}

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

This site is open source. Improve this page.