1
\$\begingroup\$
import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private static class DoublyLinkedHashMap {
        private static final class Node {
            private final int key;
            private final int value;
            private Node next;
            private Node previous;

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

            @Override
            public String toString() {
                return "Node[" +
                        "key=" + key + ", " +
                        "value=" + value + ']';
            }
        }

        private final int capacity;
        private final Map<Integer, Node> keyToNodeMap;
        private final Node sentinel;

        public DoublyLinkedHashMap(int capacity) {
            this.capacity = capacity;
            keyToNodeMap = new HashMap<>();
            sentinel = new Node(-1, -1);
            // Invarinats: sentinel.next has the head of the DLL and sentinel.previous has the tail of the DLL
            // Invariants: head is the least recently used key and tail is the most recently used key for the DLL
            sentinel.next = sentinel;
            sentinel.previous = sentinel;
        }

        public void put(int key, int val) {
            Node toPlace = new Node(key, val);
            Node toRemove = keyToNodeMap.remove(key);
            removeNodeFromBetweenItsSiblings(toRemove); // to make it the tail
            keyToNodeMap.put(key, toPlace);
            makeNodeTheTail(toPlace); // make it the tail

            // if size exceeded, remove lru - i.e. head of linked list
            if (keyToNodeMap.size() > capacity) {
                removeLRU();
            }
        }

        public int get(int key) {
            if (!keyToNodeMap.containsKey(key)) return -1;
            Node toGet = keyToNodeMap.get(key);
            removeNodeFromBetweenItsSiblings(toGet); // to make it the tail
            makeNodeTheTail(toGet); // update the tail as key's node was most recently accessed
            return toGet.value;
        }

        private void removeNodeFromBetweenItsSiblings(Node toRemove) {
            if (toRemove == null) return;
            toRemove.previous.next = toRemove.next;
            toRemove.next.previous = toRemove.previous;
        }

        private void makeNodeTheTail(Node toPlace) {
            Node previousTail = sentinel.previous;
            previousTail.next = toPlace;
            sentinel.previous = toPlace;
            toPlace.previous = previousTail;
            toPlace.next = sentinel;
        }

        private void removeLRU() {
            // head is the least recently used by invariant, so remove it.
            Node previousHead = sentinel.next;
            sentinel.next = previousHead.next;
            previousHead.next.previous = sentinel;
            keyToNodeMap.remove(previousHead.key);
        }
    }

    private final DoublyLinkedHashMap linkedHashMap;

    public LRUCache(int capacity) {
        linkedHashMap = new DoublyLinkedHashMap(capacity);
    }

    public int get(int key) {
        return linkedHashMap.get(key);
    }

    public void put(int key, int value) {
        linkedHashMap.put(key, value);
    }


    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // cache is {1=1}
        lRUCache.put(2, 2); // cache is {1=1, 2=2}
        lRUCache.get(1);    // return 1
        lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // returns -1 (not found)
        lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
        System.out.printf("%d, %d, %d\n", lRUCache.get(1), lRUCache.get(3), lRUCache.get(4));  // -1, 3,4
    }
}

