Laziest implementation: Java's LinkedHashMap takes care of everything


  • 71

    This is the laziest implementation using Java's LinkedHashMap. In the real interview, however, it is definitely not what interviewer expected.

        import java.util.LinkedHashMap;
        public class LRUCache {
            private LinkedHashMap<Integer, Integer> map;
            private final int CAPACITY;
            public LRUCache(int capacity) {
                CAPACITY = capacity;
                map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
                    protected boolean removeEldestEntry(Map.Entry eldest) {
                        return size() > CAPACITY;
                    }
                };
            }
            public int get(int key) {
                return map.getOrDefault(key, -1);
            }
            public void set(int key, int value) {
                map.put(key, value);
            }
        }
    

    Several points to mention:

    1. In the constructor, the third boolean parameter specifies the ordering mode. If we set it to true, it will be in access order. (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#LinkedHashMap-int-float-boolean-)
    2. By overriding removeEldestEntry in this way, we do not need to take care of it ourselves. It will automatically remove the least recent one when the size of map exceeds the specified capacity.(https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#removeEldestEntry-java.util.Map.Entry-)

    Below is a "normal" HashMap + doubly-linked list implementation:

    public class LRUCache {
        private class Node{
            int key, value;
            Node prev, next;
            Node(int k, int v){
                this.key = k;
                this.value = v;
            }
            Node(){
                this(0, 0);
            }
        }
        private int capacity, count;
        private Map<Integer, Node> map;
        private Node head, tail;
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.count = 0;
            map = new HashMap<>();
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
        }
        
        public int get(int key) {
            Node n = map.get(key);
            if(null==n){
                return -1;
            }
            update(n);
            return n.value;
        }
        
        public void set(int key, int value) {
            Node n = map.get(key);
            if(null==n){
                n = new Node(key, value);
                map.put(key, n);
                add(n);
                ++count;
            }
            else{
                n.value = value;
                update(n);
            }
            if(count>capacity){
                Node toDel = tail.prev;
                remove(toDel);
                map.remove(toDel.key);
                --count;
            }
        }
        
        private void update(Node node){
            remove(node);
            add(node);
        }
        private void add(Node node){
            Node after = head.next;
            head.next = node;
            node.prev = head;
            node.next = after;
            after.prev = node;
        }
        
        private void remove(Node node){
            Node before = node.prev, after = node.next;
            before.next = after;
            after.prev = before;
        }
    }

  • 22
    A

    Your solution shows you are a good API user.


  • 0
    C
    This post is deleted!

  • 0

    This is great. It's always better to use functions built-in than create our own.


  • 0
    L

    Setting load factor to 0.75f will make your code run faster.


  • 1

    Better to know this even this might not be expected in the interview. Thanks for sharing!


  • 0
    J

    said in Laziest implementation: Java's LinkedHashMap takes care of everything:

    public LRUCache(int capacity) {
    CAPACITY = capacity;
    map = new LinkedHashMap<Integer, Integer>(capacity, 1.0f, true){
    protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > CAPACITY;
    }
    };
    }

    Could you explain the LinkedHashMap initialization part please?

    map = new LinkedHashMap<Integer, Integer>(capacity, 1.0f, true){
                    protected boolean removeEldestEntry(Map.Entry eldest) {
                        return size() > CAPACITY;
                    }
                };
    

    Why return size() > CAPACITY in removeEldestEntry function?


  • 4

    @Jessica According to documentation:

    This method is invoked by put and putAll after inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache: it allows the map to reduce memory consumption by deleting stale entries.

    In other words, after put operation, LinkedHashMap will call this function, and if this function returns true, it will remove the eldest entry. Therefore, we need to make sure it returns true if and only if map.size() is greater than the CAPACITY specified.
    For more details you can refer to LinkedHashMap's documentation.


  • 2
    A

    Another lazy solution by simply extending LinkedHashMap.

    https://discuss.leetcode.com/topic/59230/easy-java-soln-by-extending-linkedhashmap-o-1


  • 4
    A

    Similar solution without using removeEldestEntry

    public class LRUCache {
        LinkedHashMap<Integer,Integer> cache=new LinkedHashMap<>();
        int cap=0;
        
        public LRUCache(int capacity) {
            cap=capacity;
        }
        public int get(int key) {
            if(cache.containsKey(key)) {
                int value=cache.get(key);
                cache.remove(key);
                cache.put(key,value);
                return value;
            }
            return -1;
        }
        public void set(int key, int value) {
            if(cache.containsKey(key)) {
              cache.remove(key);
              cache.put(key,value);
            }
            else if(cache.size() == cap) cache.remove(cache.entrySet().iterator().next().getKey());
           cache.put(key,value);
        }
    }
    

  • 0

    @sky-xu Brilliant of u on using java's build-in LinkedHashMap !!, Holy Hell (Hao li hai)!!


  • 0

    @sky-xu this is awesome, well done!!

    Extended it directly like @ananmaha however it seems to run faster with my previous HashMap + Doubly LinkedList implementation.

    public class LRUCache extends LinkedHashMap<Integer, Integer> {
        
        Predicate<Integer> removeEldestEntry;
        
        public LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.removeEldestEntry = (size) -> size > capacity;
        }
        
        public int get(int key) {
            Integer value = super.get(key);
            return (value == null) ? -1 : value;
        }
        
        public void set(int key, int value) {
            put(key, value);
        }
        
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return removeEldestEntry.test(size());
        }
    }
    

  • 0
    W

    @sky-xu
    Nice solution.
    But your implementation way of LinkedHashMap may not match the requirement:

    set(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.

    In other words, the size of the cache should be always <= capacity.
    Just making a small change in set() will be OK.


  • 0
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    W

    @abiaps I think your solution worths a new post.

    1. It does not use removeEldestEntry from the API.
    2. By leveraging the insertion-order property of LinkedHashMap, removing a key, value pair and putting it back maintains the least recently used property in O(1) time.
    3. Combining iterator.next().getKey() with remove allows you to remove the least recently used pair in O(1) time.

  • 1
    J

    The parameter of the creation of map object seems not properly.
    map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true)
    Setting capacity with 0.75 loadFactor will let your map stores only up to 0.75*capacity elements. Change it to the following statement may be better:
    map = new LinkedHashMap<Integer, Integer>((int)(capacity / 0.75 + 1), 0.75f, true)


  • 0

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.