HashMap 简介

HashMap是Map接口最常用的实现类，是非线程安全的。在 Jdk1.8 中，底层的数据结构为“数组+链表+红黑树”，相对于之前版本的“数组+链表”的组合性能有很大的提升，这里主要对 Jdk1.8 中的HashMap源码进行分析。

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

AbstractMap其实已经实现了Map接口，所以这里再实现一遍是没有意义的，这是 Java 集合创始的一个小失误。

属性

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
// 默认的初始化容量为 16，HashMap 的初始化时应该确定好需要的容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// table 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的负载因子，为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树的阈值，当链表长度超过 8，同时数组容量大于 64 时则将链表转为红黑树
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表的阈值，当红黑树的节点小于 6 时转换
static final int UNTREEIFY_THRESHOLD = 6;

// 转红黑树时 table 的最小容量，如果 table 容量小于 64，则首先进行扩容而不是转换
static final int MIN_TREEIFY_CAPACITY = 64;

// 存储元素的数组，数组的长度总是 2 的幂次
transient Node<k,v>[] table;

// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;

// 存放元素的个数，注意这个不等于数组的长度。
transient int size;

// 每次扩容和更改 map 结构的计数器
transient int modCount;

// 临界值（容量*填充因子） 当实际大小超过临界值时，会进行扩容
int threshold;

// 加载因子
final float loadFactor;

Node

Node为链表的节点类实现。

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

TreeNode

TreeNode是红黑树的节点实现，其中常用的方法有putTreeVal、getTreeNode和treeify。

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
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
    	final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v)
            
        final TreeNode<K,V> getTreeNode(int h, Object k)
        
        final void treeify(Node<K,V>[] tab)
  ...
}

putTreeVal

putTreeVal主要用来处理红黑树节点，操作时同时还会维护链表的结构。

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
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
      	// 如果目标节点的哈希值小于当前节点，则将 dir 设置为 -1，代表着左查找
        if ((ph = p.hash) > h)
            dir = -1;
      	// 如果目标节点的哈希值大于当前节点，则将 dir 设置为 1，代表着右查找
        else if (ph < h)
            dir = 1;
      	// 如果目标节点哈希值等于当前节点，则继续判断 key，如果相等则当前节点为目标节点，返回该节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
      	// 如果要查找的 key 没有实现 Comparable 接口或者 pk 和 k 的所属类不同
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 第一次执行查找
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
              	// 左右子树分别调用 find 进行查找，如果找到了就返回
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            // 如果依然没有找到，则最后进行一次比较
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
      	// 如果 p 节点的左节点或者右节点为 null，则说明找到了需要放入的位置
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            // 这里维护了 xp->x->xpn 的链表结构
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 进行红黑树的插入平衡操作
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

getTreeNode

getTreeNode主要用来获取红黑树中一个具体的树节点。

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
final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 如果当前节点有父节点，则先找到根节点，之后再调用 find 方法
    return ((parent != null) ? root() : this).find(h, k, null);
}

