在HashMap中，无法保证元素顺序，LinkedHashMap可以保证有序，这里我看下LinkedHashMap，类图如下，可以看到LinkedHashMap继承HashMap

image.png

一、参数说明

//双向链表头结点
transient LinkedHashMap.Entry<K,V> head;
//双向链表尾节点
transient LinkedHashMap.Entry<K,V> tail;
//true 代表访问排序 false代表插入排序
 final boolean accessOrder;

二、内部类说明

继承HashMap中 Node，可以看到拥有钱前继后继节点，数据是以双向链表存在

    static 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);
        }
    }

三、方法说明

1.创建方法

可以看到LinkedHashMap调用父类构造方法

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

2.put()方法

LinkedHashMap put方法还是调用HashMap中的方法，关键一点，LinkedHashMap 重写了部分方法

   //重写newNode方法
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
   //将节点存放与双向链表节点尾部，也就意味着我们塞入的值会根据塞入的前后顺序放入双向链表
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        //last指向tail了  tail为空证明双向链表为空 ，头结点也指向新入节点
        if (last == null)
            head = p;
        else {
            //因为上面tail已经指向了p 所以将p 放在last后
            p.before = last;
            last.after = p;
        }
    }

上述过程假设我们在LinkedHashMap依次放入a、b、c、d这四个元素，hash表可能如下

image.png

则也会形成关于这四个元素的双向链表，其中a 为双向链表head节点，d为双向链表tail节点

image.png

我们在看下LinkedHashMap 重写的其他方法，这些方法主要针对访问排序做的，因为上面完全可以保证我们插入排序的使用

    //HashMap当put相同key值时候和get获取值时会调用，主要将元素移到双向链表队尾
    void afterNodeAccess(Node<K,V> e) { 
        LinkedHashMap.Entry<K,V> last;
       //可以看到这个方法针对访问排序，并且要移除的e不是尾节点
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //要把这个元素放到双向链表队尾，则这个元素的后继节点指向应该为null
            p.after = null;
            //b为null 则证明要移除的元素是双向链表头结点
            if (b == null)
                head = a;
           //b不为null ，b此时为e的前继节点，则将b的的后继节点指向于e的后续节点，这里还未对before进行处理
            else
                b.after = a;
           //移除掉的元素不是双向链表尾节点，a是为e的后继节点，则将a的前继节点指向b
            if (a != null)
                a.before = b;
         //a 为空代表移除掉的元素是双向链表尾节点，前面已经判断了e不为尾节点，这里有个疑问
            else
                //last指向b
                last = b;
              //正常情况不会出现last为null
            if (last == null)
                head = p;
            else {
               //因为要将e置为队列尾部，所以将e的before置为原双向链表尾节点，并将原来双向链表尾节点的后继节点置为e
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }
   //LinkedHashMap在put时会调用
    void afterNodeInsertion(boolean evict) { 
        LinkedHashMap.Entry<K,V> first;
         //这里会移除掉一些元素，是为LRU准备的，LinkedHashMap目前没有实现
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
   //LinkedHashMap目前没有实现
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

3.get()方法

getNode还是调用HashMap方法获取，可以看到针对访问排序进行了特殊处理，我们前面已经讲过，这里不做陈述。

    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;
    }