SongGuangtao's Blog 首页关于归档标签分类相册
JDK源码分析系列--HashMap
|技术源码
字数总计: 8k|阅读时长: 33 分钟

java.util.HashMap源码一直是面试必问的项目，包括底层数据结构、扩容机制，以及为什么线程不安全等。本文作为JDK源码分析系列的开端，首先从HashMap开始，对其源码进行剖析。源码基于JDK1.8

关于红黑树的部分，本文由于篇幅有限，不再展开。

数据结构

在介绍具体方法前，有必要说明下hashMap的数据结构。

hashMap 内部的最小单元是java.util.HashMap.Node，Node部分源码如下

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

Node用于存储每个键值对，每个Node除了key、value外，还保存有自身key的hash值，以及指向下一个Node的引用next。

在JDK1.8中，hashMap 本质是由 Node 组成的 数组+链表+红黑树 的混合体。

数组+链表+红黑树

因此，hashMap 中的方法，其实都是对这个混合体所做的增删改查。

成员变量

Node数组，hashMap 的主体

1
transient Node<K,V>[] table;

所有键值对的引用，并没有真的存放键值对

1
transient Set<Map.Entry<K,V>> entrySet;

所有Node的数量，包括数组、链表和红黑树中的Node，与Node数组长度没有关系

1
transient int size;

记录hashMap 被修改的次数

1
transient int modCount;

扩容阈值，当Node数量达到这个值，则触发扩容

1
int threshold;

负载系数，决定了扩容阈值的大小，loadFactor = threshold / table.length

1
final float loadFactor;

常量

默认数组长度，16

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

最大数组长度，1 << 30 = 1073741824

1
static final int MAXIMUM_CAPACITY = 1 << 30;

默认负载系数，0.75

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表转红黑树的长度，不带头结点是8

1
static final int TREEIFY_THRESHOLD = 8;

红黑树转链表的长度，不带头结点是6

1
static final int UNTREEIFY_THRESHOLD = 6;

链表转红黑树要求的最小数组长度是64，当小于这个值会优先扩容

1
static final int MIN_TREEIFY_CAPACITY = 64;

构造方法

hashMap构造方法有四种，按是否初始化table，可以分为两类

第一类在创建对象阶段只是定义initialCapacity或loadFactor的值，并不初始化table数组。而要等到第一次put操作时才初始化。是一种延迟加载的思想。

构造一

无参构造，设定负载系数为默认值

1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

构造二

可设定初始化table数组的长度，同时设定负载系数为默认值。内部调用构造三

1
2
3
4
public HashMap(int initialCapacity) {
    // 调用了HashMap(int initialCapacity, float loadFactor)
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

构造三

可设定初始化table数组的长度以及负载系数。需要注意initialCapacity不是实际的数组长度

1
2
3
4
5
6
7
8
9
10
11
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;
    // 这里虽然赋值给了threshold，但在后续put操作时，实际上将threshold作为数组初始化长度
    this.threshold = tableSizeFor(initialCapacity);
}

重点介绍下tableSizeFor方法，该方法作用是，返回大于给定参数的最小的二次幂。

例如cap=3，返回4；cap=9，返回16；cap=25，返回32。这样不论传入的值是多少，都能保证数组的长度是二次幂。

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

关于方法实现原理，参考HashMap的tableSizeFor()方法原理

构造四

将Map转换成HashMap，会在添加元素之前先初始化table数组

首先设定负载系数为默认值

1
2
3
4
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

然后调用putMapEntries方法，在putVal方法内初始化table并将map中的元素添加到hashMap中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) {
            // 通过loadFactor计算出最小的数组长度，并加1
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                // 计算出大于ft的最小二次幂，赋值给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();
            // 初始化table，将Map中的元素循环添加到HashMap中
            putVal(hash(key), key, value, false, evict);
        }
    }
}

成员方法

put方法

put方法整体逻辑如下：

  • 先根据key的hashCode计算hash值，再根据hash值与数组最大索引的与运算，计算节点在数组中的位置；

  • 如果该位置为空，则直接加入节点；

  • 如果该位置有节点，则判断key是否相同，相同则替换节点value；

  • 如果key不同，则继续判断链表的下一个节点key是否相同；

  • 直到遍历到尾节点，将当前节点放在链表末尾；

  • 如果链表长度（包括头节点）>=9且数组长度 < 64，则执行扩容；

  • 如果链表长度（包括头节点）>=9且数组长度 >= 64，则将当前链表转为红黑树；

  • 如果节点数 > 扩容阈值，则扩容。

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hash方法

