HashMap实现原理分析
小橘子🍊
  2019-08-01 11:18:30 2019-08-01 11:18      

前言

本文是关于 HashMap 实现原理的分析文章，网上关于 HashMap 实现原理分析的文章已经足够多了，所以我这里写这篇文章仅仅是对自己看过的那些文章进行汇总，方便自己以后进行查阅。

本文大部分内容转载自思否作者 ChiuCheng 深入理解HashMap 系列文章，感谢大佬，另外他写的其他几篇文章也十分值得阅读。

HashMap 解决了什么问题

任何数据结构的产生总对应着要解决一个实际的问题，HashMap的产生要解决问题就是：如何有效的 存/取 一组 key-vaule 键值对。key-value 键值对是最常使用的数据形式，如何有效地存取他们是众多语言都需要关注的问题。注意这里有四个关键字如下，下面我们逐个来思考。

  1. key-value键值对

  2. 一组

  3. 存

  4. 取

如何表示 key-value 键值对

在java这种面向对象的语言中，表示一个数据结构自然要用到类，由于对于键值对的数据类型事先并不清楚，显而易见这里应该要用泛型，则表示key-value键值对最简单的形式可以是：

1
2
3
4
class Node<K，V> {
    K key;
    V value;
}

这里我们自定义一个 Node 类，它只有两个属性，一个 key 属性表示键，一个 value 属性表示值，则这个类就代表了一个 key-value 键值对。

当然，我们还需要定义一些方法来操纵这两个属性，例如 get 和 set 方法等，不过根据设计原则，我们应该面向接口编程，所以应该定义一个接口来描述需要执行的操作，这个接口就是 Entry<K，V>，它只不过是对于 Node<K，V> 这个类的抽象，在 java 中，这个接口定义在 Map 这个接口中，所以上面的类可以改为：

1
2
3
4
class Node<K，V> implements Map。Entry<K，V>{
    K key;
    V value;
}

这里我们总结一下，我们定义了一个Node类来表示一个键值对，为了面向接口编程，我们抽象出一个 Entry 接口，并使 Node 类实现了这个接口。至于这个接口需要定义哪些方法，我们暂不细表。这样，我们完成了对于 key-value 键值对的表示。

如何存储 key-value 键值对

在常见的业务逻辑中，我们常常需要处理一组键值对的集合，将一组键值对存储在一处，并根据 key 值去查找对应的 value 。那么我们要如何存储这些键值对的集合呢?其实换个问法可能更容易回答，应该怎样存储一组对象?(毕竟键值对已经被我们表示为 Node 对象了)，在 java 中，存储一个对象的集合无外乎两种方式：数组或者链表，关于数组和链表的优缺点大家已经耳熟能详了：

  • 数组大小有限，查找性能好，插入和删除性能差

  • 链表大小不限，查找性能差，插入和删除性能好

这里应该选哪种形式呢？那得看实际的应用了，在使用键值对时，查找和插入，删除等操作都会用到，但是在实际的应用场景中，对于键值对的查找操作居多，所以我们当然选择数组形式，在 HashMap 中该数组被表示为：

Node<K,V>[] table;

总结：我们选择数组形式来存储 key-value 对象。为了便于下文描述，我们将数组的下标称为索引(index)，将数组中的一个存储位置称为数组的一个存储桶(bucket)。

如何有效地根据key值查找value

前面已经讲到，我们选择数组形式来存储 key-value 对象，以利用其优良的查找性能，数组之所以查找迅速，是因为可以根据索引(数组下标)直接定位到对应的存储桶(数组所存储对象的位置)。但是实际应用中，我们都是通过 key 值来查找 value 值，怎么办呢？

一种方式就是遍历数组中的每一个对象，查看它的 key 是不是我们要找的key，但是很明显，这种方式效率低下(而且这不就是链表的顺序查找方式吗？) 完全违背了我们选择数组来存储键值对的初衷。

为了利用索引来查找，我们需要建立一个 key -> index 的映射关系，这样每次我们要查找一个 key 时，首先根据映射关系，计算出对应的数组下标，然后根据数组下标，直接找到对应的 key-value 对象，这样基本能以 o(1) 的时间复杂度得到结果。

这里，将 key 映射成 index 的方法称为hash算法，我们希望它能将 key 均匀的分布到数组中。

这里插一句，使用 Hash 算法同样补足了数组插入和删除性能差的短板，我们知道，数组之所以插入删除性能差是因为它是顺序存储的，在一个位置插入节点或者删除节点需要一个个移动它的后续节点来腾出位或者覆盖位置。使用hash算法后，数组不再按顺序存储，插入删除操作只需要关注一个存储桶即可，而不需要额外的操作。

如何解决hash冲突

