使用LinkedHashMap构建LRU的Cache
这段时间好好整理了一下基础，发现很多对我来说新的东西，里面博大精深的东西真的很多，经常使用HashMap，对HashMap的结构和原理非常了解，但是忽略了还有LinkedHashMap这个好东西。
?
先转一篇blog：
?
LinkedHashMap的特性:
Linked内部含有一个private transient Entryheader;来记录元素插入的顺序或者是元素被访问的顺序。利用这个线性结构的对象，可以帮助记录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.Entryextends 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方法returnfalse；（默认的实现），那么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"));
??? ???
??? ???
??? ???
??? ???
??? }
}
