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.

分析

为了使查找、插入和删除都有较高的性能，这题的关键是要使用一个双向链表和一个HashMap，因为：

  • HashMap保存每个节点的地址，可以基本保证在O(1)时间内查找节点

  • 双向链表能后在O(1)时间内添加和删除节点，单链表则不行
    具体实现细节：

  • 越靠近链表头部，表示节点上次访问距离现在时间最短，尾部的节点表示最近访问最少

  • 访问节点时，如果节点存在，把该节点交换到链表头部，同时更新hash表中该节点的地址
  • 插入节点时，如果cache的size达到了上限capacity，则删除尾部节点，同时要在hash表中删除对应的项；新节点插入链表头部
    LRU Cche
    Figure: LRU Cche

代码

Java中也有双向链表LinkedList, 但是 LinkedList 封装的太深，没有能在O(1)时间内删除中间某个元素的API(C++的list有个splice(), O(1), 所以本题C++可以放心使用splice())，于是我们只能自己实现一个双向链表。

本题有的人直接用 LinkedHashMap ，代码更短，但这是一种偷懒做法，面试官一定会让你自己重新实现。

  1. // LRU Cache
  2. // 时间复杂度O(logn)，空间复杂度O(n)
  3. public class LRUCache {
  4.     private int capacity;
  5.     private final HashMap<Integer, Node> map;
  6.     private Node head;
  7.     private Node end;
  9.     public LRUCache(int capacity) {
  10.         this.capacity = capacity;
  11.         map = new HashMap<>();
  12.     }
  14.     public int get(int key) {
  15.         if(map.containsKey(key)){
  16.             Node n = map.get(key);
  17.             remove(n);
  18.             setHead(n);
  19.             return n.value;
  20.         }
  22.         return -1;
  23.     }
  25.     public void set(int key, int value) {
  26.         if (map.containsKey(key)){
  27.             Node old = map.get(key);
  28.             old.value = value;
  29.             remove(old);
  30.             setHead(old);
  31.         } else {
  32.             Node created = new Node(key, value);
  33.             if (map.size() >= capacity){
  34.                 map.remove(end.key);
  35.                 remove(end);
  36.                 setHead(created);
  37.             } else {
  38.                 setHead(created);
  39.             }
  41.             map.put(key, created);
  42.         }
  43.     }
  45.     private void remove(Node n){
  46.         if (n.prev !=null) {
  47.             n.prev.next = n.next;
  48.         } else {
  49.             head = n.next;
  50.         }
  52.         if (n.next != null) {
  53.             n.next.prev = n.prev;
  54.         } else {
  55.             end = n.prev;
  56.         }
  58.     }
  60.     private void setHead(Node n){
  61.         n.next = head;
  62.         n.prev = null;
  64.         if (head!=null ) head.prev = n;
  66.         head = n;
  68.         if(end == null) end = head;
  69.     }
  71.     // doubly linked list
  72.     static class Node {
  73.         int key;
  74.         int value;
  75.         Node prev;
  76.         Node next;
  78.         public Node(int key, int value) {
  79.             this.key = key;
  80.             this.value = value;
  81.         }
  82.     }
  83. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/linked-list/lru-cache.html