LinkedHashMap源码

LinkedHashMap源码

Scroll Down

LinkedHashMap源码

简介

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外,LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下,该特性很有用,比如缓存。在实现上,LinkedHashMap 很多方法直接继承自 HashMap,仅为维护双向链表覆写了部分方法。所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码。关于 HashMap 的源码分析,本文并不打算展开讲了。

原理

上一章说了 LinkedHashMap 继承自 HashMap,所以它的底层仍然是基于拉链式散列结构。该结构由数组和链表或红黑树组成,结构示意图大致如下:

2020-08-30_105700
LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。其结构可能如下图:
2020-08-30_105713
上图中,淡蓝色的箭头表示前驱引用,红色箭头表示后继引用。每当有新键值对节点插入,新节点最终会接在 tail 引用指向的节点后面。而 tail 引用则会移动到新的节点上,这样一个双向链表就建立起来了。
上面的结构并不是很难理解,虽然引入了红黑树,导致结构看起来略为复杂了一些。但大家完全可以忽略红黑树,而只关注链表结构本身。好了,接下来进入细节分析吧。

内部类

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

Entry的继承关系

1120165-20181119213656738-1642597597

上面的继承体系乍一看还是有点复杂的,同时也有点让人迷惑。HashMap 的内部类 TreeNode 不继承它的了一个内部类 Node,却继承自 Node 的子类 LinkedHashMap 内部类 Entry。这里这样做是有一定原因的,这里先不说。先来简单说明一下上面的继承体系。LinkedHashMap 内部类 Entry 继承自 HashMap 内部类 Node,并新增了两个引用,分别是 before 和 after。这两个引用的用途不难理解,也就是用于维护双向链表。同时,TreeNode 继承 LinkedHashMap 的内部类 Entry 后,就具备了和其他 Entry 一起组成链表的能力。

其他属性


	//指向双向链表的头节点
	transient LinkedHashMap.Entry<K,V> head;
	//指向双向链表的尾节点
	transient LinkedHashMap.Entry<K,V> tail;
	//用来指定LinkedHashMap的迭代顺序
	//true 表示按照访问顺序,会把访问过的元素放在链表后面,放置顺序是访问的顺序
	//false 表示按照插入顺序遍历
	final boolean accessOrder;

构造函数

	//指定初始容量和负载因子
	public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
	//指定初始容量
	public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
	//无参构造,使用HashMap的构造函数,并且指定accessOrder = false,按插入顺序遍历
	public LinkedHashMap() {
        super();
        accessOrder = false;
    }
	//指定初始容量,负载因子和访问顺序
	public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
	//构造包含指定集合中的元素
	public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

上面所有的构造函数默认 accessOrder = false,除了第四个构造函数能够指定 accessOrder 的值。

put方法

LinkedHashMap 中是没有 put 方法的,直接调用父类 HashMap 的 put 方法。关于 HashMap 的put 方法,
我将方法介绍复制到下面:

//hash(key)就是上面讲的hash方法,对其进行了第一步和第二步处理
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
     *
     * @param hash 索引的位置
     * @param key  键
     * @param value  值
     * @param onlyIfAbsent true 表示不要更改现有值
     * @param evict false表示table处于创建模式
     * @return
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
            boolean evict) {
         Node<K,V>[] tab; Node<K,V> p; int n, i;
         //如果table为null或者长度为0,则进行初始化
         //resize()方法本来是用于扩容,由于初始化没有实际分配空间,这里用该方法进行空间分配,后面会详细讲解该方法
         if ((tab = table) == null || (n = tab.length) == 0)
             n = (tab = resize()).length;
         //注意:这里用到了前面讲解获得key的hash码的第三步,取模运算,下面的if-else分别是 tab[i] 为null和不为null
         if ((p = tab[i = (n - 1) & hash]) == null)
             tab[i] = newNode(hash, key, value, null);//tab[i] 为null,直接将新的key-value插入到计算的索引i位置
         else {//tab[i] 不为null,表示该位置已经有值了
             Node<K,V> e; K k;
             if (p.hash == hash &&
                 ((k = p.key) == key || (key != null && key.equals(k))))
                 e = p;//节点key已经有值了,直接用新值覆盖
             //该链是红黑树
             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);
                         //链表长度大于8,转换成红黑树
                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                             treeifyBin(tab, hash);
                         break;
                     }
                     //key已经存在直接覆盖value
                     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;
    }

这里主要介绍上面方法中,为了保证 LinkedHashMap 的迭代顺序,在添加元素时重写了的4个方法,分别是第23行、31行以及53、60行代码:

1 newNode(hash, key, value, null);
2 putTreeVal(this, tab, hash, key, value)//newTreeNode(h, k, v, xpn)
3 afterNodeAccess(e);
4 afterNodeInsertion(evict);

newNode(hash, key, value, null);

	
	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) {
        //使用last记录tail
        LinkedHashMap.Entry<K,V> last = tail;
        //尾指针向后移动为当前插入的节点
        tail = p;
        if (last == null)
            //如果没有tail,意味着还没有头节点,直接插入头部
            head = p;
        else {
            //原始链表不为空,那么将当前节点的上节点指向原始尾节点
            p.before = last;
            //原始尾节点的下一个节点指向当前插入节点
            last.after = p;
        }
    }