final TreeNode<K,V> root() {
    // 遍历寻找根节点
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
      	// 输入的哈希值小于当前节点的哈希值，左遍历
        if ((ph = p.hash) > h)
            p = pl;
      	// 大于当前节点的哈希值，右遍历
        else if (ph < h)
            p = pr;
      	// 哈希值相等，进一步判断 key 是否相同，因为不同的 key 可以有相同的哈希值，需要防止哈希冲突
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
      	// 左节点为空，开始遍历右节点
        else if (pl == null)
            p = pr;
      	// 右节点为空，开始遍历左节点
        else if (pr == null)
            p = pl;
      	// 左右节点都不为空的时候，判断向左还是向右
        else if ((kc != null ||
                  // 如果 kc 实现了 Comparable 接口
                  (kc = comparableClassFor(k)) != null) &&
                 // 比较 k 和 kc 的大小，k>pk 则 dir>0，k<pk 则 dir<0
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
      	// 如果没有实现 Comparable 接口，直接向右开始遍历
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    // 没有符合的节点返回空
    return null;
}

不同的节点的哈希值在和table长度与运算之后是可能相等的，所以红黑树中同一个索引的节点的哈希值不一定都相等。比如：

1
2
3
节点 1 的 hash 值：1110 0000 0000 1000 0111
节点 2 的 hash 值：1001 1111 0000 1010 0111
table.length-1:     0000 0000 0000 0000 0111

节点 1 和节点 2 的哈希值并不相同，但是在和table长度与运算后得到的索引位置是相同的。

treeify

treeify方法用来构建一棵以调用该方法的节点为根节点的红黑树。由于红黑树依然维护着链表结构，每次通过next属性获得下一个节点时，都会从根节点开始向下查找，根据hash值的大小找到合适的位置放入，并设置好parent与left或right属性以关联节点。

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
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    // x 的初始值为 root 节点，但是开始时 root 为 null
    // 每次通过 next 获得链表的下一个节点
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        // root 为 null 时，将 x 赋值给 root
        if (root == null) {
            // 根节点没有父节点
            x.parent = null;
            // 根节点必须为黑色
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            // 从 root 节点开始向下查找
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                // 根据哈希值放入到合适的位置
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                // 设置好父节点及左右子节点
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    // 红黑树的插入平衡调整
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 将根节点移动到 table 索引位置的头节点
    moveRootToFront(tab, root);
}

构造函数

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
// 指定容量和负载因子
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);
}

// 指定容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

// 默认构造函数，使用默认的负载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// 包含一个 Map
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

四个构造函数中都没有涉及table的初始化，所以table并不是在HashMap初始化的时候初始化的，而是在第一次put的时候初始化，下文中会有介绍。

tableSizeFor

tableSizeFor方法主要用来计算返回一个大于等于且最接近给定输入的 2 的次方数。代码如下：

1
2
3
4
5
6
7
8
9
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;
}

n |= n >>> x中，>>>表示无符号右移且空位补 0，|=表示两个数的每一位进行或操作。以输入为 97 来解释：

1
2
3
4
5
6
7
n = 97: 0110 0001
n |= n >>> 1:  0111 0001
n |= n >>> 2:  0111 1101
n |= n >>> 4:  0111 1111
n |= n >>> 8:  0111 1111
n |= n >>> 16: 0111 1111
n + 1: 1000 0000 = 128

我们可以发现：只要一直做右移然后按位或运算，最后可以得到一个大于等于输入且最接近给定输入的 2 的次方数。输入的数字最大的情况就是每一位上都是 1，此时输出就等于输入，所以这个方法可以保证输出一定大于等于输入。

hash

hash主要用来计算给定key对应的哈希值：

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

方法中首先得到key的哈希值，然后将它和它的高 16 位进行异或运算得到新的哈希值：

1
2
3
4
5
6
// 1111 1111 1111 1111 0000 0000 0011 0101
key.hashCode();
// 0000 0000 0000 0000 1111 1111 1111 1111
h >>> 16;
// 1111 1111 1111 1111 1111 1111 1100 1010
hashcode = h ^ (h >>> 16);

和高 16 位进行异或运算是为了在table的长度很小时保证哈希值的均匀性，减少碰撞的概率。

(n - 1) & hash

当我们需要定位到key在table中的索引位置时，需要使用除留余数法对table长度取模得到，但是由于取模运算的效率很低，所以这里使用与运算提高效率。假设table的长度为 16，具体过程如下：

1
2
3
4
5
6
// 1111 1111 1111 1111 1111 1111 1100 1010
hashcode = h ^ (h >>> 16);
// 0000 0000 0000 0000 0000 0000 0000 1111
table.length - 1;
// 0000 0000 0000 0000 0000 0000 0000 1010
hash & (table.length - 1);

之后的源码中经常出现(n - 1) & hash，其中 n 就是数组的长度，本质上就是通过上述方法计算数组索引。

resize

