LinkedHashMap的实现方式

HashMap的结构式数组+单向链表，LinkedHashMap继承自HashMap，在原有的基础上新增了四个主要元素，并重写了一些HashMap的方法

/**
* 元素
*/
head    //根结点
before   //前节点
after    //后节点
accessOrder //  true-访问顺序  false-插入顺序
/**
* 方法
*/
newNode()
replacementNode()
newTreeNode()
replacementTreeNode()
afterNodeRemoval()
afterNodeInsertion()
afterNodeAccess()

所以LinkedHashMap维护了一个双向链表，并且该链表定义了迭代顺序，下面分析一下他的存储方式和结构

LinkedHashMap的构造方法均调用了super()，就是调用了HashMap的构造方法，不过在之后给accessOrder赋值了，默认为false

LinkedHashMap并没有选择重写put方法，回顾下HashMap的put方法
put

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);   //1.重写  
        else {
         //忽略部分代码
          ...
        }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); //2.重写
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict); //3.重写
        return null;

在来看看LinkedHashMap重写的方法
1.newNode

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

 private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p; //1
        else {
            p.before = last; //2
            last.after = p; //3
        }
    }

主要代码还是在linkNodeLast中，如果第一次添加或者添加的元素都被清空了，那last==null成立，会给head赋值成为根结点，之后的put里，last==null永远不会成立，通过2、3两次赋值组成一个双向链表

双向链表结构.png

再看看put方法中注释3的重写方法，注释2中的方法会在get的时候被调用，晚点在看

//这个方法也是HashMap专门为LinkedHashMap提供的，在某些条件下会删除最早添加进来的数据
void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMapEntry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

put方法和HashMap的差异并不大，主要的改变是如果选择顺序为访问顺序，那么在get的时候会改变链表的节点位置，方法如下

public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
/**
*accessOrder指的就是顺序，默认是插入顺序，如果是访问顺序的话，会调用afterNodeAccess
*看到了吧，如果是访问顺序的话，那么每次get，都会重新对链表进行位置交换
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        //tail保存的是链表尾部，因为如果是访问顺序，get后的节点都会从尾部插入
        //p=当前节点e，那么b=p的上一个节点，a=p的下一个节点
        //如果p是根结点，那么b一定为null，如果p是尾节点，那么a一定为null
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

用图片解释一下转换的过程，如果get的是最后一个的话，那链表是不会有变化的
改变节点的变化如下

结构变化图.png

其它的方法没有细看过，只看了主要的get方法，大家有兴趣可以去看看