如何用LinkedHashMap实现LRU缓存算法

阿里巴巴笔试考到了LRU，一激动忘了怎么回事了。。准备不充分啊。。

缓存这个东西就是为了提高运行速度的，由于缓存是在寸土寸金的内存里面，不是在硬盘里面，所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List：每次访问一个元素后把这个元素放在 List一端，这样一来最远使用的元素自然就被放到List的另一端。缓存满了t的时候就把那最远使用的元素remove掉。但更实用的是HashMap。因为List太慢，要删掉的数据总是位于List底层数组的第一个位置，删掉之后，后面的数据要向前补位。。所以复杂度是O(n)，那就用链表结构的LinkedHashMap呗~，LinkedHashMap默认的元素顺序是put的顺序，但是如果使用带参数的构造函数，那么LinkedHashMap会根据访问顺序来调整内部 顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端，这样一来每次顶端的元素就是remove的元素。

构造函数如下：

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；

initialCapacity 初始容量

loadFactor 加载因子，一般是 0.75f

accessOrder false 基于插入顺序 true 基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU 最近最少被使用的调度算法）

import java.util.*;class Test{public static void main(String[] args) throws Exception{Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);map.put(9,3);map.put(7,4);map.put(5,9);map.put(3,4);//现在遍历的话顺序肯定是9,7,5,3//下面访问了一下9,3这个键值对，输出顺序就变喽~map.get(9);for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){System.out.println(it.next().getKey());}}}