resize方法的作用主要为两点：

  1. 当数组并未初始化时，对数组进行初始化；
  2. 若数组已经初始化，则对数组进行扩容，也就是创建一个两倍大小的新数组，并将原来的元素放入新数组中；
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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // 根据老 table 是否为空获得老 table 的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果旧 table 不为空
    if (oldCap > 0) {
        // 如果旧 table 的容量超过最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 阈值设置为最大整型
            threshold = Integer.MAX_VALUE;
            // 直接返回旧 table，不进行扩容
            return oldTab;
        }
      	// 新容量设置为旧容量的两倍
      	// 如果新容量小于最大容量，并且旧容量大于 16，则将阈值提升到原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果旧 table 为空，并且旧阈值大于 0，将旧阈值赋给新容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 如果旧 table 为空，并且旧阈值也为 0
    else {               // zero initial threshold signifies using defaults
        // 新容量设置为默认初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新阈值设置为默认初始化容量*默认负载因子
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新阈值为 0，则使用新容量*负载因子
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
      	// 如果新容量或者新阈值大于最大容量，则新阈值设置为最大整型，以后不再扩容
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 将新阈值赋值给阈值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 使用新容量创建新的 table
    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 索引位置设为空，方便 GC
                oldTab[j] = null;
              	// 如果只有一个节点
                if (e.next == null)
                  	// 根据哈希值和新 table 长度重新计算索引
                    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;
                    }
                }
            }
        }
    }
    // 返回扩容后的新 table
    return newTab;
}

旧数组为空但阈值大于 0

所有的构造函数中都没有对table进行初始化，仅仅通过this.threshold = tableSizeFor(initialCapacity)设置了阈值，所以table真的分配的时间是在第一次扩容的时候，也就是上面else if (oldThr > 0)之后的代码。

链表拆分

原数组位置上的某一条链表的所有节点，若将它们放到扩容后的新数组中，则最多分布在两个不同索引位置的链表上，并且这两个位置的索引值一定是扩容前原索引或者原索引+原容量。下面以table从 8 扩容到 16 为例：

img 
1
2
3
4
table.length         1000(8) -> 10000(16)
table.length - 1     0111(7) -> 01111(15)
0010(2)	             0010(2) -> 00010(2)
1010(10)             0010(2) -> 01010(10)

前文中讲到，索引的计算方法为key.hashCode & (table.length - 1)。假设扩容前的数组容量为8 = 1000，扩容后的数组容量为16 = 10000，则它们对应的table.length - 1为7 = 0111和15 = 01111，不同在于第四位的数字是 0 或 1。如果key.hashCode的第四位是 0，那和0111或01111做与运算的结果都是一样的。如果key.hashCode的第四位是 1，那么得到的结果是不同的。从01111到011111，差值为1000，那么使用1000和key.hashCode做与操作就可以判断第四位是否为 1。如果是从 16 扩容到 32，也就是从01111到0111111，那么差值就是10000，就需要使用10000和key.hashCode做与操作判断第五位是否为 1。实际上，我们可以发现差值就是扩容前的原容量，那么我们将key.hashCode和原容量做与操作就可以知道扩容前后的索引是否有差异。其次，如果索引在扩容后变化，那么一定原索引+旧table的容量，因为扩容前索引保留的几位在扩容后仍然会保留，而需要判断的那一位如果为 1 则正是旧table的容量大小。下面我们再来分析链表拆分的代码：

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
// 创建两个头尾节点，表示两条链表
// 存储原索引位置的链表
Node<K,V> loHead = null, loTail = null;
// 存储原索引+原 table 容量位置的链表
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;

// 循环遍历链表上的每个节点
do {
    next = e.next;
    // e.hash & oldCap 这一步就是前面说的判断多出的这一位是否为 1
    // 若与原容量做与运算，结果为 0，表示将这个节点放入到新数组中，下标不变
    if ((e.hash & oldCap) == 0) {
      	// 若这是不变链表的第一个节点，用 loHead 记录
        if (loTail == null)
            loHead = e;
      	// 否则，将它加入下标不变链表的尾部
        else
            loTail.next = e;
      	// 更新尾部指针指向新加入的节点，第一个节点即是头节点也是尾节点
        loTail = e;
    }
  	// 若与原容量做与运算，结果为 1，表示将这个节点放入到新数组中，下标将改变
    else {
      	// 若这是改变下标链表的第一个节点，用 hiHead 记录
        if (hiTail == null)
            hiHead = e;
      	// 否则，将它加入改变下标链表的尾部
        else
            hiTail.next = e;
      	// 更新尾部指针指向新加入的节点，第一个节点即是头节点也是尾节点
        hiTail = e;
    }
} while ((e = next) != null);

