[Java] Use LinkedHashMap may get a better solution


  • 1
    N

    I tried to use LinkedHashMap, maybe it's simpler, here is my code.

    public class LRUCache {
        int capacity = 0;
        java.util.LinkedHashMap<Integer, Integer> map = new java.util.LinkedHashMap<Integer, Integer>();
        
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new java.util.LinkedHashMap<Integer, Integer>(capacity);
        }
        
        public int get(int key) {
            if (map.containsKey(key)) {
                Integer val = map.get(key);
                map.remove(key);
                map.put(key, val);
                return val;
            } else {
                return -1;
            }
        }
        
        public void set(int key, int value) {
            if (map.containsKey(key) || map.size() < capacity) {
                map.remove(key);
                map.put(key, value);
                return;
            }
            
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            if (iterator.hasNext()) {
                Integer toRmKey = iterator.next().getKey();
                map.remove(toRmKey);
            }
            map.put(key, value);
        }   
    }

  • 6
    K

    Using the LinkedHashMap you can do it in even more cleaner and simpler way. But I think it is a hack.

    public class LRUCache {
    
    private static int cap;
    Map <Integer, Integer> lmap;
    public LRUCache(int capacity) {
        this.cap= capacity;
        lmap = new LinkedHashMap(capacity,0.75f,true){
            protected boolean removeEldestEntry(Map.Entry eldest){
                return size() > cap;
            }
        };
        
    }
    
    public int get(int key) {
        if(lmap.containsKey(key)){
            return lmap.get(key);
        }
        return -1;
    }
    
    public void set(int key, int value) {
        lmap.put(key,value);
    }
    

    }


  • 0
    D

    The accessMode of LinkedHashMap actually has resolved the key issue of LRU. The idea of the question is to test how you deal with such issue, not how you use other people's implementation.


  • 0
    N

    yeah, but the key point of LinkedHashMap is another way to solve the question, which reduce the arraycopy cost. Use it directly may be a hack, but knowing how it works is good for us.


  • 0
    N

    nice, agree with you


  • 0
    W

    Could you tell me why we need to call remove method ? I don't understand the two remove() calls. Thank you


  • 0
    N

    Because we need maintain the latest used in the end of the list; when the map is full, we should remove the least used item. You can also check the java class LinkedHashMap for more information.


Log in to reply
 

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