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 1:

利用了JAVA 自带的LinkedHashMap ，其实这相当于作弊了，面试官不太可能会过。但是我们仍然可以练习一下如何使用LinkedHashMap.

同学们可以参考一下它的官方文档：

1. OverRide removeEldestEntry 函数，在Size达到最大值最，删除最长时间未访问的节点。

protected boolean removeEldestEntry(Map.Entry eldest) {

return size() > capacity;

}

2. 在Get/ Set的时候，都更新节点，即删除之，再添加之，这样它会作为最新的节点加到双向链表中。

1 package Algorithms.hash; 2  3 import java.util.LinkedHashMap; 4 import java.util.Map; 5  6 public class LRUCache2 { 7     public static void main(String[] strs) { 8         LRUCache2 lrc2 = new LRUCache2(2); 9         lrc2.set(1,3);10         lrc2.set(2,2);11         lrc2.set(1,4);12         lrc2.set(4,2);13         14         System.out.println(lrc2.get(1));15     }16     17     LinkedHashMap
       
         map;18     int capacity;19     20     public LRUCache2(final int capacity) {21         // create a map.22         map = new LinkedHashMap
        
         (capacity) {23             /**24              * 25              */26             private static final long serialVersionUID = 1L;27 28             protected boolean removeEldestEntry(Map.Entry eldest) {29                 return size() > capacity;30             }31         };32         this.capacity = capacity;33     }34     35     public int get(int key) {36         Integer ret = map.get(key);37         if (ret == null) {38             return -1;39         } else {40             map.remove(key);41             map.put(key, ret);42         }43         44         return ret;45     }46     47     public void set(int key, int value) {48         map.remove(key);49         map.put(key, value);50     }51 }

View Code

SOLUTION 2:

使用 HashMap+ 双向链表实现：

1. 如果需要移除老的节点，我们从头节点移除。

2. 如果某个节点被访问（SET/GET），将其移除并挂在双向链表的结尾。

3. 链表满了后，我们删除头节点。

4. 最近访问的节点在链尾。最久被访问的节点在链头。

1 package Algorithms.hash; 2  3 import java.util.HashMap; 4  5 public class LRUCache { 6     private class DLink { 7         DLink pre; 8         DLink next; 9         int val;10         int key;11         DLink(int key, int val) {12             this.val = val;13             this.key = key;14             pre = null;15             next = null;16         }17     }18     19     HashMap
       
         map;20     21     DLink head;22     DLink tail;23     24     int capacity;25 26     public void removeFist() {27         removeNode(head.next);28     }29     30     public void removeNode(DLink node) {31         node.pre.next = node.next;32         node.next.pre = node.pre;33     }34     35     // add a node to the tail.36     public void addToTail(DLink node) {37         tail.pre.next = node;38         39         node.pre = tail.pre;40         node.next = tail;41         42         tail.pre = node;43     }44     45     public LRUCache(int capacity) {46         map = new HashMap
        
         ();47         48         // two dummy nodes. In that case, we can deal with them more conviencely.49         head = new DLink(-1, -1);50         tail = new DLink(-1, -1);51         head.next = tail;52         tail.pre = head;53         54         this.capacity = capacity;55     }56     57     public int get(int key) {58         if (map.get(key) == null) {59             return -1;60         }61         62         // update the node.63         DLink node = map.get(key);64         removeNode(node);65         addToTail(node);66         67         return node.val;68     }69     70     public void set(int key, int value) {71         DLink node = map.get(key);72         if (node == null) {73             // create a node and add the key-node pair into the map.74             node = new DLink(key, value);75             map.put(key, node);76         } else {77             // update the value of the node.78             node.val = value;79             removeNode(node);80         }81         82         addToTail(node);83         84         // if the LRU is full, just remove a node.85         if (map.size() > capacity) {86             map.remove(head.next.key);87             removeFist();88         }89     }90 }

View Code

请移步至主页君的GITHUB代码：

转载地址：http://ucmko.baihongyu.com/

你可能感兴趣的文章