HashMap实现LRU（最近最少使用）缓存更新算法

曾经终败给现在 2022-02-01 19:45 244阅读 0赞

最近阿里巴巴电话面试被问到了如何使用固定容量的HashMap，实现LRU算法。当时一脸懵逼，平时用HashMap也就用来快速存取数据而已，容量都是不限的。

想了半天，想到对node节点进行扩展，加入引用计数，然后到达指定容量后，删除引用计数最少的。  
面试官质疑这样效率太低了，能不能优化下。  
想到删除时，需要遍历所有元素，代价为O(n)，太大了。想到可以用最小堆来进行筛选。被问到建堆的节点值是什么，这块没想好，卡壳了。

面试完之后，网上搜了下，才发现Java官方已经替我们预留了LRU算法的框架，在LinkedHashMap里。我们只需要扩展下即可，代码示例如下：

/** * Constructs an empty <tt>LinkedHashMap</tt> instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - <tt>true</tt> for * access-order, <tt>false</tt> for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */
       public LinkedHashMap(int initialCapacity,
                            float loadFactor,
                            boolean accessOrder) { 
           super(initialCapacity, loadFactor);
           this.accessOrder = accessOrder;
       }
    
       //方法为protected ，摆明了是想被继承、重写
       protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
           return false;
       }

使用accessOrder来标识是使用访问顺序，还是插入顺序。默认为插入顺序。当accessOrder为访问顺序、容量固定时，即为LRU  
举例如下：

class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> { 
    	
    	/** * */
    	private static final long serialVersionUID = 1882839504956564761L;
    	
    	private int capacity;
    	
    	public LRULinkedHashMap(int capacity) { 
    		super(capacity,0.75f,true);
    		this.capacity = capacity;
    	}
    	
    	@Override
    	public boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
    		System.out.println("即将根据LRU算法，删除最近最少使用元素：key= "+eldest.getKey()+" value= "+eldest.getValue()+" .");
    		//此行代码是关键，一旦容量超出限制，即按照LRU进行删除
            return size()>capacity;
        } 
    }
    public class Test { 
    	
    	
    	
    	public static void main(String[] args) { 
    		
    		testLinkedHashMap();
    		testLRULinkedHashMap();
    		
    
    	}
    	
    	public static void testLinkedHashMap() { 
    		//容量固定，accessOrder=true
    		Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(5, 0.75f, true);
    		map.put(1, 1);
    		map.put(2, 2);
    		map.put(3, 3);
    		map.put(4, 4);
    		map.put(5, 5);
    		
    		//此时输出1,2,3,4,5
    		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) { 
    			System.out.println(it.next().getValue());
    		}
    		map.put(4, 4);
    		map.put(6, 6);
    		
    		//此时输出1,2,3,5,4,6（自动扩容）
    		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) { 
    			System.out.println(it.next().getValue());
    		}
    		
    	}
    	
    	public static void testLRULinkedHashMap() { 
    		//容量固定，accessOrder=true
    		Map<Integer, Integer> map = new LRULinkedHashMap<Integer, Integer>(5);
    		map.put(1, 1);
    		map.put(2, 2);
    		map.put(3, 3);
    		map.put(4, 4);
    		map.put(5, 5);
    		
    		//此时输出1,2,3,4,5
    		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) { 
    			System.out.println(it.next().getValue());
    		}
    		map.put(4, 4);
    		map.put(6, 6);
    		
    		//此时输出2,3,5,4,6（容量锁定，进行删除）
    		for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) { 
    			System.out.println(it.next().getValue());
    		}
    		
    	}
    	
    }