LinkedHashMap与LinkedHashSet可预知迭代顺序

一，简介

       jdk中HashMap和HashSet的遍历是无序的，而LinkedHashMap和LinkedHashSet是两种可以预知迭代顺序的集合类。LinkedHashMap支持两种迭代顺序(插入顺序和访问顺序，其中默认是插入顺序)。而LinkedHashSet仅支持按插入顺序遍历。

二，实现原理

      LinkedHashMap<K,V>继承自HashMap<K,V>，与HashMap的区别是LinkedHashMap底层还维护着一个双向循环链表（用于记录元素的插入顺序或访问顺序）。

      结构图：

      JDK源码：

     

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * The head of the doubly linked list.
     */
    private transient Entry<K,V> header;//双向循环链表的表头

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    private final boolean accessOrder;
    
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;//默认为插入顺序，如果要以访问顺序遍历，需要设置为true
    }

    public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
    /**
     *LinkedHashMap重写了HashMap中的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;
    }
    
      /**
     * LinkedHashMap entry. 
     * 由于继承于HashMap.Entry<K,V>，所以Entry<K,V>实际上包含以下三个Entry<K,V>属性：before,after,next(HashMap是基于单链表+数组实现的，next单链表节点的后继元素)。
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;//双向链表中节点的前驱和后继节点引用

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

        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * This method is invoked by the superclass whenever the value
         * of a pre-existing entry is read by Map.get or modified by Map.set.
         * If the enclosing Map is access-ordered, it moves the entry
         * to the end of the list; otherwise, it does nothing.
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {//如果是访问顺序，则修改header引用为最新访问的节点元素
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }
}

   LinkedHashMap中的访问顺序遍历，已经为我们实现LRU算法(最近最少使用算法)提供了便利。记录访问顺序：将最新访问的元素添加到双向循环链表的表头，并从原来的位置删除。由于链表的增加、删除操作是常量级的，故并不会带来性能的损失。LinkedHashMap类是重写了HashMap中的get方法（添加记录访问顺序逻辑）。

   下面介绍一下LinkedHashSet的实现原理

    LinkedHashSet是继承HashSet实现的,而HashSet是不具备按插入顺序遍历的。那么LinkedHashSet又是如何实现按插入顺序遍历的呢？JDK源码如下：

  

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    /**
     * Constructs a new, empty linked hash set with the specified initial
     * capacity and load factor.
     *
     * @param      initialCapacity the initial capacity of the linked hash set
     * @param      loadFactor      the load factor of the linked hash set
     * @throws     IllegalArgumentException  if the initial capacity is less
     *               than zero, or if the load factor is nonpositive
     */
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    /**
     * Constructs a new, empty linked hash set with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param   initialCapacity   the initial capacity of the LinkedHashSet
     * @throws  IllegalArgumentException if the initial capacity is less
     *              than zero
     */
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    /**
     * Constructs a new, empty linked hash set with the default initial
     * capacity (16) and load factor (0.75).
     */
    public LinkedHashSet() {
        super(16, .75f, true);
    }

    /**
     * Constructs a new linked hash set with the same elements as the
     * specified collection.  The linked hash set is created with an initial
     * capacity sufficient to hold the elements in the specified collection
     * and the default load factor (0.75).
     *
     * @param c  the collection whose elements are to be placed into
     *           this set
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
}

   通过阅读JDK源码，发现LinkedHashSet中并没有像LinkedHashMap一样实现一个记录可预订顺序的双向循环链表。那肯定是HashSet帮LinkedHashSet做了这件事， 于是乎继续阅读HashSet实现源码。

 

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

     public HashSet() {
	map = new HashMap<E,Object>();
    }
    
     /**访问权限为public，组合的是HashMap*/
    public HashSet(int initialCapacity, float loadFactor) {
	map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }
    /**访问权限为defalut为包内访问，组合的是LinkedHashMap,由于HashSet没有提供可以设置
     * accessOrder属性的构造函数，则LinkedHashSet仅具备按插入顺序遍历的功能
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
	map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }
}

   通过阅读HashSet的源码，LinkedHashSet最终是组合LinkedHashMap来实现的，但由于父类HashSet没有提供赋值accessOrder属性的入口，所以只具备按插入顺序遍历的功能。平常我们在应用中使用的HashSet都是基于组合HashMap实现的，所以HashSet的遍历是无序的。

三，总结

   LinkedHashMap(插入顺序和访问顺序)和LinkedHashSet(插入顺序)，这两种集合类操作是非线程安全的。