5
\$\begingroup\$

Problem Statement:

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise -1.
put(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.

Follow up:
Could you do both operations in O(1) time complexity?

I have a Java implementation that utilizes Hashtable and LinkedList. I am looking for feedbacks on how to write better, more elegant code. Any suggestions on >style, simplicity, comments, etc., are welcome.

My code:

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


//Not thread safe!
class LRUCache {
    private Map<Integer, Node> nodeMap;
    private DoubleLinkedList lruList;
    private int size;
    private int capacity;

    class Node {
        private int key;
        private int value;
        private Node prev = null;
        private Node next = null;

        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    class DoubleLinkedList{
        private Node head;
        private Node tail;

        DoubleLinkedList(){
            head = null;
            tail = null;
        }

        void remove(Node node){
            if(node.prev == null){
                assert head == node;
                head = node.next;
            }else{
                node.prev.next = node.next;
            }
            if(node.next == null){
                assert tail == node;
                tail = node.prev;
            }else{
                node.next.prev = node.prev;
            }
            node.prev = node.next = null;
        }

        void addToHead(Node node){
            if(head == null){
                assert tail == null;
                head = tail = node;
                return;
            }
            node.next = head;
            head.prev = node;
            head = node;
        }


        Node removeFromTail(){
            if(tail == null) throw new IllegalStateException("List is empty, cannot remove from it");
            Node removed = tail;
            Node new_tail = tail.prev;
            if(new_tail == null){
                head = tail = null; 
                removed.prev = removed.next = null;
                return removed;
            }
            new_tail.next = null;
            tail = new_tail;
            removed.prev = removed.next = null;
            return removed;

        }
    }

    public LRUCache(int capacity) {
        assert capacity > 0;
        this.nodeMap = new HashMap<Integer, Node>();
        this.lruList = new DoubleLinkedList();
        this.size = 0;
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = nodeMap.get(key);
        if(node == null) return -1;
        assert node.key == key;
        moveToMRU(node);
        return node.value;
    }

    public void put(int key, int value) {
        //first see if key already exists in cahce
        Node node = nodeMap.get(key);
        if(node != null){
            node.value = value;
            moveToMRU(node);
            return;
        }

        //have to insert
        if(size == capacity) evict();
        node = new Node(key, value);
        nodeMap.put(key, node);
        //newly inserted item is put to the MRU end
        lruList.addToHead(node);
        size += 1;
    }

    private void moveToMRU(Node node){
        lruList.remove(node);
        lruList.addToHead(node);
    }

    private void evict(){
        Node node = lruList.removeFromTail();
        assert node != null;
        nodeMap.remove(node.key);
        size -= 1;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
\$\endgroup\$
5
\$\begingroup\$

Combine declarations and initialization if you can

    private Map<Integer, Node> nodeMap;
    private DoubleLinkedList lruList;

Consider

    private final Map<Integer, Node> nodeMap = new HashMap<>();
    private final DoubleLinkedList lruList = new DoubleLinkedList();

This uses the <> notation to save having to list the types twice. This is more robust than the original, as you can make the change in only one place. You don't need parallel changes. Of course, the compiler would probably warn you anyway.

You don't have to make these final, but it can help make clear that you never discard them. This is a preference rather than a requirement. Some find it verbose. Some find that it clarifies your intent.

Reuse what you already have

        if(size == capacity) evict();

You don't need to maintain your own size variable.

        if (nodeMap.size() == capacity) {
            evict();
        }

Then you can get rid of the declaration and updates for the size variable. This will just use the value that nodeMap already maintains.

I also prefer to always use the block form of control structures rather than the statement form. More discussion.

Keep it simple

    public LRUCache(int capacity) {
        assert capacity > 0;
        this.nodeMap = new HashMap<Integer, Node>();
        this.lruList = new DoubleLinkedList();
        this.size = 0;
        this.capacity = capacity;
    }

With the previous changes, this could just be

    public LRUCache(int capacity) {
        assert capacity > 0;
        this.capacity = capacity;
    }

This mostly saves you in typing. You don't need this.nodeMap; and this.lruList;. It also means that you don't have to figure out that the other lines are not dependent on the value of capacity.

Alternatively, consider

    public LRUCache(int capacity) {
        assert capacity > 0;
        nodeMap = new HashMap<Integer, Node>(capacity);
        this.capacity = capacity;
    }

You don't need the this. with nodeMap. There is no ambiguity. There is only one nodeMap visible in this method. You can use it if you want to do so for clarity or readability. You just aren't required to use it for the method to compile.

Passing capacity to the HashMap constructor allows it to size appropriately. This way it won't resize as much as it grows. Since a resize can be an expensive operation, this may be more efficient.

Don't forget to remove the initialization with the declaration if you do this. Otherwise, the final will cause an error. Without the final, it will just be wasteful.

You do need the this. with capacity. There are two variables with that same name visible in this method.

LinkedHashMap

Also consider

    public LRUCache(int capacity) {
        assert capacity > 0;
        this.capacity = capacity;

        nodeMap = new LinkedHashMap<Integer, Integer>(capacity, .75, true) {

            @Override
            protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
                return size() > LRUCache.this.capacity;
            }

        };
    }

The anonymous class replaces the evict functionality. After it adds a new element, it tests if the capacity is overtaken. If so, it removes the oldest element.

The .75 is the default load factor and the true tells it to use access order for the ordering.

I haven't tested this, so I'm not sure what other changes you'd have to make to get this working.

The goal here is to simplify the methods, as the LinkedHashMap manages some of the complexity.

\$\endgroup\$
  • \$\begingroup\$ Should use (capacity*4+2)/3 as initial capacity for the linked hashmap to avoid resizing. \$\endgroup\$ – Nevay Aug 22 '17 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.