这里不是直接使用的hashCode。h是一个32位的数，h >>> 16 表示h的高16位，h ^ (h >>> 16)表示h的低16位与高16位进行异或运算，作为新的低16位，原有的高16位在异或运算后保持不变。目的在于使结果更加离散。

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

putVal方法

调用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
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)
        // 首次put，通过resize()方法扩容
        n = (tab = resize()).length;
    
    // 通过hash值与数组最大索引的与运算，计算出在数组中的位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果当前位置为空，则直接存放。由于是首节点，所以next=null
        tab[i] = newNode(hash, key, value, null);
    else { // 表示当前位置已经有值了，p指向当前节点
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 先比较hash值，再比较key，如果相等，让e指向当前节点
            e = p;
        else if (p instanceof TreeNode)
            // 如果是树节点，则走树节点的put逻辑
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 说明是链表，但是首节点的key又不同，则要开始遍历链表
            // binCount计数器
            for (int binCount = 0; ; ++binCount) {
                // 让e指向下一个节点。如果下一个节点为null，说明已经遍历到了链表末尾
                if ((e = p.next) == null) {
                    // 将新节点加到末尾即可
                    p.next = newNode(hash, key, value, null);
                    // binCount=7，此时链表长度来到9(包含首节点)，需要执行转红黑树逻辑(不是一定会转)
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在遍历时发现key完全相同，则停止遍历，此时e指向当前节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 让p指向e，使p在链表上移动
                p = e;
            }
        }
        // e!=null，则说明存在key相等的情况，且e指向该节点
        if (e != null) {
            // 取出oldValue用于返回
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 替换value
                e.value = value;
            // 用于java.util.LinkedHashMap的后处理。这里没作用。
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 记录修改次数
    ++modCount;
    // 能走到这里，说明增加了节点数，需要判断节点数是否超过扩容阈值
    if (++size > threshold)
        // 扩容
        resize();
    // 用于java.util.LinkedHashMap的后处理。这里没作用。
    afterNodeInsertion(evict);
    return null;
}

重点看一下这一句，将数组长度-1和hash值进行与运算

1
p = tab[i = (n - 1) & hash]

由于n始终是2的m次方，所以n-1的二进制一定是111…111(m个)。而与运算的规则是都为1则是1，所以(n - 1) & hash的结果其实取决于hash值的低m位（从右往左数），所以(n - 1) & hash的结果在000…000(m个)到111…111(m个)之间。也就是说i的值在0到n-1之间。

相比hashTable中用hash值对数组长度取余的做法，虽然也能获得在数组中的位置，但位运算显然更高效。

1
int index = (hash & 0x7FFFFFFF) % tab.length;

treeifyBin方法

在putVal方法中可以看到，当链表长度（包含头结点）>=9时，会进入treeifyBin方法

代码中判断条件是if(binCount >= 7)，

第一次进入循环时，节点数是2（p和e），对应binCount =0；

最后一次进入循环时，节点数是9（到p是8个，再加上newNode），对应binCount =7.

image-20220913145102559

treeifyBin方法转红黑树前会先判断数组长度是否达到64。

如果数组长度 < 64，优先扩容（避免过早引入红黑树）。

如果数组长度 >= 64，则执行链表转红黑树逻辑。

具体逻辑是：先将普通节点Node转换成红黑树节点TreeNode，然后补充prev属性，将单向链表转换成双向链表，最后通过TreeNode#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
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 数组长度小于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);
            if (tl == null)
                // 第一次进来，hd指向链表首结点
                hd = p;
            else {
                // 前后节点互相指向，形成双向链表
                p.prev = tl;
                tl.next = p;
            }
            // tl指向尾结点
            tl = p;
        } while ((e = e.next) != null);
        // 将双向链表放到数组原位置上
        if ((tab[index] = hd) != null)
            // 双向链表转红黑树
            hd.treeify(tab);
    }
}

resize方法

当HashMap中数组未初始化，或节点数超出阈值，或链表长度达到8而数组长度不到64时，会触发扩容。

每次扩容，新数组长度总是旧数组的两倍，且数组长度为2的幂次方。因此在扩容后，节点在数组中的位置只有两种可能：保持不变或移动一个旧数组长度。

相对应的，HashMap提供了扩容方法，却没有提供缩容方法，即数组长度只能增大不能减小。

