集合框架源码分析五之LinkedHashMap，LinkedHashSet

    LinkedHashMap是为了解决遍历Hash表的无序问题，它内部维护了一个链表用于记录你插入元素（或你访问元素的顺序）的位置，遍历时直接遍历链表，元素的顺序即为你插入的顺序，但是Entry对象要多加两个成员变量before和after用于记录链表的前驱和后继。所以LinkedHashMap的的存储效率要低于HashMap，但是遍历效率要高于HashMap。
java.util.LinkedHashMap

import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

/**
 * LinkedHashMap内部不仅存储了一个散列表，
 * 也维护了一个链表，
 * 根据链表中元素的顺序可以分为：按插入顺序的链表，和按访问顺序(调用get方法)的链表。
 * 默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素
 * 移至链表尾部，不断访问可以形成按访问顺序排序的链表。
 * 可以重写removeEldestEntry方法返回true值指定插入元素时移除最老的元素
 */
public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V>
{

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * 此Map中维护的一个双向循环链表的头节点
     */
    private transient Entry<K,V> header;

    /**
     * 
     * 遍历Map的顺序的变量，
     * true为按访问顺序遍历
     * false为按插入顺序遍历
     */
    private final boolean accessOrder;

    /**
     * 
     * 构造一个空的，按插入顺序遍历的LinkedHashMap实例，
     * 初始容量与加载因子由自己指定
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
     * 构造一个空的，按插入顺序遍历的LinkedHashMap实例，
     * 初始容量由自己指定
     */
    public LinkedHashMap(int initialCapacity) {
    	super(initialCapacity);
        accessOrder = false;
    }

    /**
     * 
     * 构造一个空的，按插入顺序遍历的LinkedHashMap实例
     * 初始容量与加载因子按HashMap的默认值16与0.75
     */
    public LinkedHashMap() {
    	super();
        accessOrder = false;
    }

    /**
     * 构造一个非空，按插入顺序遍历的LinkedHashMap实例
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity,
			 			 float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    
    /**
     * 
     * 在HashMap每个构造方法中都会调用一次此init()方法
     * 这里是初始化一个双向循环链表的头节点
     */
    void init() {
        header = new Entry<K,V>(-1, null, null, null);
        header.before = header.after = header;
    }

    /**
     * 
     * 在父类HashMap进行容量扩充时会调用此方法
     * 把原来Entry数组中的对象经过重新计算索引转移到此newTable中
     * 这里与HashMap中的transfer方法的实现不再相同，而且比它更快。
     * 
     * HashMap是遍历Entry数组，需要检查是否为null，如果不为空的话则就需
     * 要遍历数组中的链表，而这里所有的元素都链接成了一个链表，直接遍历此
     * 链表就可以遍历出LinkedHashMap中的所有元素。
     */
    void transfer(HashMap.Entry[] newTable) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            int index = indexFor(e.hash, newCapacity);	 //根据新容量重新计算index
            e.next = newTable[index];	//最后添加的节点放最前面
            newTable[index] = e;
        }
    }


    /**
     * 
     *  查找Map中是否含有本值，这里重写了HashMap的containsValue方法
     *  因为在LinkedHashMap中只需要遍历链表查找，这比HashMap遍历table查找更加
     *  高效和快速
     */
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

    /**
     * 
     * 通过key值获得value，如果没有找到此key则返回null。
	 * 不过返回null也可能是其value为null
	 * 通过contain方法可判断Map中是否含有此键
	 * 
	 * 重写此方法的原因是：
	 * 如果map中链表是按照访问顺序进行排序，
	 * 就需要把本次访问的元素移到链表尾部，表示
	 * 这是你最新访问的元素,以后可能会继续访问它
	 * 
     */
    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;
    }

    /**
     * 移除元素，清空链表
     */
    public void clear() {
        super.clear();
        header.before = header.after = header;
    }

    /**
     * LinkedHashMap 的Entry对象.
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // 包含其前驱和后继的信息.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

        /**
         * 
         * 在链表中移除此对象只需要修改前驱和后继的指针
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * 
         * 把元素插入到指定的存在的元素之前
         * 链表的插入也是修改指针
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * 
         * 当调用父类的put或putAll方法，发现要插入的键已经存在时会调用此方法，
         * 当调用LinkedHashMap的get方法时会调用此方法。
         * 如果LinkedHashMap是按访问顺序遍历的，就移动此Entry
         * 到链表的最后位置，否则do nothing
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();		//移除它
                addBefore(lm.header);	//再把她添加到链表尾部
            }
        }

        /**
         * 在移除元素时会调用此方法，即调用
         * 父类的remove(key)方法时调用它
         * 这里是改变链表指针，移除链表中的此元素
         */
        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
    	Entry<K,V> nextEntry    = header.after;		//初始为第一个元素
    	Entry<K,V> lastReturned = null;

    	/**
    	 * 检测同步
    	 */
		int expectedModCount = modCount;

		public boolean hasNext() {
	            return nextEntry != header;
		}

		public void remove() {
		    if (lastReturned == null)
		    	throw new IllegalStateException();
		    if (modCount != expectedModCount)
		    	throw new ConcurrentModificationException();
	
	        LinkedHashMap.this.remove(lastReturned.key);
	        lastReturned = null;
	        expectedModCount = modCount;
		}

		Entry<K,V> nextEntry() {
		    if (modCount != expectedModCount)
		    	throw new ConcurrentModificationException();
	        if (nextEntry == header)
	            throw new NoSuchElementException();
	
	        Entry<K,V> e = lastReturned = nextEntry;
	        nextEntry = e.after;
	        return e;
		}
    }

    //依次重写next方法，返回不同的迭代器。
    private class KeyIterator extends LinkedHashIterator<K> {
    	public K next() { return nextEntry().getKey(); }
    }

    private class ValueIterator extends LinkedHashIterator<V> {
    	public V next() { return nextEntry().value; }
    }

    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
    	public Map.Entry<K,V> next() { return nextEntry(); }
    }

    // These Overrides alter the behavior of superclass view iterator() methods
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

    /**
     * 
     * 重写父类addEntry方法
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        createEntry(hash, key, value, bucketIndex);

        
        /*如果子类重写了removeEldestEntry方法并返回true，
                          将在map中移除链表中的第一个元素，否则检测是否需要扩充容量。
          eldest元素即为链表中的第一个元素*/
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        } else {
            if (size >= threshold)
                resize(2 * table.length);	//扩充至原来的2倍
        }
    }

    /**
     * 
     * 重写父类的createEntry方法，此方法不需要检测是否要扩充容量，
     * 与HashMap中此方法的唯一区别时，这里不仅把元素插入到散列表中，
     * 而且将元素插入到了链表尾
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

    /**
     * 
     * 此方法会在调用put()或putAll()方法时调用，此方法告诉linkedHashMap
     * 是否在添加一个元素后移除最老的元素
     * 比如下面代码会让LinedHashMap的大小始终保持在100
     *     private static final int MAX_ENTRIES = 100;
     *
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *        return size() > MAX_ENTRIES;
     *     }
     *  此方法默认返回false，需要子类去复写此方法
     *  
     *  什么是eldest元素?
     *  如果按插入问顺序来说，是map中最先插入的元素
     *  如果按访问顺序来说，是map中最久未被访问的元素
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}

关于LinkedHashSet

/**
 * LinkedHashSet实际上是基于LinkedHashMap的基础上实现的，
 * LinkedHashSet继承自HashSet，在HashSet中有一构造方法
 * HashSet(int initialCapacity, float loadFactor, boolean dummy) 
 * 第三个参数dummy为true时new出了一个LinkedHashMap实例，以Set中的
 * 元素为键，以一个Object的虚假的对象为值，所以HashSet中的元素不可能重复。
 * 以下构造函数dummy都为true
 */
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {

private static final long serialVersionUID = -2851667679971038690L;


public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}


public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}


public LinkedHashSet() {
    super(16, .75f, true);
}


public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}
}