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.

Ref: http://www.cnblogs.com/feiling/p/3426967.html

[解题思路]

LRU是Least Recently Used 的缩写，翻译过来就是“最不常使用”，也就是说，LRU缓存把最不常使用的数据移除，让给最新读取的数据。大多数情况下，最常读取的，也是读取次数最多的，所以，利用LRU缓存，我们能够提高系统的performance. LRU cache是非常频繁出现的一道面试题，一般来讲，当我们问到这道题时，面试官往往想得到的答案是利用 doubly linked list + hashtable 实现 LRU Cache, 那么我们现在就来讲一讲如何利用doubly linked list + hashtable实现LRU Cache的。

这里为什么使用Doubly linkd list 而不使用 Linked list的原因是：

当访问一个节点后，我们需要将他从原来的list中删除，然后将它插入到头节点处，删除过程中需要将其前后节点连接起来，单链表做不到。

查询：

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

插入：

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

更新：

• 和查询相似

删除：

• 从双向链表和Hashmap中同时删除对应的记录。
  

  public class LRUCache {
      
      private int capacity;
      private Map<Integer, DoubleLinkNode> nodesMap;
      private int currentSize;
      private DoubleLinkNode first;
      private DoubleLinkNode last;
      
      public LRUCache(int capacity) {
          this.capacity = capacity;
          currentSize = 0;
          nodesMap = new HashMap<Integer, DoubleLinkNode>();
      }
      
      public int get(int key) {
          DoubleLinkNode node = nodesMap.get(key);
          if(node != null){
              moveToHead(node);
              return node.value;
          } else {
              return -1;
          }
      }
      
      public void set(int key, int value) {
          DoubleLinkNode node = nodesMap.get(key);
          if(node == null){
              if(currentSize >= capacity){
                  nodesMap.remove(last.key);
                  removeLast();
              } else {
                  currentSize ++;
              }
              node = new DoubleLinkNode();
          }
          
          if(currentSize == 1){
              first = node;
              last = node;
          }
          
          node.key = key;
          node.value = value;
          moveToHead(node);
          nodesMap.put(key, node);
      }
      
      private void moveToHead(DoubleLinkNode node){
          if(node == first)
              return;
          
          // delete current node from doubly linked list
          if(node.pre != null){
              node.pre.next = node.next;
          }
          if(node.next != null){
              node.next.pre = node.pre;
          }
          
          if(last == node){
              last = node.pre;
          }
          
          if(first != null){
              node.next = first;
              first.pre = node;
          }
          first = node;
          node.pre = null;
          
      }
      
      private void removeLast(){
          if(last != null){
              if(last.pre != null){
                  last.pre.next = null;
              } else {
                  first = null;
              }
              last = last.pre;
          }
      }
  }
  
  class DoubleLinkNode{
      DoubleLinkNode pre;
      DoubleLinkNode next;
      int key;
      int value;
  }

  

   

LRU Cache

原文：http://www.cnblogs.com/RazerLu/p/3555330.html