最近阿里巴巴电话面试被问到了如何使用固定容量的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()); } } }

技术
©2020 ioDraw All rights reserved
JS基础重点知识实验总结(全)error: (-215:Assertion failed)解决方案逆向工程核心原理笔记(一)——Hello World-1特征工程详解PHP中的die、exit、return特朗普的"VIP疗法":正接受一种尚未获批的药物治疗HashMap实现LRU(最近最少使用)缓存更新算法三分钟看懂神经网络机器翻译SK海力士全球首发DDR5内存:频率冲上5600MHz、容量可达256GB日经:索尼和铠侠正积极申请华为供货许可