jdk1.8 LinkedHashMap原理

╰+哭是因爲堅強的太久メ 2023-01-15 09:29 127阅读 0赞

# LinkedHashMap #

HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表的HashMap。由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap的元素存取过程基本与HashMap基本类似，只是在细节实现上稍有不同。当然，这是由LinkedHashMap本身的特性所决定的，因为它额外维护了一个双向链表用于保持迭代顺序。

### 特点 ###

*  key和value都允许为空
 *  key重复会覆盖,value可以重复
 *  有序的(双向链表来维护顺序性)
 *  LinkedHashMap是非线程安全的

## LinkedHashMap结构图： ##

LinkedHashMap的实现主要分两部分，一部分是哈希表，另外一部分是链表（双向）。哈希表部分（有个别方法重写了）继承了HashMap，拥有了HashMap那一套高效的操作，而链表保证对哈希表迭代时的有序性，而这个有序是指键值对插入的顺序（默认）。另外，当向哈希表中重复插入某个键的时候，不会影响到原来的有序性。所以我们要看的就是LinkedHashMap中链表的部分，了解它是如何来维护有序性的。

LinkedHashMap 的大致实现如下图所示，当然链表和哈希表中相同的键值对都是指向同一个对象，这里把它们分开来画只是为了呈现出比较清晰的结构。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5_size_16_color_FFFFFF_t_70][]

从上图中可以看出，LinkedHashMap其实就是一个哈希表（HashMap）和一个双向链表构成的。说下这个双向链表吧，这个链表只是维护了键值对的插入顺序。比如先插入（k1,v1） 简称a,再插入（k2,v2）简称b,  那么a就是头（head）,如果b是最后一个，那b就是tail(最后一个插入的是tail)。那a.after就指向b,b.before指向a。  before、after、tail、head后面会提到。

accessOrder变量的值决定了该`LinkedHashMap`按插入顺序有序还是按访问顺序有序。accessOrder默认false是按插入顺序有序，为true是按访问顺序有序，下面介绍构造方法会说这个参数

## LinkedHashMap接口 ##

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

## LinkedHashMap构造函数 ##

public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
    
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
    
        public LinkedHashMap() {
            //调用HashMap的无参构造方法  默认长度也是16  负载因子也是0.75
            super();
            //false表示按put的先后排序，true表示按访问的顺序排序
            accessOrder = false;
        }
    
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }
    
        public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

LinkedHashMap存储数据是有序的，而且分为两种：插入顺序和访问顺序。这里accessOrder设置为false，表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap提供了5种构造函数，其中有四个构造函数的accessOrder默认是为false,还有一种可以设置accessOrder的构造方法，我们来look下这个构造方法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5_size_16_color_FFFFFF_t_70 1][]

可以看出accessOrder为true，是按访问顺序有序，也就是被访问的元素被移动到双向链表的末尾。

## init 方法（JDK1.6） ##

从上面的五种构造函数我们可以看出，无论采用何种方式创建LinkedHashMap，其都会调用HashMap相应的构造函数。事实上，不管调用HashMap的哪个构造函数，HashMap的构造函数都会在最后调用一个init()方法进行初始化，只不过这个方法在HashMap中是一个空实现，而在LinkedHashMap中重写了它用于初始化它所维护的双向链表。例如，HashMap的参数为空的构造函数以及init方法的源码如下：

/**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            table = new Entry[DEFAULT_INITIAL_CAPACITY];
            init();
        }
    
       /**
         * Initialization hook for subclasses. This method is called
         * in all constructors and pseudo-constructors (clone, readObject)
         * after HashMap has been initialized but before any entries have
         * been inserted.  (In the absence of this method, readObject would
         * require explicit knowledge of subclasses.)
         */
        void init() {
        }

在LinkedHashMap中，它重写了init方法以便初始化双向列表，源码如下：

/**
         * Called by superclass constructors and pseudoconstructors (clone,
         * readObject) before any entries are inserted into the map.  Initializes
         * the chain.
         */
        void init() {
            header = new Entry<K,V>(-1, null, null, null);
            header.before = header.after = header;
        }

因此，我们在创建LinkedHashMap的同时就会不知不觉地对双向链表进行初始化。

## LinkedHashMap元素节点 ##

LinkedHashMap中的节点元素为Entry<K,V>，直接继承HashMap.Node<K,V>

//LinkedHashMap中的Entry
    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);
            }
        }
    
    //HashMap中的Entry
    static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;final K key;V value;Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;this.key = key;this.value = value;this.next = next;
            }
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;value = newValue;
                return oldValue;
            }
    
            public final boolean equals(Object o) {
                if (o == this)return true;
                if (o instanceof Map.Entry) {
                    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                    if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                        return true;
                }
                return false;
            }
        }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5_size_16_color_FFFFFF_t_70 2][]![这里写图片描述][SouthEast]

LinkedHashMap的Entry<K,V>是在HashMap的Entry<K,V>节点基础属性上扩展了  before和after属性。

next是用于维护HashMap指定table位置上连接的Entry顺序的;before、after是用于维护Entry插入的先后顺序的.

正是因为before、after和header的存在,LinkedHashMap才形成了循环双向链表.

需要注意的是,header节点,是LinkedHashMap的一个属性,它并不保存key-value内容,它是双向链表的入口.

## LinkedhashMap常见方法 ##

HashMap源码中有这三个空的方法，其实这三个方法表示的是在访问、插入、删除某个节点之后，进行一些处理，它们在LinkedHashMap都有各自的实现。LinkedHashMap正是通过重写这三个方法来保证链表的插入、删除的有序性。