I would appreciate a review of my solution to the LRU Cache problem. All the operations are O(1) as asked in the question (but for some reason it's faster than only 68%). I used the sentinel node to avoid null checks.

\$\endgroup\$
1
  • \$\begingroup\$ For ideas on deriving doubly linkable objects, have a look at Simula's CLASS LINKAGE. \$\endgroup\$
    – greybeard
    Aug 7 at 17:19

2 Answers 2

2
\$\begingroup\$

Don't write, never publish/commit undocumented/uncommented code.
For Java, there's javadoc.

(A pity
LRUCache is specified to be a class - I'd rather have an interface there.
• java.util.LinkedList doesn't allow plucking nodes from it - no access to nodes at all, at that.)

Given that you use java.util.HashMap<K, V> instead of rolling your own:
Why not just use LinkedHashMap<K, V>, specifying access-order?
(Instantiate collections and maps specifying a capacity where supported.)

DoublyLinkedHashMap.get() does two lookups where the key is mapped:
Just get() the node and return -1 if null.

While unconditionally plucking the node from the list in put() looks arguable,
remove()ing it from keyToNode doesn't seem called for:
get() the node, if != null, just update value.

removeNodeFromBetweenItsSiblings() could be an instance method(pluck()) of Node
(set next&previous to this in constructor.)
(pluck() could be called from precede()&follow(), reducing its use to remove from list.)


I see two parts in LeetCode's problem:

  1. Design a data structure
    I think you've done fine sketching a general LRU cache except for omitting genericity.
  2. Implement the LRUCache class
    The key space is exceptionally small, just 0…10000 for a max. capacity of 3000.
    This invites to just use arrays:
    You don't need to store keys
    You can get mean re space for linkage
    (to get real mean, encode linkage&value in one integer - even (10⁵+2)*(2*(10⁴+1)+1) < 2³¹)
\$\endgroup\$
2
\$\begingroup\$

If you are looking for micro-optimizations to get the time down, consider

            keyToNodeMap = new HashMap<>();

could be

            keyToNodeMap = new HashMap<>(2 * capacity);

If you do it that way, you both make it unlikely that the HashMap will resize and decrease the average chain length in case of a hash collision. Handling collisions is slow and resizes are slow. So this should make it faster.

In general, if you know the capacity, it is a good idea to pass it to these kinds of constructors. They take capacity arguments for exactly that reason. You will often let them resize as needed, but you don't have to do so.

The tradeoff of course is that this version is likely to use more space. However, since resizes tend to double the space, it may not. If the default capacity is 15, doubling would give 30, 60, 120, 240, 480, 960, 1920, 3840, 7680. And remember we double at 75% of capacity by default. So the capacity would double when the size reached 12, 23, 45, 90, 180, 360, 720, 1440, 2880. So if the known capacity of the LRU is 3000, when it reaches 2880, it will double the capacity of the HashMap to 7680. That's larger than the 6000. Even a more realistic default of 16, would get us to 4096.

            keyToNodeMap = new HashMap<>(3 + 3 * capacity / 4);

This would be tighter space but would still probably prevent resizes. It would allow more collisions though. And obviously it is a more complex calculation.

            if (!keyToNodeMap.containsKey(key)) return -1;
            Node toGet = keyToNodeMap.get(key);

Pretty much the first thing that a HashMap.get has to do is its own containsKey. So by doing containsKey immediately before the get, you make it do two containsKey calls. Now, it is potentially possible for the compiler to realize this and skip one of them. But if you want to be sure to skip one of them, you can change the code to

            Node toGet = keyToNodeMap.get(key);
            if (toGet == null) {
                return -1;
            }

This skips the first one. If the map allowed null values, it would change the logic slightly. If it does not allow null values, then this has exactly the same result. Your get method does not allow a null return and your put does not allow a null value, so presumably this would work as well.

If this is for an interview, as you suggested in the comments, it's worth noting that I personally would mark you down for using the statement form of control structures. I would prefer to always see the block form used. Other interviewers may react differently, including some interviewers who would prefer the statement form. The block form is probably safer, as interviewers who prefer the statement form would tend to understand that many others don't. But if you use the statement form, you are more likely to end up at a job that uses it. You'll have to work out your own balance.

As previously noted, a more likely optimization given the small range of potential keys would be an array. While both an array and a HashMap have \$\mathcal{O}(1)\$ time accesses, in practice, the pointer math to dereference an array is faster than the hashing needed to dereference a HashMap. Also, with the array, you can prefill it with -1 so that you don't have to handle the missing case at all.

Using an array this way also makes a mockery of the capacity measure. But that isn't necessarily a blocker. It can still act like the capacity matters even if it doesn't need to do so. Since a HashMap has to store both key and value, it's even possible that the array version will actually be smaller. I.e. a 10,000 element array may turn out to be smaller than a 3000 element HashMap. Particularly if your 3000 element HashMap has a capacity of 7680.

A HashMap also has to handle collisions. Two common solutions are to make the buckets lists or to add a next pointer to the bucket. Lists have some additional overhead, often a 10 element default capacity. Or the next pointer is a third piece of data.

Again, this is a result of the small key space. It is practical to cache 10,000 values. If we expand the key space to even sixteen bits, that would give a less practical 65,536 elements. And thirty-two bits is much less practical. Even a three byte ASCII string would be a questionable 16,777,216 elements as an array. A two character Unicode string would be as impractical as a thirty-two bit integer.

If we decreased the key space to always match the capacity, then the array would be clearly better. Smaller size and faster. This key range may have been chosen to make the question interesting. People can sacrifice space to gain speed or vice versa.

\$\endgroup\$

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.