这个问题其实是由上一个问题引出的，虽然我们要求 hash 算法能将 key 均匀的分布到数组中，但是它只能尽量做到，并不是绝对的，更何况我们的数组大小是有限的，保不齐我们的 hash 算法将就两个不同的 key 映射成了同一个 index 值，这就产生了 hash 冲突，也就是两个 Node 要存储在数组的同一个位置该怎么办?

解决hash冲突的方法有很多，在 HashMap 中我们选择链地址法，即在产生冲突的存储桶中改为单链表存储。此外还有一些其它的用于解决 hash 冲突的的办法如下，详细的请参考文章 解决哈希（HASH）冲突的主要方法。

  • 开放地址法：线性探查法、线性补偿探测法 、随机探测

  • 拉链法：HashMap 即采用该方式

其实，最理想的效果是，Entry 数组中每个位置都只有一个元素，这样查询的时候效率最高，不需要遍历单链表，也不需要通过equals 去比较 Key，而且空间利用率最大。链地址法使我们的数组转变成了链表的数组，其结构如下：

HashMap 的数组加链表结构

至此，我们对key-value键值对的表示变为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
    }
    ...
}

链表长度过长怎么办

我们知道，链表查找只能通过顺序查找来实现，因此，时间复杂度为 o(n)，如果很不巧，我们的 key 值被 Hash 算法映射到一个存储桶上，将会导致存储桶上的链表长度越来越长，此时，数组查找退化成链表查找，则时间复杂度由原来的 o(1) 退化成 o(n)。

为了解决这一问题，在 java8 中，当链表长度超过 8 之后，将会自动将链表转换成红黑树，以实现 o(log n) 的时间复杂度，从而提升查找性能。

HashMap 的数组加链表或者红黑树结构

什么时候扩容

前面已经说到，数组的大小是有限的，在新建的时候就要指定，如果加入的节点已经到了数组容量的上限，已经没有位置能够存储 key-value 键值对了，此时就需要扩容。

但是很明显，我们不会等到火烧眉毛了才想起来要扩容，在实际的应用中，数组空间已使用 3/4 之后，我们就会括容。为什么是0.75呢，官方文档的解释是：

the default load factor (.75) offers a good tradeoff between time and space costs.

再说回扩容，有的同学就要问了，咱上面不是将数组的每一个元素转变成链表了吗? 就算此时节点数超过了数组大小，新加的节点会存在数组某一个位置的链表里啊，链表的大小不限，可以存储任意数量的节点啊！

没错，理论上来说这样确实是可行的，但这又违背了我们一开始使用数组来存储一组键值对的初衷，还记得我们选择数组的原因是什么吗？为了利用索引快速的查找！如果我们试图指望利用链表来扩容的话，当一个存储桶的中的链表越来越大，在这个链表上的查找性能就会很差(退化成顺序查找了)，为此，在数组容量不足时，为了继续维持利用数组索引查找的优良性能，我们必须对数组进行扩容。

每次扩容扩多大

我们知道，数组的扩容是一个很耗费 CPU 资源的动作，需要将原数组的内容复制到新数组中去，因此频繁的扩容必然会导致性能降低，所以不可能数组满了之后，每多加一个 node，我们就扩容一次。

但是，一次扩容太大，导致大量的存储空间用不完，势必又造成很大的浪费，因此，必须根据实际情况设定一个合理的扩容大小。在 HashMap 的实现中，每次扩容我们都会将新数组的大小设为原数组大小的两倍。

Hash 算法原理

为了利用数组索引进行快速查找，我们需要先将 key 值映射成数组下标。因为数组的下标是有限的集合，所以我们可以先通过 hash 算法将 key 映射成整数，再将整数映射成有限的数组下标，即 Object -> int -> index。

对于 Object -> int 部分，使用的就是 hash function，而对于 int -> index 部分，我们可以简单的使用对数组大小取模来实现。在 java 中，hash 函数是一个 native 方法，这个方法定义在 Object 类中，所以所有的对象都会继承。因为这是一个本地方法，所以我们无法看到它的具体实现，但是从函数签名上可以看出，该方法将任意对象映射成一个整型值。调用该方法，我们就完成了 Object -> int的映射。

所以将 key 映射成 index 的方式可以是：

1
key.hashCode() % table.length

那么 HashMap 是这样做的吗？事实上，HashMap 定义了自己的散列方法：

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我们知道 int 类型是 32 位的，h ^ h >>> 16 其实就是将 hashCode 的高 16 位和低 16 位进行异或，这充分利用了高半位和低半位的信息，对低位进行了扰动，目的是为了使该 hashCode 映射成数组下标时可以更均匀。另外从这个函数中，我们还可以得到一个意外收获：HashMap 中 key 值可以为 null，且 null 值一定存储在数组的第一个位置。

前面我们提到，将 hash 值转换成数组下标我们可以采用取模运算，但是取模运算是十分耗时的。另一方面，我们知道，当一个数是 2^n 时，任意整数对2^n取模等效于:

