修复了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> {
     /**
      * 默认容量
      */
-    private int DEFAULT_CAPACITY = 1024;
+    private static final int DEFAULT_CAPACITY = 1024;
     /**
      * 缓存容量
      */
@@ -19,19 +19,21 @@ public class LRUCache<K, V> {
     /**
      * 高效访问的散列表
      */
-    private Map<K, Node<V>> map;
+    private Map<K, Node<K, V>> map;
 
-    private Node<V> head, tail;
+    private Node<K, V> head, tail;
 
     /**
      * 自定义双向链表中的节点
      */
-    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> {
     /**
      * 对于新添加的元素，应将新元素添加到链表的头部
      */
-    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> {
     /**
      * 对于被访问的元素，将该元素移动到头部
      */
-    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) { // 如果是首节点，无需移动
             return node;
@@ -127,15 +133,14 @@ public class LRUCache<K, V> {
     /**
      * 缓存满时，应删除（淘汰）最后一个节点
      */
-    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; // 移动 tail
         if (prev == null) { // 如果尾节点的前一个节点也为空，说明尾节点也是首节点
@@ -144,7 +149,7 @@ public class LRUCache<K, V> {
             prev.next = null;
         }
         size--;
-        return element;
+        return t;
     }
 }
 ```
