使用LinkedHashMap构建LRU的Cache
?
顾名思义LinkedHashMap是比HashMap多了一个链表的结构。与HashMap相比LinkedHashMap维护的是一个具有双重链表的HashMap，LinkedHashMap支持2中排序一种是插入排序，一种是使用排序，最近使用的会移至尾部例如 M1 M2 M3 M4，使用M3后为 M1 M2 M4 M3了，LinkedHashMap输出时其元素是有顺序的，而HashMap输出时是随机的，如果Map映射比较复杂而又要求高效率的话，最好使用LinkedHashMap，但是多线程访问的话可能会造成不同步，所以要用Collections.synchronizedMap来包装一下，从而实现同步。其实现一般为：?
??? Map<String String> map = Collections.synchronizedMap(new LinkedHashMap(<String String));
HashMap,LinkedHashMap,TreeMap都属于Map
Map?主要用于存储键(key)值(value)对，根据键得到值，因此键不允许键重复,但允许值重复。
HashMap?是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力。
LinkedHashMap?LinkedHashMap也是一个HashMap,但是内部维持了一个双向链表,可以保持顺序
TreeMap?不仅可以保持顺序，而且可以用于排序
HashMap例子：
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("a3", "aa");
map.put("a2", "bb");
map.put("b1", "cc");
for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
}LinkedHashMap例子：
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("a3", "aa");
map.put("a2", "bb");
map.put("b1", "cc");
for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
}TreeMap例子：
public static void main(String[] args) {
Map<String, String> map = new TreeMap<String, String>(new Comparator<Object>(){
Collator collator = Collator.getInstance();
public int compare(Object o1, Object o2) {
CollationKey key1 = collator.getCollationKey(o1.toString());
CollationKey key2 = collator.getCollationKey(o2.toString());
return key1.compareTo(key2);
//return collator.compare(o1, o2);
}});
map.put("a3", "aa");
map.put("a2", "bb");
map.put("b1", "cc");
for (Iterator iterator = map.values().iterator(); iterator.hasNext();) {
String name = (String) iterator.next();
System.out.println(name);
}
}LinkedHashMap的特性:Linked内部含有一个private transient Entry header;来记录元素插入的顺序或者是元素被访问的顺序。利用这个线性结构的对象，可以帮助记录entry加入的前后顺序或者记录entry被访问的 频率(最少被访问的entry靠前，最近访问的entry靠后)。大致的过程如下:new LinkedHashMap(10, 0.75, true);其中前面两个参数就是HashMap构造函数需要的参数，后面的true表明LinkedHashMap按照访问的次序来排序。按照访问的次序来排序的含义:当调用LinkedHashMap的get(key)或者put(key, value)时，碰巧key在map中被包含，那么LinkedHashMap会将key对象的entry放在线性结构的最后。按照插入顺序来排序的含义:调用get(key), 或者put(key, value)并不会对线性结构产生任何的影响。正是因为LinkedHashMap提供按照访问的次序来排序的功能，所以它才需要改写HashMap的get(key)方法（HashMap不需要排序）和HashMap.Entry的recordAccess(HashMap)方法public Object get(Object key) {??????? Entry e = (Entry)getEntry(key);??????? if (e == null)??????????? return null;????????e.recordAccess(this);???????? return e.value;??? }void recordAccess(HashMap m) {??????????? LinkedHashMap lm = (LinkedHashMap)m;??????????? if (lm.accessOrder) {??????????????? lm.modCount++;????????????????remove();??????????????? addBefore(lm.header);??????????? }??????? }注 意addBefore(lm.header)是将该entry放在header线性表的最后。（参考LinkedHashMap.Entry extends HashMap.Entry 比起HashMap.Entry多了before, after两个域，是双向的）至于put(key, value)方法， LinkedHashMap不需要去改写，用HashMap的就可以了，因为HashMap在其put(key, value)方法里边已经预留了e.recordAccess(this);还有一个方法值得关注:??? protected boolean removeEldestEntry(Map.Entry eldest) {??????? return false;??? }当 调用put(key, value)的时候，HashMap判断是否要自动增加map的size的作法是判断是否超过threshold， LinkedHashMap则进行了扩展，如果removeEldestEntry方法return false；（默认的实现），那么LinkedHashMap跟HashMap处理扩容的方式一致；如果removeEldestEntry返回 true，那么LinkedHashMap会自动删掉最不常用的那个entry（也就是header线性表最前面的那个）。
这会造成严重的性能问题吗？答案当然是否定的。因为在这儿的链表操作是常量级的。这也是LinkedHashMap/Set在这儿比TreeMap/Set性能更高的原因。
同样，LinkedHashMap/Set也不是thread-safe的。如果在多线程下访问，是需要进行外部同步，或者使用Collections.synchronizedMap()的方法包装成一个thread-safe的Map/Set。
特别需要注意的是，在使用“访问顺序”时，读取节点操作也是“结构变化”的操作。因为，这会改变元素遍历的顺序。所以，在使用 LinkedHashMap的iterator()方法，遍历元素时，如果其它线程有读取操作，也要进行同步。否则，也会抛出同其它fail-fast一 样的由于删除或增加操作而引起的CurrentModificationException的例外。?最后，LinkedHashMap缺省是使用插入顺序的，如何构造一个访问顺序的LinkedHashMap呢？很简单：?public LinkedHashMap(int initialCapacity,?float loadFactor,?boolean accessOrder) accessOrder = true 即可。
?
回来补充一个利用LinkedHashMap来实现LRU的Cache类，看了上面的特性，实现起来实在太简单了！
?
package lru;import java.util.LinkedHashMap;import java.util.Map;import java.util.Map.Entry;/**?*?*<p>Test</p>?*<p>Description:</P>?*<p>Company:Cisco CAS</p>?*<p>Department:CAS</p>?*@Author: Tommy Zhou?*@Since: 1.0?*@Version:Date:2011-5-13?*?**/public class LRUCache<K,V> extends LinkedHashMap<K, V>{??? private LinkedHashMap<K,V>? cache =null ;??? private int cacheSize = 0;??? ?????? public LRUCache(int cacheSize){??? ??? this.cacheSize = cacheSize;??????? int hashTableCapacity = (int) Math.ceil (cacheSize / 0.75f) + 1;??????? cache = new LinkedHashMap<K, V>(hashTableCapacity, 0.75f,true)??????? {??????????? // (an anonymous inner class)??????????? private static final long serialVersionUID = 1;??????????? @Override??????????? protected boolean removeEldestEntry (Map.Entry<K, V> eldest)??????????? {??????????? ??? System.out.println("size="+size());??????????????? return size () > LRUCache.this.cacheSize;??????????? }??????? };??? }?????? public V put(K key,V value){??????? return cache.put(key, value);??? }??? public V get(Object key){??? ??? return cache.get(key);??? }??????? public static void main(String[] args) {??? ??? LRUCache<String, String> lruCache = new LRUCache<String, String>(5);??? ??? lruCache.put("1", "1");??? ??? lruCache.put("2", "2");??? ??? lruCache.put("3", "3");??? ??? lruCache.put("4", "4");??? ??????? ??? System.out.println(lruCache.get("2"));??? ??? lruCache.get("2");??? ??? lruCache.put("6", "6");??? ??? lruCache.put("5", "5");??? ??? System.out.println(lruCache.get("1"));??? ??????? ??????? ??????? ??????? }}
?