1
h % 2^n = h & (2^n -1)

这样我们就将取模操作转换成了位操作，而位操作的速度远远快于取模操作。因此在 HashMap 中，table 的大小都是 2 的 n 次方大小，即使你在构造函数中指定了 table 的大小，HashMap 也会将该值扩大为距离它最近的 2 的整数次幂的值. 这在我们下面分析构造函数的时候就能看到了。

HashMap 构造函数

HashMap 共有四个构造函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

    // 默认初始大小 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 默认负载因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
     
    final float loadFactor;
    
    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;
    
    transient Node<K,V>[] table;
     
    // 没有指定时, 使用默认值
    // 即默认初始大小16, 默认负载因子 0.75
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    // 指定初始大小, 但使用默认负载因子
    // 注意这里其实是调用了另一个构造函数
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    // 指定初始大小和负载因子
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 利用已经存在的map创建HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
}

从代码我们知道，即使我们在构造函数中指定了 initialCapacity，这个值也只被用来计算 threshold，代码如下：

1
this.threshold = tableSizeFor(initialCapacity);

而 threshold 这个值在初始化 table 时，就代表了数组的初始大小，我们看看 tableSizeFor 函数的实现，可以知道它就是得到了大于等于参数的最小的 2 的幂级数。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

最后我们来看最后一个构造函数，它调用了 putMapEntries 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold)
            resize();
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

我们知道，当使用构造函数HashMap(Map<? extends K，? extends V> m) 时，我们并没有为 table 赋值，所以，table 值一定为null，我们先根据传入 Map 的大小计算 threshold 值，然后判断需不需要扩容，最后调用 putVal 方法将传入的 Map 插入 table 中。

HashMap 的 resize 扩容

resize 用于以下两种情况之一：

  • 初始化table

  • 在table大小超过threshold之后进行扩容

下面我们直接来对照源码分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 原table中已经有值
    if (oldCap > 0) {
    
        // 已经超过最大限制, 不再扩容, 直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 注意, 这里扩容是变成原来的两倍
        // 但是有一个条件: `oldCap >= DEFAULT_INITIAL_CAPACITY`
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)    // DEFAULT_INITIAL_CAPACITY 为 16
            newThr = oldThr << 1; // double threshold
    }
    
    // 在构造函数一节中我们知道
    // 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
    // 如果指定了initialCapacity, 该值被初始化成大于initialCapacity的最小的2的次幂
    
    // 这里是指, 如果构造时指定了initialCapacity, 则用threshold作为table的实际大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    
    // 如果构造时没有指定initialCapacity, 则用默认值
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 计算指定了initialCapacity情况下的新的 threshold
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    
    //从以上操作我们知道, 初始化HashMap时, 
    //如果构造函数没有指定initialCapacity, 则table大小为16
    //如果构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
    
    
    // 从下面开始, 初始化table或者扩容, 实际上都是通过新建一个table来完成的
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 下面这段就是把原来table里面的值全部搬到新的table里面
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是清除旧表的引用, 但是真正的node节点还在, 只是现在由e指向它
                oldTab[j] = null;
                
                // 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 如果该存储桶里面存的是红黑树, 则拆分树
                else if (e instanceof TreeNode)
                    //红黑树的部分以后有机会再讲吧
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                
                // 下面这段代码很精妙, 我们单独分一段详细来讲
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

下面我们单独来看看这段设计的很精妙的代码，首先是定义了四个 Node 的引用，从变量命名上，我们初步猜测，这里定义了两个链表，我们把它称为 lo 链表 和 hi 链表， loHead 和 loTail 分别指向 lo 链表的头节点和尾节点， hiHead 和 hiTail 以此类推。

1
2
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

接着是一个 do while 循环代码块如下，其逻辑很简单就是按顺序遍历该存储桶位置上的链表中的节点。如果 (e.hash & oldCap) == 0，我们就将该节点放入 lo 链表，否则放入 hi 链表。如果 lo 链表非空，我们就把整个 lo 链表放到新 table 的 j 位置上，如果 hi 链表非空, 我们就把整个 hi 链表放到新 table 的 j+oldCap 位置上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

综上我们知道，这段代码的意义就是将原来的链表拆分成两个链表，并将这两个链表分别放到新的 table 的 j 位置和 j+oldCap 上, j 位置就是原链表在原 table 中的位置，拆分的标准就是下边的代码，具体的过程可以通过下边的示意图进行说明。

1
(e.hash & oldCap) == 0
HashMap resize 过程链表拆分示意图

关于两个链表的存放位置，可能会有些疑惑，为什么一定是 j 和 j+oldCap 这两个位置呢？