// 所有节点遍历完后，判断下标不变的链表是否有节点在其中
if (loTail != null) {
    // 将这条链表的最后一个节点的 next 指向 null
    loTail.next = null;
    // 同时将其放入新数组的相同位置
    newTab[j] = loHead;
}
// 同理
if (hiTail != null) {
    hiTail.next = null;
    // 不同的是原索引位置要加上 oldCap
    newTab[j + oldCap] = hiHead;
}

treeifyBin

treeifyBin用来将链表节点转为树节点，并且在转换的过程中仍然保持了链表的特点，最后通过treeify方法构建红黑树：

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
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // table 为空或者 table 长度小于 64
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 扩容
        resize();
    // 当前索引位置的节点不为空
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        // 遍历整条链表
        do {
            // 链表节点转为树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            // 尾节点为空，则将 p 赋值给头节点
            if (tl == null)
                hd = p;
            // 尾节点不为空，则将 p 连接到尾节点之后
            else {
                p.prev = tl;
                tl.next = p;
            }
            // 重置尾节点
            tl = p;
        } while ((e = e.next) != null);
        // 索引位置的节点替换为树节点
        if ((tab[index] = hd) != null)
            // 以头节点为根构建红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

put

put方法通过内置的putVal方法添加键值对。putVal中判断了table是否需要扩容，是否需要将链表转化为红黑树以及覆盖原节点的值等：

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
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;
    // table 的长度如果是 0 或者为空，则先进行扩容
    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;
        // 判断当前节点的 hash 和 key 是否和输入的相同，如果相同，将当前 p 节点的值赋给 e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 判断是否是红黑树节点，如果是则需要调用红黑树相关的 put 方法
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 否则为链表节点，遍历链表节点，并且统计链表的节点数 binCount
            for (int binCount = 0; ; ++binCount) {
              	// 如果到达链表尾部，则根据输入的 hash 和 key 等创建一个新的节点加入链表尾部
                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))))
                    // hash 和 key 都相等时，跳出循环，e 节点就是目标节点
                    break;
              	// 迭代过程中将 p 设置为下一个节点
                p = e;
            }
        }
      	// e 节点不为空时，说明链表或者红黑树中包含目标节点，用新值覆盖旧值并且返回旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 只有添加了新节点才会走到这里，table 的 size 需要加一
    ++modCount;
    // 如果 size 超过了阈值，则需要进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

get

通过key的值获取到对应的value：

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
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table 不为空 & table 的长度大于 0 & 根据哈希值得到的数组索引的第一个节点不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果第一个节点的 key 和输入的 key 相同，直接返回第一个节点
        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);
            // 如果是链表，则不断遍历直到 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

remove主要用来删除指定的键值对，输入参数为key的值，代码如下：

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
public V remove(Object key) {
    Node<K,V> e;
    // 如果未找到要删除的节点直接返回 null，否则返回删除节点的 value
    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;
    // table 不为 null & table 的长度大于 0 & 索引位置的链表头节点不为 null
    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;
        // 如果当前节点的哈希值和 key 都和输入的相等，那么当前节点就是目标节点，将其赋值给 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)))) {
            // 是树节点则需要调用树节点的 remove 方法
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 是头节点的话直接将索引位置指向下一个节点
            else if (node == p)
                tab[index] = node.next;
            // p 是 node 节点的上一个节点情况时
            else
                p.next = node.next;
            ++modCount;
            // 总节点数减一
            --size;
            afterNodeRemoval(node);
            // 返回被删除的节点
            return node;
        }
    }
    // 未找到目标节点，直接返回 null
    return null;
}

参考

  1. HashMap 源码解读——逐句分析 resize 方法的实现
  2. HashMap 源码&底层数据结构分析
  3. n |= n ＞＞＞ 1——JDK10 的 HashMap 原理 tableSizeFor(initialCapacity) 方法
  4. java 中的移位运算符：<<,>>,>>>总结