LeetCode - LRU Cache

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.

 

Solution:

其实就是LinkedHashMap。我们可以用HashMap和双向链表来实现。最新取得和插入的数据移动到链表尾部。当容量满时，移除头部节点，并将头节点更新为下一个节点。

 

查询：

• 根据键值查询hashmap，若命中，则返回节点，否则返回null。
• 从双向链表中删除命中的节点，将其重新插入到表尾。
• 所有操作的复杂度均为O(1)。

插入：

• 将新的节点关联到Hashmap
• 如果Cache满了，删除双向链表的头节点，同时删除Hashmap对应的记录
• 将新的节点插入到双向链表尾部

public class LRUCache {
    private int capacity;
    private Map<Integer, CacheEntry> map;
    private CacheEntry head, tail;
    
    public static class CacheEntry {
        int key, data;
        CacheEntry prev, next;
        CacheEntry(int key, int data) {
            this.key = key;
            this.data = data;
        }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<Integer, CacheEntry>(capacity);
    }
    
    public int get(int key) {
        CacheEntry e = map.get(key);
        if(e == null) return -1;
        linkNodeLast(e); //将e节点移动到链表尾部
        return e.data;
    }
    
    public void set(int key, int value) {
        CacheEntry e = map.get(key);
        if(e != null) {
            e.data = value;
        } else {
            e = new CacheEntry(key, value);
            map.put(key, e);
        }
        linkNodeLast(e); //将e节点移动到链表尾部
        
        if(map.size() > capacity) { //移除头节点
            CacheEntry oldHead = head;
            head = head.next;
            oldHead.next = null;
            head.prev = null;
            map.remove(oldHead.key);
        }
    }
    
    private void linkNodeLast(CacheEntry e) {
        if(e == tail) return; //如果要移动的节点就是尾节点，直接返回
        if(tail == null) { //tail为null的话，说明目前还没有插入数据
            head = e; //更新头节点
        } else {
            if(head == e) { //如果等于头节点，需要把头节点移动到尾部，并更新头节点
                head = head.next;
            }
            if(e.prev != null) { //如果e本身就是头节点的话，prev为null，所以要判断一下
                e.prev.next = e.next;
            }
            if(e.next != null) {
                e.next.prev = e.prev;
            }
            tail.next = e; //将e节点放到链表尾部
            e.prev = tail;
            e.next = null;
        }
        tail = e; //更新尾节点
    }
}

 

有个更简单的方法，head和tail不保存实际内容，仅仅代表头部和尾部，这样可以避免上个方法中移动头部和尾部节点判断null的问题。

public class LRUCache {
    private int capacity;
    private Node head, tail;
    private Map<Integer, Node> map = new HashMap<>();
    
    public static class Node {
        int key, value;
        Node prev, next;
        public Node(int k, int v) {
            key = k;
            value = v;
        }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null) return -1;
        linkNodeLast(node);
        return node.value;
    }
    
    public void set(int key, int value) {
        Node node = map.get(key);
        if(node == null) {
            node = new Node(key, value);
        } else {
            node.value = value;
        }
        map.put(key, node);
        linkNodeLast(node);
        if(map.size() > capacity) {
            Node item = head.next;
            head.next = item.next;
            item.next.prev = head;
            map.remove(item.key);
        }
    }
    
    private void linkNodeLast(Node node) {
        if(node.prev != null) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.prev = tail.prev;
        tail.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }
}