也就是说将当前添加的元素设为原始链表的尾节点。

putTreeVal 方法

是在添加红黑树节点时的操作,LinkedHashMap 也重写了该方法的 newTreeNode 方法:

	
	TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

也就是说上面两个方法都是在将新添加的元素放置到链表的尾端,并维护链表节点之间的关系。

对于 afterNodeAccess(e) 方法,

在 putVal 方法中,是当添加数据键值对的 key 存在时,会对 value 进行替换。然后调用 afterNodeAccess(e) 方法:

	//把当前节点放到双向链表的尾部
	void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        //当 accessOrder = true 并且当前节点不等于尾节点tail。这里将last节点赋值为tail节点
        if (accessOrder && (last = tail) != e) {
            //记录当前节点的前继节点和后继节点
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //释放当前节点和后一个节点的关系
            p.after = null;
            //如果当前节点的前驱节点是null
            if (b == null)
                //头节点=当前节点的下一个节点
                head = a;
            else
                //不为null
                //前驱节点的后一节点变为a
                b.after = a;
            //如果后继节点不为null
            if (a != null)
                //a的前继节点为b
                a.before = b;
            else
                //后继节点a为null
                //b为尾节点
                last = b;
            //如果尾节点为null
            if (last == null)
                //p就是头节点
                head = p;
            else {
                //尾节点不为null,p的前驱节点为last
                p.before = last;
                //last的后继节点为p
                last.after = p;
            }
            //尾节点为p
            tail = p;
            ++modCount;
        }
    }	

该方法是在 accessOrder = true 并且 插入的当前节点不等于尾节点时,该方法才会生效。并且该方法的作用是将插入的节点变为尾节点,后面在get方法中也会调用。代码实现可能有点绕,可以借助下图来理解:
1120165-20181120073825056-124637381.png

再看 afterNodeInsertion(evict) 方法

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

该方法用来移除最老的首节点,首先方法要能执行到if语句里面,必须 evict = true,并且 头节点不为null,并且 removeEldestEntry(first) 返回true,这三个条件必须同时满足,前面两个好理解,我们看最后这个方法条件:

	protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

这就奇怪了,该方法直接返回的是 false,也就是说怎么都不会进入到 if 方法体内了,那这是这么回事呢?这其实是用来实现 LRU(Least Recently Used,最近最少使用)Cache 时,重写的一个方法。比如在 mybatis-connector 包中,有这样一个类:

package com.mysql.jdbc.util;

import java.util.LinkedHashMap;
import java.util.Map.Entry;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    protected int maxElements;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        this.maxElements = maxSize;
    }

    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return this.size() > this.maxElements;
    }
}

可以看到,它重写了 removeEldestEntry(Entry<K,V> eldest) 方法,当元素的个数大于设定的最大个数,便移除首元素。

删除元素

同理也是调用 HashMap 的remove 方法,这里我不作过多的讲解,着重看LinkedHashMap 重写的第 46 行方法。

	public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    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;
        //(n - 1) & hash找到桶的位置
        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;
        //如果键的值与链表第一个节点相等,则将 node 指向该节点
        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;
    }

我们看第 46 行代码实现:

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

该方法其实很好理解,就是当我们删除某个节点时,为了保证链表还是有序的,那么必须维护其前后节点。而该方法的作用就是维护删除节点的前后节点关系。

查找元素

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

相比于 HashMap 的 get 方法,这里多出了第 5,6行代码,当 accessOrder = true 时,即表示按照最近访问的迭代顺序,会将访问过的元素放在链表后面。对于 afterNodeAccess(e) 方法,在前面第 4 小节 添加元素已经介绍过了,这就不在介绍。

遍历元素

LinkedHashMap<String,String> map = new LinkedHashMap<>();
        map.put("A","1");
        map.put("B","2");
        map.put("C","3");
        map.get("B");
        Set<Map.Entry<String,String>> entrySet = map.entrySet();
        for(Map.Entry<String,String> entry : entrySet ){
            System.out.println(entry.getKey()+"---"+entry.getValue());
        }
Iterator<Map.Entry<String,String>> iterator = map.entrySet().iterator();
         while(iterator.hasNext()){
             Map.Entry<String,String> entry = iterator.next();
             System.out.println(entry.getKey()+"----"+entry.getValue());
         }

迭代器如何改变顺序

我们把上面遍历的LinkedHashMap 构造函数改成下面的:

LinkedHashMap<String,String> map = new LinkedHashMap<>(16,0.75F,true);

也就是说将 accessOrder = true,表示按照访问顺序来遍历,注意看上面的 第 5 行代码:map.get("B)。也就是说设置 accessOrder = true 之后,那么 B---2 应该是最后输出,我们看一下打印结果:

A---1
C---3
B---2

结果跟预期一致。那么在遍历的过程中,LinkedHashMap 是如何进行的呢?
看****entrySet

	public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }	

发现 entrySet = new LinkedEntrySet() ,接下来我们查看 LinkedEntrySet 类。

	final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED |
                                            Spliterator.DISTINCT);
        }
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                action.accept(e);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

看其中的

	public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }

new了一个LinkedEntryIterator
这个类继承 LinkedHashIterator。

	abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;

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

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

此方法通过链表顺序来访问节点。