我们假设 oldCap = 16，即 2^4，16 - 1 = 15，二进制表示为 0000 0000 0000 0000 0000 0000 0000 1111 可见除了低 4 位，其他位置都是 0（简洁起见，高位的 0 后面就不写了），则 (16-1) & hash 自然就是取 hash 值的低 4 位，我们假设它为 abcd。

以此类推，当我们将 oldCap 扩大两倍后，新的 index 的位置就变成了 (32-1) & hash，其实就是取 hash 值的低 5 位. 那么对于同一个 Node，低 5 位的值无外乎下面两种情况：

1
2
0abcd
1abcd

其中，0abcd 与原来的 index 值一致，而 1abcd = 0abcd + 10000 = 0abcd + oldCap，故虽然数组大小扩大了一倍，但是同一个 key 在新旧 table 中对应的 index 却存在一定联系：要么一致，要么相差一个 oldCap。

而新旧index是否一致就体现在 hash 值的第 4 位(我们把最低为称作第 0 位)，怎么拿到这一位的值呢，只要通过下边这个计算表达式即可，即 hash & oldCap。

1
hash & 0000 0000 0000 0000 0000 0000 0001 0000

因此可以有如下结论：

如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j

如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap

HashMap 的 put 方法

put 方法在接口中的定义为，第一个参数为 key 所对应的 hash 值，key 和 value 代表我们要进行存储的键值对。第四个参数 onlyIfAbsent 用于决定待存储的 key 已经存在的情况下，要不要用新值覆盖原有的value，如果为true，则保留原有值，false 则覆盖原有值，从下边的调用看，该值为false，说明当key值已经存在时，会直接覆盖原有值。最后一个参数 evict 用来区分当前是否是构造模式，我们在讲解构造函数的时候曾经提到，HashMap 的第四个构造函数可以通过已经存在的 Map 初始化一个 HashMap，如果为 false，说明在构造模式下，这里我们是用在 put 函数而不是构造函数里面，所以为 true。

1
2
3
4
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) */
}

putVal 方法的具体实现如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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是否是空的
    // 我们知道, HashMap的三个构造函数中, 都不会初始Table, 因此第一次put值时, table一定是空的, 需要初始化
    // table的初始化用到了resize函数, 这个我们上一篇文章已经讲过了
    // 由此可见table的初始化是延迟到put操作中的
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 这里利用 `(n-1) & hash` 方法计算 key 所对应的下标
    // 如果key所对应的桶里面没有值, 我们就新建一个Node放入桶里面
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 到这里说明目标位置桶里已经有东西了
    else {
        Node<K,V> e; K k;
        // 这里先判断当前待存储的key值和已经存在的key值是否相等
        // key值相等必须满足两个条件
        //    1. hash值相同
        //    2. 两者 `==` 或者 `equals` 等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // key已经存在的情况下, e保存原有的键值对
        
        // 到这里说明要保存的桶已经被占用, 且被占用的位置存放的key与待存储的key值不一致
        
        // 前面已经说过, 当链表长度超过8时, 会用红黑树存储, 这里就是判断存储桶中放的是链表还是红黑树
        else if (p instanceof TreeNode)
            // 红黑树的部分以后有机会再说吧
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        //到这里说明是链表存储, 我们需要顺序遍历链表
        else {
            for (int binCount = 0; ; ++binCount) {
                // 如果已经找到了链表的尾节点了,还没有找到目标key, 则说明目标key不存在，那我们就新建一个节点, 把它接在尾节点的后面
                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则直接退出
                // 退出时e保存的是目标key的键值对
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 到这里说明要么待存储的key存在, e保存已经存在的值
        // 要么待存储的key不存在, 则已经新建了Node将key值插入, e的值为Null
        
        // 如果待存储的key值已经存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            
            // 前面已经解释过, onlyIfAbsent的意思
            // 这里是说旧值存在或者旧值为null的情况下, 用新值覆盖旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //这个函数只在LinkedHashMap中用到, 这里是空函数
            // 返回旧值
            return oldValue;
        }
    }
    
    // 到这里说明table中不存在待存储的key, 并且我们已经将新的key插入进数组了
    
    ++modCount; // 这个暂时用不到
    
    // 因为又插入了新值, 所以我们得把数组大小加1, 并判断是否需要重新扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict); //这个函数只在LinkedHashMap中用到, 这里是空函数
    return null;
}

put 函数的总结就是：

  • 在 put 之前会检查 table 是否为空，这说明 table 真正的初始化并不是发生在构造函数中，而是发生在第一次 put 的时候。

  • 查找当前 key 是否存在的条件是 p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))。

  • 如果插入的key值不存在，则值会插入到链表的末尾。

  • 每次插入操作结束后，都会检查当前 table 节点数是否大于 threshold，若超过，则扩容。

  • 当链表长度超过TREEIFY_THRESHOLD（默认是8）个时，会将链表转换成红黑树以提升查找性能。