// Callbacks to allow LinkedHashMap post-actions
        void afterNodeAccess(Node<K,V> p) { }
        void afterNodeInsertion(boolean evict) { }
        void afterNodeRemoval(Node<K,V> p) { }

在LinkedHashMAP中这三个方法的介绍：

//移动节点到尾部
    void afterNodeAccess(Node<K,V> e) { // move node to last
            LinkedHashMap.Entry<K,V> last;
            if (accessOrder && (last = tail) != e) {
                LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e,
                b = p.before, a = p.after;
                p.after = null;//p==e即是当前节点，要移动到双向链表尾部的话 p.after要为null(最后一个节点)
                if (b == null)//b是p(当前节点)的前一个节点，如果b为null，那p后面那个节点a就是双向链表的头（相当于当前节点p被访问的时候排在双向链表的第一个节点,因为要移动最后，那当前节点p的后一个节点上位到第一位）
                    head = a;
                else//else就说明当前节点p前后都有节点，p的前面是b,后面是a，因为p要移动到双向链表的末尾，那就是把p拽出来，把a和b连接起来呗
                    b.after = a;
                if (a != null)//a是p后面的节点，a不为null，还是相当于p前面是b（b可能为null,b=null,p移动到最后，a作为头，那么a.before=b=null成立）,后面是a.把p拽出来，把a和b连接起来呗
                    a.before = b;
                else//这个else有点绕，a是p的后面节点，a是null，那就说明p是最后一个节点了，此处假设要把p拽出来，先不放双向链表，那p的前面节点b就是last了吧---》但是我认为他不会走else，因为前面(last = tail) != e  能得出 p=e这个当前界面不可能是tail吧
                    last = b;
                if (last == null)//这last为null，则上面的last=b是不成立的，也就是说当前节点是头了
                    head = p;
                else {//last=b成立，因为p要放在最后了，那last后面一定是p了
                    p.before = last;
                    last.after = p;
                }
                tail = p;//p成为tail
                ++modCount;
            }
        }

把当前节点e移至链表的尾部。因为使用的是双向链表，所以在尾部插入可以以O(1)的时间复杂度来完成。并且只有当accessOrder设置为true时，才会执行这个操作。在HashMap的putVal方法中，就调用了这个方法

void afterNodeInsertion(boolean evict) { // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
            if (evict && (first = head) != null && removeEldestEntry(first)) {
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
        }
    
    final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
            Node<K,V>[] tab; Node<K,V> p; int n, index;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
                Node<K,V> node = null, e; K k; V v;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
                else if ((e = p.next) != null) {
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                    else {
                        do {
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) {
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    else if (node == p)
                        tab[index] = node.next;
                    else
                        p.next = node.next;
                    ++modCount;
                    --size;
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

afterNodeInsertion方法是在哈希表中插入了一个新节点时调用的，它会把链表的头节点删除掉，删除的方式是通过调用HashMap的removeNode方法。 不过这个removeEldestEntry（）方法一直返回的false

void afterNodeRemoval(Node<K,V> e) { // unlink
            LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e,
            b = p.before, a = p.after;
            p.before = p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a == null)
                tail = b;
            else
                a.before = b;
        }

这个方法是当HashMap删除一个键值对时调用的，它会把在HashMap中删除的那个键值对一并从链表中删除，保证了哈希表和链表的一致性。

### put()方法 ###

LinkedHashMap中并有put方法，而是调用HashMap中的put()方法，但是重写了newNode方法来构建自己的节点对象

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    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);
            else {
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    
    //HashMap中的newNode方法：
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
       return new Node<>(hash, key, value, next);
     }
    
    //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;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
        }

除此之外LinkedHashMap还重写了afterNodeAccess和afterNodeInsertion方法。

**`afterNodeInsertion`**方法用于移除链表中的最旧的节点对象，也就是链表头部的对象。但是在JDK1.8版本中，可以看到`removeEldestEntry`一直返回`false`，所以该方法并不生效。如果存在特定的需求，比如链表中长度固定，并保持最新的N的节点数据，可以通过重写该方法来进行实现。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    	    LinkedHashMap.Entry<K,V> first;
    	    if (evict && (first = head) != null && removeEldestEntry(first)) {
    	        K key = first.key;
    	        removeNode(hash(key), key, null, false, true);
    	    }
    	}
    	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    	    return false;
    	}

**`afterNodeAccess`**方法实现的逻辑，是把入参的节点放置在链表的尾部（代码上面有）。

### get()方法 ###

LinkedHashMap的get方法其实可以说就是沿用了HashMap的get方法，唯一不同的是当accessOrder=true，做了一次访问顺序的一个排序

public V get(Object key) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)//getNode直接调用HashMap中的getNode方法
                return null;
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }
    final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                if ((e = first.next) != null) {
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

### remove方法  ###

LinkedHashMap调用了HashMap中的remove方法，但是重写了afterNodeRemoval方法（代码见上），删除节点的时候，调整了双向链表的结构。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5_size_16_color_FFFFFF_t_70]: /images/20221022/c80a093312034aecb3f2a899ee7680e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5_size_16_color_FFFFFF_t_70 1]: /images/20221022/3a39acb8a4f44303882887062b298dfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210422143549525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MDQ0NDE5,size_16,color_FFFFFF,t_70
[SouthEast]: https://img-blog.csdn.net/20170512155609530?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvanVzdGxvdmV5b3Vf/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast