修复了map无法删除元素的问题

hicf · hicf · commit e0335368b7ff · 2019-09-01T13:44:46.000+08:00
diff --git a/resource/markdown/algorithm/LRUCache.md b/resource/markdown/algorithm/LRUCache.md
@@ -7,7 +7,7 @@ public class LRUCache<K, V> {
     /**
      * &#40664;&#35748;&#23481;&#37327;
      */
-    private int DEFAULT_CAPACITY = 1024;
+    private static final int DEFAULT_CAPACITY = 1024;
     /**
      * &#32531;&#23384;&#23481;&#37327;
      */
@@ -19,19 +19,21 @@ public class LRUCache<K, V> {
     /**
      * &#39640;&#25928;&#35775;&#38382;&#30340;&#25955;&#21015;&#34920;
      */
-    private Map<K, Node<V>> map;
+    private Map<K, Node<K, V>> map;
 
-    private Node<V> head, tail;
+    private Node<K, V> head, tail;
 
     /**
      * &#33258;&#23450;&#20041;&#21452;&#21521;&#38142;&#34920;&#20013;&#30340;&#33410;&#28857;
      */
-    private static class Node<V> {
+    private static class Node<K, V> {
+        K key;
         V value;
-        Node<V> prev;
-        Node<V> next;
+        Node<K, V> prev;
+        Node<K, V> next;
 
-        Node(Node<V> prev, V value, Node<V> next) {
+        Node(Node<K, V> prev, K key, V value, Node<K, V> next) {
+            this.key = key;
             this.value = value;
             this.prev = prev;
             this.next = next;
@@ -46,14 +48,18 @@ public class LRUCache<K, V> {
     }
 
     public LRUCache(int capacity) {
+        if (capacity <= 0) {
+            throw new IllegalArgumentException("Capacity must be positive integer");
+        }
+
         this.capacity = capacity;
         this.map = new HashMap<>(capacity, 0.75F);
         this.head = null;
         this.tail = null;
     }
 
     public V get(K key) {
-        Node<V> node = this.map.get(key);
+        Node<K, V> node = this.map.get(key);
         if (node != null) {
             this.moveToHead(node);
             return node.value;
@@ -63,19 +69,19 @@ public class LRUCache<K, V> {
     }
 
     public V put(K key, V value) {
-        Node<V> node = this.map.get(key);
+        Node<K, V> node = this.map.get(key);
         if (node != null) {
             node.value = value;
             moveToHead(node);
             return value;
         }
 
         if (size == capacity) {
-            removeLast();
-            map.remove(key);
+            node = removeLast();
+            map.remove(node.key);
         }
 
-        node = addFirst(value);
+        node = addFirst(key, value);
         map.put(key, node);
 
         return value;
@@ -84,9 +90,9 @@ public class LRUCache<K, V> {
     /**
      * &#23545;&#20110;&#26032;&#28155;&#21152;&#30340;&#20803;&#32032;&#65292;&#24212;&#23558;&#26032;&#20803;&#32032;&#28155;&#21152;&#21040;&#38142;&#34920;&#30340;&#22836;&#37096;
      */
-    private Node<V> addFirst(V e) {
-        final Node<V> h = head;
-        final Node<V> newNode = new Node<>(null, e, h);
+    private Node<K, V> addFirst(K key, V value) {
+        final Node<K, V> h = head;
+        final Node<K, V> newNode = new Node<>(null, key, value, h);
         head = newNode;
         if (h == null) {
             tail = newNode;
@@ -101,9 +107,9 @@ public class LRUCache<K, V> {
     /**
      * &#23545;&#20110;&#34987;&#35775;&#38382;&#30340;&#20803;&#32032;&#65292;&#23558;&#35813;&#20803;&#32032;&#31227;&#21160;&#21040;&#22836;&#37096;
      */
-    private Node moveToHead(Node<V> node) {
-        final Node<V> prev = node.prev;
-        final Node<V> next = node.next;
+    private Node<K, V> moveToHead(Node<K, V> node) {
+        final Node<K, V> prev = node.prev;
+        final Node<K, V> next = node.next;
 
         if (prev == null) { // &#22914;&#26524;&#26159;&#39318;&#33410;&#28857;&#65292;&#26080;&#38656;&#31227;&#21160;
             return node;
@@ -127,15 +133,14 @@ public class LRUCache<K, V> {
     /**
      * &#32531;&#23384;&#28385;&#26102;&#65292;&#24212;&#21024;&#38500;&#65288;&#28120;&#27760;&#65289;&#26368;&#21518;&#19968;&#20010;&#33410;&#28857;
      */
-    private V removeLast() {
-        final Node<V> t = tail;
+    private Node<K, V> removeLast() {
+        final Node<K, V> t = tail;
         if (t == null) {
             return null;
         }
 
-        V element = t.value;
         t.value = null; // help GC
-        Node<V> prev = t.prev;
+        Node<K, V> prev = t.prev;
         t.prev = null; // help GC
         tail = prev; // &#31227;&#21160; tail
         if (prev == null) { // &#22914;&#26524;&#23614;&#33410;&#28857;&#30340;&#21069;&#19968;&#20010;&#33410;&#28857;&#20063;&#20026;&#31354;&#65292;&#35828;&#26126;&#23614;&#33410;&#28857;&#20063;&#26159;&#39318;&#33410;&#28857;
@@ -144,7 +149,7 @@ public class LRUCache<K, V> {
             prev.next = null;
         }
         size--;
-        return element;
+        return t;
     }
 }
 ```
