LRU缓存示例

Question

请检查以下LRU缓存实现。

谢谢你的宝贵意见

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    HashMap<Integer, Node> lruHashMap = new HashMap<>();

    private final int DEFAULT_CACHE_SIZE =5;

    int capacity = 0;

    class Node{
        int value;
        Node prev, next;
        public Node(int value, Node prev, Node next){
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
        public Node(int value){
            this.value = value;
            this.prev = null;  this.next = null;
        }
    }

    Node head;
    Node tail;

    public void addData(int value){

        if(head == null) {
            head = new Node(value);
            tail = head;
            capacity++;
            lruHashMap.put(value, head);
            return;
        }

        if( lruHashMap.containsValue(value)) {
            // Item already at the linkedList and map
            // Delete node first

            Node deleteNode = lruHashMap.get(value);
            deleteNode.next.prev = deleteNode.prev;
            deleteNode.prev.next = deleteNode.next;
            deleteNode = null;
        }

        Node newNode = new Node(value,null,head);
        // Add item to head
        head.prev = newNode;
        head = head.prev;

        lruHashMap.put(value,newNode);

        ++capacity;

        checkSize(capacity);


    }

    private void checkSize(int capacity) {
        if(capacity > DEFAULT_CACHE_SIZE) {
            // remove last element
            removeLast();
        }

    }


    private void removeLast() {

        int value = tail.value;

        tail = tail.prev;
        tail.next = null;
        --capacity;

        lruHashMap.remove(value);
    }

    private void getDataOfLRUCache(){

        for(Map.Entry<Integer,Node> entry: lruHashMap.entrySet()){
            System.out.print (entry.getKey() + " - " );
            System.out.println(entry.getValue() );
        }
    }


    public boolean isEmpty() {
        return capacity == 0;
    }

    public static void main(String args[]){

        LRUCache lruCache = new LRUCache();

        lruCache.addData(5);
        lruCache.addData(6);
        lruCache.addData(7);
        lruCache.addData(8);
        lruCache.addData(9);

        //   lruCache.getDataOfLRUCache();

        lruCache.addData(11);
        lruCache.addData(12);
        lruCache.getDataOfLRUCache();
    }

}

Answer 1

我有一些建议给你。

• 将static关键字添加到DEFAULT_CACHE_SIZE变量(全帽蛇壳 )。

使用映射的大小，而不是使用capacity变量

您可以使用java.util.HashMap#size。在我看来，这样做的可能性会更小(如果你忘了更新，等等)。

避免使用C-style数组声明

在main方法中，使用C-style变量声明了一个args数组声明。

先于

String args[]

后

String[] args

在我看来，这种风格使用较少，并可能造成混乱。

潜在问题

从不直接向外部类

公开数组/集合/映射

在本例中，lruHashMap映射公开给任何其他实例，我强烈建议您使用private关键字来隐藏实例。如果不这样做，任何其他类都可以直接编辑映射，您的类将失去对自己数据的控制。

总是比较相同类型的

对象

在方法LRUCache#addData中，当您检查lruHashMap是否包含该值时，您将java.lang.Integer与Node进行比较。您可能想要使用java.util.HashMap#containsKey来代替。

//[...]
if (lruHashMap.containsValue(value)) { // Bug, will always return false
//[...]

通过设置对象空，当来自集合时，它不会从集合中删除它。

在本例中，在LRUCache#addData方法中，您将对象null设置为删除它吗？这只会影响变量deleteNode的当前引用，而不会影响映射中的对象。

// Item already at the linkedList and map
// Delete node first

Node deleteNode = lruHashMap.get(value);
deleteNode.next.prev = deleteNode.prev;
deleteNode.prev.next = deleteNode.next;
deleteNode = null; // Set the `deleteNode` to null

重构代码

   public class LRUCache {
      private HashMap<Integer, Node> lruHashMap = new HashMap<>();

      private static final int DEFAULT_CACHE_SIZE = 5;
      private Node head;
      private Node tail;

      class Node {
         int value;
         Node prev, next;

         public Node(int value, Node prev, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
         }

         public Node(int value) {
            this.value = value;
            this.prev = null;
            this.next = null;
         }
      }

      public void addData(int value) {
         if (head == null) {
            head = new Node(value);
            tail = head;
            lruHashMap.put(value, head);
            return;
         }

         if (lruHashMap.containsKey(value)) {
            // Item already at the linkedList and map
            // Delete node first

            Node deleteNode = lruHashMap.get(value);
            deleteNode.next.prev = deleteNode.prev;
            deleteNode.prev.next = deleteNode.next;
            // lruHashMap.remove(value); uncomment if you want to remote the item from the map
         }

         Node newNode = new Node(value, null, head);
         // Add item to head
         head.prev = newNode;
         head = head.prev;

         lruHashMap.put(value, newNode);

         checkSize();
      }

      private void checkSize() {
         if (lruHashMap.size() > DEFAULT_CACHE_SIZE) {
            // remove last element
            removeLast();
         }
      }


      private void removeLast() {
         int value = tail.value;

         tail = tail.prev;
         tail.next = null;

         lruHashMap.remove(value);
      }

      private void getDataOfLRUCache() {

         for (Map.Entry<Integer, Node> entry : lruHashMap.entrySet()) {
            System.out.print(entry.getKey() + " - ");
            System.out.println(entry.getValue());
         }
      }


      public boolean isEmpty() {
         return lruHashMap.isEmpty();
      }

      public static void main(String[] args) {
         LRUCache lruCache = new LRUCache();

         lruCache.addData(5);
         lruCache.addData(6);
         lruCache.addData(7);
         lruCache.addData(8);
         lruCache.addData(9);

         //   lruCache.getDataOfLRUCache();

         lruCache.addData(11);
         lruCache.addData(12);
         lruCache.getDataOfLRUCache();
      }
   }
```