扩容的逻辑如下：

  • 初始化新数组，其长度是旧数组的两倍
  • 从旧数组索引为0开始，遍历数组节点
    • 节点为空，则移动到数组下一位
    • 只有一个节点，则重新计算节点的索引，并放置到新数组上
    • 不止一个节点，则判断节点类型
      • 如果是树节点，则调用树节点的拆分方法，将红黑树拆分成两棵（或一棵）。如果树中节点数<=6，则转换成链表。最后放到新数组对应的位置上
      • 如果是链表节点，则重新计算每个节点的索引，拆分成两条链表（或一条）。最后放到新数组对应的位置上

由于扩容是按照链表的方向进行，因此链表的顺序在扩容后依然得到保证，即在同一条链表（或红黑树）中，先插入节点始终在后插入节点的前面

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
109
110
111
112
113
114
final Node<K,V>[] resize() {
    // 当前数组
    Node<K,V>[] oldTab = table;
    // 当前数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 当前数组扩容阈值
    int oldThr = threshold;
    // 新数组长度，新数组扩容阈值
    int newCap, newThr = 0;
    // 对应数组已初始化的情况
    if (oldCap > 0) {
        // 数组长度 >= 2^30，无法再扩容，因为int最大2^31-1
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 阈值设到最大，表示不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 当前数组长度 >= 16且扩容后数组长度 < 2^30，则将数组长度和扩容阈值各增加一倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    // 数组未初始化，扩容阈值不为0，对应构造方法二或三
    else if (oldThr > 0)
        // 将阈值作为新数组长度
        newCap = oldThr;
    else { // 数组未初始化，阈值为0，对应构造方法一
        // 设定初始长度为16，阈值0.75*16=12
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    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"})
    // 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 赋值给成员变量table
    table = newTab;
    
    // 正式开始数组扩容，先遍历数组，从每个数组节点开始再遍历链表（或红黑树）
    if (oldTab != null) {
        // 遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 当前节点置空
                oldTab[j] = null;
                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 { // 遍历链表，将一个链表分成两个（有可能一个）
                    // 位置不变的链表头节点，位置不变的链表尾节点
                    Node<K,V> loHead = null, loTail = null;
                    // 位置改变的链表头节点，位置改变的链表尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        // 记录下一个链表节点，方便指针在链表上移动
                        next = e.next;
                        // 为0表示当前节点位置不变
                        if ((e.hash & oldCap) == 0) {
                            // 首次进来，尾节点为空
                            if (loTail == null)
                                // e作为头节点
                                loHead = e;
                            else
                                // 尾节点不为空，则让next指向e
                                loTail.next = e;
                            // e成为尾结点
                            loTail = e;
                        } else { // 说明当前节点位置改变
                            // 首次进来，尾节点为空
                            if (hiTail == null)
                                // e作为头节点
                                hiHead = e;
                            else
                                // 尾节点不为空，则让next指向e
                                hiTail.next = e;
                            // e成为尾结点
                            hiTail = e;
                        }
                        // e指向下一个节点，继续循环，直到当前链表遍历结束
                    } while ((e = next) != null);
                    // 说明位置不变的链表存在
                    if (loTail != null) {
                        // 尾节点指向null
                        loTail.next = null;
                        // 将链表放置在数组原位置
                        newTab[j] = loHead;
                    }
                    // 说明位置改变的链表存在
                    if (hiTail != null) {
                        // 尾节点指向null
                        hiTail.next = null;
                        // 将链表放置在数组原索引 + oldCap的位置
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

重点：

  • 在链表只有一个节点时，通过下面这句确定新e在新数组中的位置

    1
    newTab[e.hash & (newCap - 1)] = e;

    这一句非常巧妙，newCap - 1的二进制是111…111(n+1个)，oldCap - 1的二进制是111…111(n个)，前者比后者多一个1位。所以e.hash & (newCap - 1)和e.hash & (oldCap - 1)的差别关键就在hash值的最高位上。最高位为0则结果相同，最高位为1则二者相差一个最高位的1，而这个1表示的大小正好就是2^n=oldCap。

    所以扩容的结果就是：这个节点要么位置不变，要么移动oldCap长度

  • 在判断链表上节点是否移动时，用了这一句

    1
    (e.hash & oldCap) == 0

    因为oldCap的二进制是1000…000，所以上面这句实际就是判断hash的最高为是否为0，由上面分析可知，为0就表示不移动。

remove方法

根据hash值定位到在数组中的位置，如果节点是在数组上，则让该位置为null。如果节点在链表或红黑树上，则移除节点的引用即可。

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

removeNode方法

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 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 &&
        // 根据hash值定位到在数组中的位置
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果头节点的key与要删除的key相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 让node指向头节点
            node = p;
        // 如果头节点的key与要删除的key不同，让e指向下一个节点
        else if ((e = p.next) != null) {
            // e是树节点
            if (p instanceof TreeNode)
                // 则找到key相同的树节点，赋值给node
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else { // 是链表节点
                do {
                    // 与当前节点的key相同
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        // node指向当前节点
                        node = e;
                        break;
                    }
                    // 与当前节点的key不同，让p指向e，移动指针
                    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)
                // 是头节点，让下一个节点成为头节点。有两种情况，next为null和不为null
                tab[index] = node.next;
            else
                // 不是头节点，让前一个节点指向下一个节点
                p.next = node.next;
            // 记录修改次数
            ++modCount;
            // 节点数减1
            --size;
            // 用于java.util.LinkedHashMap的后处理。这里没作用。
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

get方法

先根据key的hash值定位到在数组中的位置，再遍历链表或红黑树，key相同则返回value

1
2
3
4
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 根据hash值定位到在数组中的位置
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 首节点key相同，则返回首节点
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 首节点key不同，判断下一个节点
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 是树节点，调用getTreeNode方法查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 节点key相同，则返回
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
              // key不同，则让e指向下一个节点，遍历链表  
            } while ((e = e.next) != null);
        }
    }
    return null;
}

keySet方法

一直想当然认为keySet方法会返回一个java.util.Set集合，里面包含了所有节点的key。实际上keySet方法并没有真的返回一个保存key的集合，而是提供了一个对节点的引用，真正的遍历操作还是通过table数组来完成的。下面跟随源码，看看内部是如何实现的。

keySet是HashMap从java.util.AbstractMap继承而来的成员变量，在初次调用keySet方法时，keySet为空。因此会创建一个java.util.HashMap.KeySet对象。

1
2
3
4
5
6
7
8
9
10
11
public Set<K> keySet() {
    // 初次调用时，keySet为null
    Set<K> ks = keySet;
    if (ks == null) {
        // 创建KeySet对象
        ks = new KeySet();
        // 赋值给keySet，方便下次使用
        keySet = ks;
    }
    return ks;
}

我们知道，在使用增强for循环遍历set集合时，底层实际调用的是迭代器。

KeySet类

查看KeySet源码，发现重写了iterator方法，内部返回一个java.util.HashMap.KeyIterator对象。

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
final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    
    // 增强for循环实际会调用iterator方法
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    
    // 支持Java8的流式编程，原理还是按数组+链表去遍历
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

KeyIterator类

KeyIterator继承了java.util.HashMap.HashIterator。在next方法内部调用了父类的nextNode方法，并返回key

1
2
3
4
5
final class KeyIterator extends HashIterator
    implements Iterator<K> {
    // 调用了父类的nextNode方法
    public final K next() { return nextNode().key; }
}

HashIterator类

调用KeyIterator的构造方法前，会先隐式调用HashIterator的构造方法。该构造方法会初始化next，并使其指向第一个不为null的数组节点。

nextNode方法的作用是：每调用一次，返回next节点，并使next在所在链表上移动一次。直到链表上数据为空，则移动到下一个不为null的数组节点。

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
// 部分源码
abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot
  
    HashIterator() {
        // 初始化预期修改次数
        expectedModCount = modCount;
        // 指向table数组
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { 
            // 如果next为null，则指向下一个元素，直到不为null
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }
   
    public final boolean hasNext() {
        return next != null;
    }
    
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        // next已在构造方法中初始化
        Node<K,V> e = next;
       
        // 先比较预期修改次数，不相等则抛出异常
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
      
        if (e == null)
            throw new NoSuchElementException();
      
        // 若当前链表遍历完成，则进入循环，移动到下一个不为null的数组节点
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }  
}

注意

由此可以看见，keySet方法返回的并不是一个真正的“集合”，那么集合常见的功能必然也是受限的。

HashMap.KeySet完整源码如下：

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
final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

支持remove方法，内部也是调用了HashMap#removeNode方法，与HashMap#remove实现原理相同。

由于未重写add方法，所以在执行时会调用到父类java.util.AbstractCollection#add方法，会报UnsupportedOperationException异常。从另一方面考虑，Map中的基本单元是键值对，add方法只添加一个key肯定是不对的。

1
2
3
4
// AbstractCollection#add
public boolean add(E e) {
    throw new UnsupportedOperationException();
}

values方法

说完keySet方法，values方法原理相似。

values是HashMap从java.util.AbstractMap继承而来的成员变量。首次调用values方法时，values为空，因此会创建一个java.util.HashMap.Values对象

1
2
3
4
5
6
7
8
public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

Values类

Values类重写了iterator方法，返回一个java.util.HashMap.ValueIterator迭代器

1
2
3
4
5
6
// 部分源码
final class Values extends AbstractCollection<V> {
    public final Iterator<V> iterator() { 
      return new ValueIterator(); 
    }
}

ValueIterator类

ValueIterator类重写了next方法，内部同样调用了HashIterator#nextNode方法，区别是这里取了value值

1
2
3
4
final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}

