Two code implementations of LruCache

Recently I read some interviews. LruCache, as a classic medium algorithm, is often asked to tear by hand in interviews. Interviewers often ask interviewees to optimize the algorithm to improve efficiency. Two designs are available.

Note: Most interviewers will not let candidates use Java’s internal implementation classes, so LinkedHashMap is not considered in this article.

1.LinkedList+HashMap

Ideas:

public class LruCache {		
    private int capacity;	
    private HashMap<Integer, Integer> map;	
    private LinkedList<Integer> list;		
    public LruCache(int capacity) {		
        this.capacity=capacity;		
        this.map=new HashMap<>();		
        this.list=new LinkedList<>();	
    }		
    public int get(int key) {		
        if(!map.containsKey(key))return -1;		
        list.remove((Integer)key);		
        list.addLast(key);		
        return map.get(key);	
    }		
    public void put(int key,int value) {		
        if(map.size()==capacity) {			
        map.remove(list.getFirst());            
        list.removeFirst();		
        }		
        if(!map.containsKey(key)){			
            map.put(key, value);			        
            list.addLast(key);		
        }else {			
            map.put(key, value);			
            list.remove((Integer)key);
            list.addLast(key);		
        }
    }

}
Copy the code

2.HashMap+ custom bidirectional node:

Ideas:

class LRUCache { int capacity; HashMap<Integer,LruNode> map; LruNode first; LruNode first; LruNode last; public LRUCache(int capacity) { this.capacity=capacity; map=new HashMap<>(); The first = new LruNode (1, 0); The last = new LruNode (1, 0); first.next=last; last.pre=first; } public int get(int key) { if(! map.containsKey(key))return -1; LruNode node=map.get(key); deleteNode(node); updateLast(node); map.put(key,node); return node.value; } public void put(int key,int value) { if(map.containsKey(key)){ LruNode node= map.get(key); deleteNode(node); updateLast(node); node.value=value; map.put(key,node); }else{ if(map.size()==capacity){ LruNode temp=first.next; first.next=temp.next; temp.next.pre=first; map.remove(temp.key,temp); LruNode node=new LruNode(key,value); updateLast(node); map.put(key,node); }else{ LruNode node=new LruNode(key,value); updateLast(node); map.put(key,node); } } } public void updateLast(LruNode node) { last.pre.next=node; node.pre=last.pre; node.next=last; last.pre=node; } public void deleteNode(LruNode node) { node.pre.next=node.next; node.next.pre=node.pre; } class LruNode{ int key; int value; LruNode pre; LruNode next; public LruNode(int key,int value){ this.value=value; this.key=key; }}}Copy the code

Execution results with inner classes fall somewhere in between:

No method has been found that is more efficient than the second one, and other ideas will continue to be added.