LinkedHashMap的扩展应用

一. 概述：
        LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。LinkedHashMap实现与HashMap的不同之处在于，LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序（insert-order）或者是访问顺序，其中默认的迭代访问顺序就是插入顺序，即可以按插入的顺序遍历元素，这点和HashMap有很大的不同。

二.LinkedHashMap的accessOrder
    1.访问顺序
        LinkedHashMap除了支持默认的插入顺序，还支持访问顺序。所谓访问顺序(access-order)是指在迭代遍历列表中的元素时最近访问的元素会排在LinkedHashMap的尾部 。从其构造函数中可以看出当accessOrder设为true时即为访问顺序。

 public LinkedHashMap(int initialCapacity,
                   float loadFactor,
                   boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
 }

 

     2.访问顺序时程序举例

        public class LinkedHashMapTest {
       
            public static void main(String[] args) {
                Map<String, Object> map = new LinkedHashMap<String, Object>(16, 0.75F, true);
       
                for (int i = 1; i <= 5; i++) {
                    map.put(i + "", i);
                }
                Iterator<Entry<String, Object>> iterator = map.entrySet().iterator();
                while (iterator.hasNext()) {
                    System.out.println(iterator.next().getValue());
                }
       
                map.get("2");
                map.get("3");
                System.out.println("===============split line==================");
       
                Iterator<Entry<String, Object>> iterator2 = map.entrySet().iterator();
                while (iterator2.hasNext()) {
                    System.out.println(iterator2.next().getValue());
                }
            }
        }

    
    输出如下：

        1
        2
        3
        4
        5
        ===============separator bar ======================
        1
        4
        5
        2
        3

 

    通过例子可以看出，最近经常使用的元素就放在后面，最近最少使用的就排在了链表的前面。
   
三.LinkedHashMap的扩展应用
    基于LinkedHashMap的访问顺序的特点，可构造一个LRU（Least Recently Used）最近最少使用简单缓存。也有一些开源的缓存产品如ehcache的淘汰策略（LRU）就是在LinkedHashMap上扩展的。
   
    1.LruCache的简单代码

public class LruCache<K, V> extends LinkedHashMap<K, V> {
       
            private static final long serialVersionUID = -9062508768983283300L;
           
            /** 最大容量 */
            private int maxCapacity;
       
            public LruCache(int maxCapacity) {
                super(16, 0.75f, true);
                this.maxCapacity = maxCapacity;
            }
       
            public int getMaxCapacity() {
                return this.maxCapacity;
            }
       
            public void setMaxCapacity(int maxCapacity) {
                this.maxCapacity = maxCapacity;
            }
       
            /**
             * 当列表中的元素个数大于指定的最大容量时，返回true,并将最老的元素删除。
             */
            @Override
            protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
                if (super.size() > maxCapacity) {
                    return true;
                }
                return false;
            }
        }

 

    2.测试代码

public class LruCacheTest {
       
            public static void main(String[] args) {
                LruCache<String, Object> cache = new LruCache<String, Object>(10);
       
                for (int i = 1; i <= 15; i++) {
                    cache.put(i + "", i);
                }
       
                // 此时访问指定KEY的元素
                cache.get("10");
       
                Iterator<Entry<String, Object>> iterator = cache.entrySet().iterator();
                for (; iterator.hasNext();) {
                    Entry<String, Object> entry = iterator.next();
                    System.out.println("key=" + entry.getKey() + ",value=" + entry.getValue());
                }
            }
        }

 

        输出如下：

      key=7,value=7
      key=8,value=8
      key=9,value=9
      key=11,value=11
      key=12,value=12
      key=13,value=13
      key=14,value=14
      key=15,value=15
      key=10,value=10

 

四.LinkedHashMap对上述特性支持的分析
    1.添加时删除最老元素
    LinkedHashMap如何在添加元素时把最早放入的元素删除的呢，LinkedHashMap没有提供put方法，而是使用基类HashMap的put方法，看下面的HashMap的put(K key, V value)方法的源代码：

     public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                //HashMap中这个方法没有实现。
                    e.recordAccess(this);
                    return oldValue;
                }
            }
   
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

 

     LinkedHashMap覆盖了HashMap中的这个addEntry(hash, key, value, i)方法，在 LinkedHashMap类中，removeEldestEntry（）永远返回false;
     也就是这个方法，提供了子类更强大功能扩展的机会。

	    void addEntry(int hash, K key, V value, int bucketIndex) {
			createEntry(hash, key, value, bucketIndex);

			// Remove eldest entry if instructed, else grow capacity if appropriate
			Entry<K,V> eldest = header.after;
			//该方法返回false.
			if (removeEldestEntry(eldest)) {
			    removeEntryForKey(eldest.key);
			} else {
			    if (size >= threshold)
				resize(2 * table.length);
			}
	    }

 

   
    2.访问时重组列表
          在获取元素时，LinkedHashMap提供了get()方法，其代码如下：

      public V get(Object key) {
            Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null)
                return null;
                 //最近访问的元素重新插入到最后面。
            e.recordAccess(this);
            return e.value;
      }

 

    HashMap中这个recordAccess（）方法没有实现，只有空的方法体，在LinkedHashMap中的实现如下 ，也就是这个方法，将最近访问的元素给予重组，达到了LRU的目的。                

   void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                   //accessOrder要指定为true.
                if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
                }
        }