entrySet方法

entrySet方法也相似。区别在于entrySet是HashMap的成员变量，初次调用entrySet方法会返回一个java.util.HashMap.EntrySet对象

1
2
3
4
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

EntrySet类

EntrySet类内部重写了iterator方法，返回一个java.util.HashMap.EntryIterator对象

1
2
3
4
5
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
    }
}

EntryIterator类

EntryIterator类重写了next方法，内部同样调用了HashIterator#nextNode方法

1
2
3
4
final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}

computeIfAbsent方法

computeIfAbsent方法是JDK1.8中新加的方法，该方法接收一个key和一个函数式接口，仅当key对应节点不存在或key对应value为null时才生效。

具体逻辑如下：

  • 当key存在

    • 且对应的value不为null时，返回value，不做任何操作

    • 且对应的value为null时，用该函数式接口的值作为新value，并返回新value

  • 当key不存在时，将key和该函数式接口的值作为新节点，添加到链表头部或红黑树中

computeIfAbsent方法源码如下：

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
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    if (mappingFunction == null)
        throw new NullPointerException();
    int hash = hash(key);
    Node<K,V>[] tab; Node<K,V> first; int n, i;
    int binCount = 0;
    TreeNode<K,V> t = null;
    // 表示key对应的节点
    Node<K,V> old = null;
    // 节点数超过阈值 或 数组未初始化，则先扩容
    if (size > threshold || (tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找到key对应桶的头结点
    if ((first = tab[i = (n - 1) & hash]) != null) {
        // 如果头结点是树节点，则根据key从树中查找，将找到的节点赋值给old
        if (first instanceof TreeNode)
            old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
        else {
            Node<K,V> e = first; K k;
            // 如果头结点是链表节点，则根据key从链表中查找，将找到的节点赋值给old
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            } while ((e = e.next) != null);
        }
        V oldValue;
        // 如果old存在，且old.value不为空，则返回value，程序结束
        if (old != null && (oldValue = old.value) != null) {
            afterNodeAccess(old);
            return oldValue;
        }
    }
    /*
    走到这里，说明old不存在，或old存在但old.value为null
    */
    // 获得函数式接口的值，作为新Value
    V v = mappingFunction.apply(key);
    // 新Value为null，程序结束
    if (v == null) {
        return null;
    } else if (old != null) {
        // old存在且old.value为null，直接替换value
        old.value = v;
        afterNodeAccess(old);
        return v;
    }
    else if (t != null)
        // old不存在，头节点为树节点，添加到树中
        t.putTreeVal(this, tab, hash, key, v);
    else {
        // old不存在，头结点为链表节点，添加到链表头部（即添加到数组中，指向原头节点）
        tab[i] = newNode(hash, key, v, first);
        // 判断转红黑树
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
    }
    ++modCount;
    ++size;
    afterNodeInsertion(true);
    return v;
}

