为什么做网站越早越好,仿制别人的竞价网站做竞价犯法吗,海南响应式网页建设方案,做网站一般都用什么字体最近阿里巴巴电话面试被问到了如何使用固定容量的HashMap#xff0c;实现LRU算法。当时一脸懵逼#xff0c;平时用HashMap也就用来快速存取数据而已#xff0c;容量都是不限的。
想了半天#xff0c;想到对node节点进行扩展#xff0c;加入引用计数#xff0c;然后到达指…最近阿里巴巴电话面试被问到了如何使用固定容量的HashMap实现LRU算法。当时一脸懵逼平时用HashMap也就用来快速存取数据而已容量都是不限的。
想了半天想到对node节点进行扩展加入引用计数然后到达指定容量后删除引用计数最少的。 面试官质疑这样效率太低了能不能优化下。 想到删除时需要遍历所有元素代价为O(n)太大了。想到可以用最小堆来进行筛选。被问到建堆的节点值是什么这块没想好卡壳了。
面试完之后网上搜了下才发现Java官方已经替我们预留了LRU算法的框架在LinkedHashMap里。我们只需要扩展下即可代码示例如下
/*** Constructs an empty ttLinkedHashMap/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 - tttrue/tt for* access-order, ttfalse/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.EntryK,V eldest) {return false;}
使用accessOrder来标识是使用访问顺序还是插入顺序。默认为插入顺序。当accessOrder为访问顺序、容量固定时即为LRU 举例如下 class LRULinkedHashMapK,V extends LinkedHashMapK,V {/*** */private static final long serialVersionUID 1882839504956564761L;private int capacity;public LRULinkedHashMap(int capacity) {super(capacity,0.75f,true);this.capacity capacity;}Overridepublic boolean removeEldestEntry(Map.EntryK,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() {//容量固定accessOrdertrueMapInteger, Integer map new LinkedHashMapInteger, 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,5for(IteratorMap.EntryInteger, 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(IteratorMap.EntryInteger, Integer it map.entrySet().iterator(); it.hasNext();) {System.out.println(it.next().getValue());}}public static void testLRULinkedHashMap() {//容量固定accessOrdertrueMapInteger, Integer map new LRULinkedHashMapInteger, 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,5for(IteratorMap.EntryInteger, 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(IteratorMap.EntryInteger, Integer it map.entrySet().iterator(); it.hasNext();) {System.out.println(it.next().getValue());}}}
