HashMap和有序LinkedHashMap实现对比

LinkedHashMap：LinkedHashMap简单来说是一个有序的HashMap，其是HashMap的子类，HashMap是无序的。接下来我们通过对比分析HashMap和LinkedHashMap来了解一下LinkedHashMap是如何实现有序的。首先HashMap及子类LinkedHashMap都提供了一个数组。

Node<K,V>[] table      

 不同key的hash值是分布在这个数组中的，key值不同，经过hash计算的hash值相同的话节点会作为相同hash值节点的next节点

class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
}      

LinkedHashMap提供的节点添加了两个属性before和after节点，用来生成双向循环列表的，这样每次在Map中添加值都会追加到链表的最后一位，这样就按照插入顺序生成了一个链表

class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
}      

在LinkedHashMap中添加了链表的head和tail节点

transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;      

总结：LinkedHashMap实现有序key值的关键就是根据插入顺序另外维护了一个按照插入顺序作为标记的双向循环列表，这样在获取所有数据进行循环获取时获取到的数据就是有序的数据。

LinkedHashMap从迭代器获取到的数据就是有序的

LinkedHashIterator() {
            next = head;
            expectedModCount = modCount;
            current = null;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
      //获取双向链表的下一个数据
            next = e.after;
            return e;
        }      

HashMap从迭代器中获取到的数据就是hash值的相对排序的数据

HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
      //从不断的从table中获取数据，table
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }      

总结：从上面两段HashMap和LinkedHashMap迭代器实现就可以看出LinkedHashMap的实现原理了，简单来说就是访问队列。