computeIfPresent方法

computeIfPresent方法接收一个key和一个函数式接口，仅当key对应节点存在且key对应value不为null时才生效。

具体逻辑如下：

  • key对应节点不存在或key对应value为null时，返回null，不做任何操作

  • key对应节点存在且key对应value不为null

    • 且函数式接口的结果不为null时，用该结果替换value，并返回新value
    • 且函数式接口的结果为null时，删除该节点，返回null

    computeIfPresent方法源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    if (remappingFunction == null)
        throw new NullPointerException();
    Node<K,V> e; V oldValue;
    int hash = hash(key);
    // key存在且key对应value不为null
    if ((e = getNode(hash, key)) != null && (oldValue = e.value) != null) {
        // 获得函数式接口的结果，作为新value
        V v = remappingFunction.apply(key, oldValue);
        // v存在，则用v替换value，返回v
        if (v != null) {
            e.value = v;
            afterNodeAccess(e);
            return v;
        }
        else
            // v不存在，删除该节点
            removeNode(hash, key, null, false, true);
    }
    return null;
}

compute方法

compute方法接收一个key和一个函数式接口，与上面两者相比，无论key对应节点是否存在，都生效

具体逻辑如下：

  • key对应节点存在
    • 且函数式接口有结果时，用该结果替换value
    • 且函数式接口结果为null，删除节点
  • key对应节点不存在，且函数式接口有结果
    • 且对应桶是树节点时，将key和该函数式接口的值作为新节点，添加到红黑树中
    • 且对应桶是链表节点时，将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 compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    if (remappingFunction == null)
        throw new NullPointerException();
    int hash = hash(key);
    Node<K,V>[] tab; Node<K,V> first; int n, i;
    int binCount = 0;
    TreeNode<K,V> t = null;
    // 表示key对应的节点
    Node<K,V> old = null;
    if (size > threshold || (tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((first = tab[i = (n - 1) & hash]) != null) {
        if (first instanceof TreeNode)
            old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
        else {
            Node<K,V> e = first; K k;
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            } while ((e = e.next) != null);
        }
    }
    V oldValue = (old == null) ? null : old.value;
    // 函数式接口运行结果
    V v = remappingFunction.apply(key, oldValue);
    // 对应节点存在
    if (old != null) {
        // v不为null，则替换old.value
        if (v != null) {
            old.value = v;
            afterNodeAccess(old);
        }
        else
            // v不为null，则删除old节点
            removeNode(hash, key, null, false, true);
    }
    // 对应节点不存在，且v不为null
    else if (v != null) {
        // 头节点是树节点，则添加到树中
        if (t != null)
            t.putTreeVal(this, tab, hash, key, v);
        else {
            // 头结点为链表节点，添加到链表头部
            tab[i] = newNode(hash, key, v, first);
            // 判断转红黑树
            if (binCount >= TREEIFY_THRESHOLD - 1)
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        afterNodeInsertion(true);
    }
    return v;
}

merge方法

merge方法接收一个key，一个value和一个函数式接口为参数，与compute方法相比，可以指定一个默认的value

具体逻辑如下：

  • key对应节点存在
    • 且对应value不为null，则将函数式接口的值替换旧对应value
    • 且对应value为null，则将value替换对应value
  • key对应节点不存在，且value不为null
    • 且对应桶是树节点时，将key和value作为新节点，添加到红黑树中
    • 且对应桶是链表节点时，将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
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
public V merge(K key, V value,
               BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    if (value == null)
        throw new NullPointerException();
    if (remappingFunction == null)
        throw new NullPointerException();
    int hash = hash(key);
    Node<K,V>[] tab; Node<K,V> first; int n, i;
    int binCount = 0;
    TreeNode<K,V> t = null;
    // key对应的节点
    Node<K,V> old = null;
    if (size > threshold || (tab = table) == null ||
        (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((first = tab[i = (n - 1) & hash]) != null) {
        if (first instanceof TreeNode)
            old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
        else {
            Node<K,V> e = first; K k;
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                    old = e;
                    break;
                }
                ++binCount;
            } while ((e = e.next) != null);
        }
    }
    // 节点存在
    if (old != null) {
        V v;
        // 旧value不为null，则将函数式接口的值赋值给v
        if (old.value != null)
            v = remappingFunction.apply(old.value, value);
        else
            // 旧value为null，则将value赋值给v
            v = value;
        // v不为null，则将上面得到的作为新的value
        if (v != null) {
            old.value = v;
            afterNodeAccess(old);
        } else
            // v为null，则删除该节点
            removeNode(hash, key, null, false, true);
        return v;
    }
    // 节点不存在，value不为null，则使用key和value创建新的节点
    if (value != null) {
        if (t != null)
            // 桶对应的是红黑树，则添加为树节点
            t.putTreeVal(this, tab, hash, key, value);
        else {
            // 桶对应的是链表，则添加到链表头
            tab[i] = newNode(hash, key, value, first);
            if (binCount >= TREEIFY_THRESHOLD - 1)
                // 判断转红黑树
                treeifyBin(tab, hash);
        }
        ++modCount;
        ++size;
        afterNodeInsertion(true);
    }
    return value;
}

参考资料

  1. HashMap的tableSizeFor()方法原理
文章作者: SongGT
文章链接: http://www.songguangtao.xyz/2022/08/24/12.JDK源码分析系列--HashMap/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 SongGuangtao's Blog！
源码
大哥大嫂[微信打赏]
过年好[支付宝打赏]