深入浅出 JAVA 之集合 - HashMap

1Map<String, String> map = new HashMap<>();
2Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
3while (iterator.hasNext()) {
4    Map.Entry<String, String> entry = iterator.next();
5    System.out.println("key=" + entry.getKey());
6    System.out.println("value=" + entry.getValue());
7}

1Map<String, String> map = new HashMap<>();
2for (Map.Entry<String, String> entry : map.entrySet()) {
3    System.out.println("key=" + entry.getKey());
4    System.out.println("value=" + entry.getValue());
5}

1Map<String, String> map = new HashMap<>();
2for (String key : map.keySet()) {
3    System.out.println("key=" + key);
4    System.out.println("value=" + map.get(key));
5}

1Map<String, String> map = new HashMap<>();
2for (String value : map.values()) {
3    System.out.println("value=" + value);
4}

1public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
2    // 略
3}

 1/**
 2 * 默认初始容量。该值必须是 2 的 n 次幂，默认值为 16
 3 */
 4static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 5
 6/**
 7 * 集合的最大容量。最大不能超过 2^30
 8 */
 9static final int MAXIMUM_CAPACITY = 1 << 30;
10
11/**
12 * 默认的负载因子
13 */
14static final float DEFAULT_LOAD_FACTOR = 0.75f;
15
16/**
17 * 桶中-链表转换为红黑树的阈值
18 */
19static final int TREEIFY_THRESHOLD = 8;
20
21/**
22 * 桶中-红黑树还原为链表的阈值
23 */
24static final int UNTREEIFY_THRESHOLD = 6;
25
26/**
27 * 链表转化为红黑树时对集合最小容量的限制值，如果集合容量小于该值则链表不会转换为红黑树
28 */
29static final int MIN_TREEIFY_CAPACITY = 64;

 1/**
 2 * 存储元素的数组
 3 */
 4transient Node<K,V>[] table;
 5
 6/**.
 7 * 存放具体元素的集合 (俗称的 “桶”)
 8 */
 9transient Set<Map.Entry<K,V>> entrySet;
10
11/**
12 * 记录集合当前大小，即记录集合中键值对个数
13 */
14transient int size;
15
16/**
17 * 记录集合数据修改次数，用于记录迭代过程中集合结构是否发生变化，如果有则迭代时会快速失败
18 */
19transient int modCount;
20
21/**
22 * 集合扩容的阈值，当实际大小超过临界值时，会进行扩容
23 * - ① 如果初始化时给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方
24 *     比如你给定初始化大小 19，实际上初始化大小为 32，即 2^5
25 * - ② 如果是通过 resize 方法进行扩容，则阈值大小为: 数组容量 * 负载因子 (capacity * loadFactor)
26 */
27int threshold;
28
29/**
30 * 集合的负载因子，用于参与阈值计算，控制进行扩容的百分比。 
31 */
32final float loadFactor;

1/**
2 * 无参构造方法
3 */
4public HashMap() {
5    this.loadFactor = DEFAULT_LOAD_FACTOR;
6}

 1/**
 2 * 支持配置初始化容量的构造方法
 3 *
 4 * @param initialCapacity 初始化容量
 5 * @throws IllegalArgumentException 非法参数异常 (如果初始容量为负数或者负载因子为负数，则抛出该异常)
 6 */
 7public HashMap(int initialCapacity) {
 8    // 调用 HashMap(int initialCapacity, float loadFactor) 构造方法
 9    this(initialCapacity, DEFAULT_LOAD_FACTOR);
10}

 1/**
 2 * 支持配置初始化容量与负载因子的构造方法
 3 *
 4 * @param initialCapacity 初始化容量
 5 * @param loadFactor      负载因子
 6 * @throws IllegalArgumentException 非法参数异常 (如果初始容量为负数或者负载因子为负数，则抛出该异常)
 7 */
 8public HashMap(int initialCapacity, float loadFactor) {
 9    // 如果初始化容量为负数，则抛出 IllegalArgumentException 异常
10    if (initialCapacity < 0) {
11        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
12    }
13    // 如果初始化容量大于 MAXIMUM_CAPACITY 值，则就设置初始化容量为 MAXIMUM_CAPACITY
14    if (initialCapacity > MAXIMUM_CAPACITY) {
15        initialCapacity = MAXIMUM_CAPACITY;
16    }
17    // 如果负载因子为负数，或者非数字 (NaN)，则抛出 IllegalArgumentException 异常
18    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
19        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
20    }
21    // 设置【负载因子】和【扩容阈值】变量
22    this.loadFactor = loadFactor;
23    this.threshold = tableSizeFor(initialCapacity);
24}

 1/**
 2 * 返回一个大于等于且最接近 cap 的 2 的幂次方:
 3 *  - 比如传入初始化容量 cap = 9，则返回 2^4，即 16
 4 *  - 比如传入初始化容量 cap = 25，则返回 2^5，即 32
 5 *
 6 * @param cap 传入构造方法中初始化容量
 7 * @return 传入初始化容量 cap 的 2 的幂次方
 8 */
 9static final int tableSizeFor(int cap) {
10    int n = cap - 1;
11    n |= n >>> 1;
12    n |= n >>> 2;
13    n |= n >>> 4;
14    n |= n >>> 8;
15    n |= n >>> 16;
16    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
17}

 1/**
 2 * 支持根据已有 Map 集合创建新集合的构造方法
 3 *
 4 * @param m 已有的 Map 集合
 5 * @throws NullPointerException 空指针异常
 6 */
 7public HashMap(Map<? extends K, ? extends V> m) {
 8    this.loadFactor = DEFAULT_LOAD_FACTOR;
 9    putMapEntries(m, false);
10}

 1/**
 2 * 将传入已有 Map 集合中的全部元素逐个添加到当前集合中
 3 *
 4 * @param m 指定的 Map 集合
 5 * @param evict 当构造方法传入指定 Map 集合时该值为 false，其他情况为 true
 6 */
 7final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 8    // 获得传入 Map 集合的大小，并赋值给变量 s
 9    int s = m.size();
10
11    // 判断传入 Map 集合大小是否存在数据，是则执行下面步骤
12    if (s > 0) {
13        // 判断 table 是否已经初始化:
14        // - 如果 table 已经初始化，则计算存储传入 Map 集合中全部元素所需要的最小容量，然后根据计算结果
15        //   确认是否对当前集合的阈值进行调整。
16        // - 如果 table 没有初始化，则判断传入的 Map 集合大小是否大于当前集合的阈值，然后根据判断结果
17        //   确认是否对当前集合的容量进行扩容。
18        if (table == null) {
19            // --- 计算存储传入 Map 集合所需要的最小容量 ---
20            // s 为传入集合的大小，loadFactor 为传入集合的负载因子，因此下面代码中 s/loadFactor 是
21            // 为了计算存储传入集合所需最小容量，算完成后将值赋给变量 ft，而这里计算结果 +1.0F，则是
22            // 为了防止集合扩容。
23            float ft = ((float) s / loadFactor) + 1.0F;
24            // --- 判断上面计算出的容量是否超出限制 ---
25            // 为了防止计算出的容量超出最大限制，需要判断容量 ft 是否超出容量限制值 MAXIMUM_CAPACITY:
26            // - 如果没有超出最大容量限制，就设置集合容量为 ft，并赋给变量 t
27            // - 如果超出最大容量限制，就设置集合容量为 MAXIMUM_CAPACITY，并赋给变量 t
28            int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
29            // --- 根据计算出的所需容量进行判断，再依据判断结果对当前集合阈值进行调整 ---
30            // 如果计算出的容量 t > 当前集合扩容阈值 threshold，则对当前集合扩容阈值 threshold 进行调整
31            if (t > threshold) {
32                // 调整当前集合的扩容阈值 threshold，将其设置为与最小容量 t 最接近且大于的 【2的n次幂】 的值
33                threshold = tableSizeFor(t);
34            }
35        } else if (s > threshold) {
36            // 执行 resize 方法进行扩容
37            resize();
38        }
39
40        // 执行循环，将传入的 Map 集合中的全部元素逐个添加到当前集合中
41        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
42            K key = e.getKey();
43            V value = e.getValue();
44            putVal(hash(key), key, value, false, evict);
45        }
46    }
47}

 1/**
 2 * 计算 Key 哈希值方法
 3 */
 4static final int hash(Object key) {
 5    // 定义记录 key 哈希值的变量
 6    int h;
 7    // 判断 key 是否为 null:
 8    // - 如果 key 为 null 则直接返回 0。
 9    // - 如果 key不为 null 则获取 key 的哈希值，然后使哈希值进行高位运算，将 h 右移 16 位，最后使 
10    //   (低16位hash) 异或 (高16位hash)，这样得出的哈希值更加散列均匀，可以一定程度减少哈希碰撞。
11    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
12}

 1/**
 2 * 将指定的键值对插入到 HashMap 集合中
 3 *
 4 * @param key 待插入的键
 5 * @param value 待插入的值
 6 * @return 返回与 Key 关联的旧值，分两种情况:
 7 *   - 如果集合中不存在对应的 key，即插入一个新的 key，则返回 null；
 8 *   - 如果集合中已经存在一个相同的 key，则新 value 覆盖旧 value，然后返回旧 value；
 9 */
10public V put(K key, V value) {
11    return putVal(hash(key), key, value, false, true);
12}

 1/**
 2 * 实现 Map.put() 和相关方法。
 3 *
 4 * @param hash Key 的 Hash 值
 5 * @param key 插入的键
 6 * @param value 插入的值
 7 * @param onlyIfAbsent 如果为 true 则不更改现有的值
 8 * @param evict 如果为 false 则表示 table 处于创建模式
 9 * @return 如果插入的 Key 已经存在，则返回已存在 Key 的节点值，否则返回 null
10 */
11final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
12    Node<K,V>[] tab; // 记录 table 数组的变量
13    Node<K,V> p;     // 记录临时 Node 节点的变量，如记录 i 所在数组下标位置的 Node 节点
14    int n;           // 记录 table 数组长度的变量
15    int i;           // 记录 key 经过计算后得到在 table 数组下标位置索引的变量
16
17    // 判断 table 数组是否为空，如果为空则调用 resize() 方法初始化 table 数组
18    if ((tab = table) == null || (n = tab.length) == 0) {
19        n = (tab = resize()).length;
20    }
21
22    // 通过哈希值计算当前 key 在 table 数组中的索引位置，然后判断数组当前位置(桶)是否为空，如果当前数组位置为空，
23    // 则直接在当前位置存储键值对数据，插入链表节点 Node。
24    // 注: 这里 (n-1)&hash 位运算，而不是使用 (n-1)%hash 取模运算，这主要是因为:
25    // - ① 位运算比取模运算效率更高
26    // - ② 保证索引不会发生数组越界
27    // - ③ 保证元素尽可能的均匀分布
28    if ((p = tab[i = (n - 1) & hash]) == null){
29        tab[i] = newNode(hash, key, value, null);
30    }
31    // 键值对数据加入到当前位置，关联到的链表/红黑树中来解决哈希冲突
32    else {
33        Node<K,V> e;  // 记录当前节点的临时变量
34        K k;          // 记录插入数据 key 的变量
35
36        // 判断当前数组下标位置的节点，是否是为要查找的 key 的节点，符合下面两条条件之一则说明就是要查找的节点:
37        // - 如果节点 key 和 hash 与插入的 key 和 hash 相同，则该节点就是要查找的节点;
38        // - 如果插入的 key 不为空，并且插入的 key 和节点 key 相同，则该节点就是要查找的节点;
39        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
40            e = p;
41        }
42        // 判断当前节点是否为红黑树 TreeNode 阶段，则将键值对数据加入到红黑树中
43        else if (p instanceof TreeNode) {
44            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
45        }
46        // 如果以上判断条件都不满足，则说明当前阶段是一个链表阶段，则将键值对数据加入到链表中，并赋给变量 e
47        else {
48            // 从链表头节点开始遍历链表
49            for (int binCount = 0; ; ++binCount) {
50                // 判断是否遍历到了链表的尾结点
51                if ((e = p.next) == null) {
52                    // 创建一个新节点，将其加入到链表的尾部
53                    p.next = newNode(hash, key, value, null);
54                    // 判断链表长度是否 ≥ 链表转换为红黑树的最小节点限制，是则将链表转换为红黑树
55                    if (binCount >= TREEIFY_THRESHOLD - 1) {
56                        treeifyBin(tab, hash);
57                    }
58                    break;
59                }
60                // 判断遍历到的当前阶段，是否为要查找的 key 的节点，如果是则结束当前循环
61                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
62                    break;
63                }
64                // 更改循环的当前元素，使 p 在遍历过程中一直往后移动
65                p = e;
66            }
67        }
68        // 判断变量 e 是否为空，如果不为空，则说明找到了 key 所在节点，需要将插入的新值替换掉老值，然后返回老值
69        if (e != null) {
70            // 获取老值，然后判断变量 onlyIfAbsent 是否为 false，并且老值不为空，如果是则新值会覆盖老值
71            V oldValue = e.value;
72            if (!onlyIfAbsent || oldValue == null) {
73                e.value = value;
74            }
75            afterNodeAccess(e);
76            // 返回老值
77            return oldValue;
78        }
79    }
80    // 使 modCount 值加 1，用于记录 HashMap 的数据结构发生了变化
81    ++modCount;
82    // 如果 HashMap 的大小 size 超过了扩容阈值 threshold，则调用 resize() 方法进行扩容操作
83    if (++size > threshold) {
84        resize();
85    }
86    // 调用 afterNodeAccess 方法，该方法 HashMap 没有任何实现逻辑，目的是为了让子类根据需要自行覆写
87    afterNodeInsertion(evict);
88    return null;
89}

 1/**
 2 * 红黑树中插入键值对的方法
 3 *
 4 * @param map Map集合
 5 * @param tab 数组 table
 6 * @param h   要插入键值对 key 的 hash值
 7 * @param k   要插入键值对的 key
 8 * @param v   要插入键值对的 value
 9 * @return 指定 key 所匹配到的节点对象，针对这个对象去修改 V (返回空说明创建了一个新节点)
10 */
11final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) {
12    Class<?> kc = null;
13    boolean searched = false;
14
15    // 如果当前节点的父节点不为空，则寻找根节点，否则就以当前节点作为根节点
16    TreeNode<K, V> root = (parent != null) ? root() : this;
17    // 遍历当前节点所在的树形结构
18    for (TreeNode<K, V> p = root;;) {
19        int dir, ph; K pk;
20        // 如果当前节点的哈希值 ph 大于待插入节点的哈希值 h，说明 p 在 h 的右边
21        if ((ph = p.hash) > h) {
22            dir = -1;
23        }
24        // 否则，如果当前节点的哈希值 ph 小于待插入节点的哈希值 h，说明 p 在 h 的左边
25        else if (ph < h) {
26            dir = 1;
27        }
28        // 否则，如果当前节点的哈希值等于带插入节点的哈希值，并且当前节点的 key 和带插入节点的 key 相等，
29        // 则说明要放进去 key 在当前树中已经存在了
30        else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
31            return p;
32        }
33        // 否则，哈希值相等但是 key 值不相等同时 key 的类型都没有实现 Comparable 接口
34        else if ((kc == null && (kc = comparableClassFor(k)) == null)
35                || (dir = compareComparables(kc, k, pk)) == 0) {
36            // 还没找到节点
37            if (!searched) {
38                TreeNode<K, V> q, ch;
39                searched = true;
40                if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null)
41                        || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) {
42                    return q;
43                }
44            }
45            // 如果左右节点均无法找到，而 key 的类名相等，则通过 key 的哈希进行比较
46            dir = tieBreakOrder(k, pk);
47        }
48
49        TreeNode<K, V> xp = p;
50        // 根据上一步骤比较的结果进行判断，p 等于其左子节点还是右子节点，并且其子节点为空，则进行插入
51        if ((p = (dir <= 0) ? p.left : p.right) == null) {
52            // 获取 p 节点的下一个节点
53            Node<K, V> xpn = xp.next;
54            // 新建节点
55            TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
56            // 将新建的节点和 p 节点相连
57            if (dir <= 0) {
58                xp.left = x;
59            } else {
60                xp.right = x;
61            }
62            xp.next = x;
63            x.parent = x.prev = xp;
64            if (xpn != null) {
65                ((TreeNode<K, V>) xpn).prev = x;
66            }
67            // 将新节点插入到红黑树中
68            // 在将节点插入到链表节点以后，调整节点数组的结构，将数组放到节点数组的最前面
69            moveRootToFront(tab, balanceInsertion(root, x));
70            return null;
71        }
72    }
73}

 1/**
 2 * 对哈希表进行初始化或者扩容
 3 *
 4 * @return table
 5 */
 6final Node<K,V>[] resize() {
 7    Node<K,V>[] oldTab = table;                        // 现有 table 变量
 8    int oldCap = (oldTab == null) ? 0 : oldTab.length; // 现有 table 的容量 (现有容量)
 9    int oldThr = threshold;                            // 现有 table 阈值   (现有阈值)
10    int newCap;                                        // 扩容后 table 容量 (新容量)
11    int newThr = 0;                                    // 扩容后 table 阈值 (新阈值)
12
13    // 如果现有容量 (oldCap) 大于 0，则说明现有 table 不为空，需要重新计算现有阈值 (threshold) 和新阈值 (newThr) 大小
14    if (oldCap > 0) {
15        // 若现有容量 (oldCap) 大于集合所允许的最大容量 (2^30)，则置扩容临界值 threshold=Integer.MAX_VALUE
16        if (oldCap >= MAXIMUM_CAPACITY) {
17            threshold = Integer.MAX_VALUE;
18            return oldTab;
19        }
20        // 将现有容量 (oldTab) 扩大 2 倍，若现有容量 (oldTab) 扩容后，小于集合所允许的最大容量 (2^30)，
21        // 且大于默认的初始容量 (16)，则将现有阈值 (oldThr) 扩大一倍得到一个新的阈值 (newThr)
22        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
23            newThr = oldThr << 1;
24        }
25    }
26    // 如果现有容量 oldCap ≤ 0，但是现有阈值 oldThr > 0，则将新容量等于现有阈值 newCap = oldThr;
27    else if (oldThr > 0) {
28        newCap = oldThr;
29    }
30    // 如果现有容量 oldCap ≤ 0 和现有阈值 oldThr ≤ 0，则:
31    // - ① 将新容量设置为默认容量 16
32    // - ② 将新阈值为默认容量 * 默认负载因子 0.75
33    else {
34        newCap = DEFAULT_INITIAL_CAPACITY;
35        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
36    }
37
38    // 如果新阈值为 0，说明新阈值未赋值，则:
39    // - ① 通过新容量 * 负载因子，即 newCap * loadFactor 计算新的阈值
40    // - ② 判断新容量 newCap 和第①步计算的阈值 ft 是否都小于最大集合容量，是则设置新阈值为 ft，否则为 Integer.MAX_VALUE
41    if (newThr == 0) {
42        float ft = (float) newCap * loadFactor;
43        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
44    }
45
46    // 设置现有阈值等于新阈值
47    threshold = newThr;
48    // 创建新的 table
49    @SuppressWarnings({"rawtypes", "unchecked"}) // 忽略检查，如 sonar 扫描检查等
50    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
51    table = newTab;
52    // 如果现有 table 不为 null，则需要进行循环遍历，将现有 table 中的元素转移到新 table 中
53    if (oldTab != null) {
54        for (int j = 0; j < oldCap; ++j) {
55            Node<K,V> e;
56            if ((e = oldTab[j]) != null) {
57                oldTab[j] = null;
58                if (e.next == null) {
59                    newTab[e.hash & (newCap - 1)] = e;
60                } else if (e instanceof TreeNode) {
61                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
62                } else { // preserve order
63                    Node<K,V> loHead = null, loTail = null;
64                    Node<K,V> hiHead = null, hiTail = null;
65                    Node<K,V> next;
66                    do {
67                        next = e.next;
68                        if ((e.hash & oldCap) == 0) {
69                            if (loTail == null) {
70                                loHead = e;
71                            } else {
72                                loTail.next = e;
73                            }
74                            loTail = e;
75                        }
76                        else {
77                            if (hiTail == null) {
78                                hiHead = e;
79                            } else {
80                                hiTail.next = e;
81                            }
82                            hiTail = e;
83                        }
84                    } while ((e = next) != null);
85                    if (loTail != null) {
86                        loTail.next = null;
87                        newTab[j] = loHead;
88                    }
89                    if (hiTail != null) {
90                        hiTail.next = null;
91                        newTab[j + oldCap] = hiHead;
92                    }
93                }
94            }
95        }
96    }
97    return newTab;
98}

 1/**
 2 * 从集合中删除指定 key 对应的键值对数据
 3 *
 4 * @param key key 要删除数据的 key
 5 * @return 判断集合中存在指定的 key 对应的键值对数据，不存在则返回 null，存在则返回键值对的 value
 6 */
 7public V remove(Object key) {
 8    Node<K,V> e;
 9    return (e = removeNode(hash(key), key, null, false, true)) == null ?
10            null : e.value;
11}

 1/**
 2 * 删除集合中指定的键值对数据
 3 *
 4 * @param hash  key 的 hash 值
 5 * @param key   要删除数据的 key
 6 * @param value 要删除数据的 value (该值是否作为删除的条件取决于参数 matchValue 是否为 true)
 7 * @param matchValue 删除数据时是否需要验证传入的 value 是否和查找到的 value 相等，true 则验证，false 则不验证
 8 * @param movable 删除后是否移动节点，true 则移动，false 则不移动
 9 * @return 返回被删除的节点对象，如果没有删除任何节点则返回 null
10 */
11final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
12    Node<K,V>[] tab; // 节点数组
13    Node<K,V> p;     // 当前节点
14    int n;           // 数组长度
15    int index;       // 数组索引
16
17    // 获取数组 table 不为空，则使用【传入哈希值】与【数组长度】进行位运算，得出 key 在数组的下标位置，如果该数组
18    // 下标位置不为空，则执行下面的删除逻辑。
19    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
20        Node<K,V> node = null; // 记录返回节点对象
21        Node<K,V> e;           // 记录临时节点变量
22        K k;                   // 记录节点 key 的变量
23        V v;                   // 记录节点 value 的变量
24
25        // 判断数组当前位置节点的 hash 和 key 是否和要删除键值对的 hash 和 key 相同，如果是则将当前阶段赋给变量 node
26        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
27            node = p;
28        }
29        // 如果当前数组当前位置节点不是要删除的节点，则继续判断是否存在下一个节点，如果存在则继续遍历红黑树/链表
30        // 寻找要删除的节点。
31        else if ((e = p.next) != null) {
32            // 判断下一个节点是否为树节点，是则遍历红黑树寻找要删除的节点，并将其赋给变量 node
33            if (p instanceof TreeNode) {
34                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
35            }
36            // 如果下一个节点不是树节点，则说明是链表，继续遍历链表寻找要删除的节点，并将其赋给变量 node
37            else {
38                do {
39                    // 判断链表中的当前节点是否为要删除的节点，如果是则赋给变量 node
40                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
41                        node = e;
42                        break;
43                    }
44                    p = e;
45                } while ((e = e.next) != null);
46            }
47        }
48        
49        // 如果寻找到的要删除的节点 node 不为空，需要继续验证是否设置 matchValue 为 true，如果为是则还需要继续验证节点
50        // 的 value，如果条件都符合，则执行下面逻辑。
51        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
52            // 如果节点属于红黑树，则从红黑树中删除
53            if (node instanceof TreeNode) {
54                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
55            }
56            // 如果是链表，并且要删除的节点为链表的头节点，则直接将数组下标位置直接指向要删除节点的下一个节点，这样就
57            // 相当于进行了删除操作。
58            else if (node == p) {
59                tab[index] = node.next;
60            }
61            // 如果是链表，且要删除的节点不是链表的头节点，则让要删除节点的前一个阶段的 next 属性，指向要删除节点的
62            // 下一个节点，这样就相当于进行了删除操作
63            else {
64                p.next = node.next;
65            }
66            // 使 modCount 值加 1，用于记录 HashMap 的数据结构发生了变化
67            ++modCount;
68            // 使集合大小 size 减 1
69            --size;
70            // 调用 afterNodeRemoval 方法，该方法 HashMap 没有任何实现逻辑，目的是为了让子类根据需要自行覆写
71            afterNodeRemoval(node);
72            return node;
73        }
74    }
75    return null;
76}

1/**
2 * 查找指定 Key 的值，如果未找到则返回 null
3 *
4 * @see #put(Object, Object)
5 */
6public V get(Object key) {
7    Node<K,V> e;
8    return (e = getNode(hash(key), key)) == null ? null : e.value;
9}

1/**
2 * 判断当前 HashMap 集合中是否包含指定的 Key
3 *
4 * @param key 指定的键
5 * @return 当前 HashMap 集合是否包含指定 Key 的结果，存在则返回 true，否则返回 false
6 */
7public boolean containsKey(Object key) {
8    return getNode(hash(key), key) != null;
9}

 1/**
 2 * 在集合中查找指定 key 节点 (实现 Map.get() 和相关方法)
 3 *
 4 * @param hash 键 key 的哈希值
 5 * @param key  要查找的 key
 6 * @return 寻找到的键值对节点，如果为寻找到则返回 null
 7 */
 8final Node<K, V> getNode(int hash, Object key) {
 9    Node<K,V>[] tab; // 记录数组 table 的变量
10    Node<K,V> first; // 记录数组指定位置的 Node 节点的变量
11    Node<K,V> e;     // 记录临时 Node 节点的变量
12    int n;           // 记录 table 数组长度的变量
13    K k;             // 记录数组指定位置的 Node 节点的键值对 key
14
15    // 判断数组 table 是否不为空，如果是则使用 key 的哈希值进行位运算，得出 key 在数组 table 中的下标位置，并且赋给变量 first
16    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
17        // 始终每次都先判断第一个 Node 节点是否就是要查找的 key 的节点
18        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) {
19            return first;
20        }
21        // 如果第一个 Node 节点不是要查找的 key 的节点，则继续判断下一个节点是否为空
22        if ((e = first.next) != null) {
23            // 判断是否为红黑树 TreeNode 类型节点，如果是则说明关联的节点为红黑树，则遍历红黑树获取查找 key 节点
24            if (first instanceof TreeNode) {
25                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
26            }
27            // 如果不为红黑树 TreeNode 类型节点，则说明关联的节点为链表，则遍历链表查找 key 节点
28            do {
29                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
30                    return e;
31                }
32            } while ((e = e.next) != null);
33        }
34    }
35    // 如果数组 table 为空，或者遍历红黑树和链表后都没有找到 key 节点，则返回 null
36    return null;
37}

 1/**
 2 * 链表转换为红黑树 (将当前桶下的链表中的 Node 节点类型转化为 TreeNode 节点类型)
 3 *
 4 * @param tab  集合数组 table
 5 * @param hash 键值对 key 的哈希值
 6 */
 7final void treeifyBin(Node<K,V>[] tab, int hash) {
 8    int n;       // 记录数组长度的变量
 9    int index;   // 记录索引的变量
10    Node<K,V> e; // 记录临时 Node 节点的变量
11
12    // 如果前桶下的链表为 null，或者数组 table 长度小于链表转化为红黑树时对集合最小容量的限制值 64，则链表不转换为红黑树，
13    // 只对现有集合 table 进行一次扩容操作
14    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
15        resize();
16    }
17    // 如果前桶下的链表和链表中的最后元素不为 null，并且当前桶下的链表长度 ≥ 链表转化为红黑树时对集合最小容量的限制值，
18    // 则将链表转换为红黑树
19    else if ((e = tab[index = (n - 1) & hash]) != null) {
20        // 将链表 Node 节点 e 转化 TreeNode 树节点 p，然后构建由 TreeNode 组成的双向链表
21        TreeNode<K,V> hd = null; // 头结点
22        TreeNode<K,V> tl = null; // 尾节点
23        do {
24            TreeNode<K,V> p = replacementTreeNode(e, null);
25            if (tl == null) {
26                hd = p;
27            }
28            else {
29                p.prev = tl;
30                tl.next = p;
31            }
32            tl = p;
33        } while ((e = e.next) != null);
34        
35        // 将由 TreeNode 组成的双向链表进行数化，转换为红黑树
36        if ((tab[index] = hd) != null) {
37            // 转换为红黑树的方法实现
38            // 这个方法里就开始做各种比较，左旋右旋，然后把双向链表搞成一个红黑树
39            hd.treeify(tab);
40        }
41    }
42}

 1/**
 2 * 取消树化，将红黑树转换为链表
 3 *
 4 * @param map Map集合,这里将 Map 集合传入进来是为了调用类中的 replacementNode() 方法，来构建 Node 节点进而生成链表
 5 * @return 链表的头结点
 6 */
 7final Node<K,V> untreeify(HashMap<K,V> map) {
 8    Node<K,V> hd = null;  // 链表头节点
 9    Node<K,V> tl = null;  // 链表尾节点
10
11    // 遍历 TreeNode 节点
12    for (Node<K,V> q = this; q != null; q = q.next) {
13        // 将 TreeNode 节点转换为普通的 Node 节点
14        Node<K,V> p = map.replacementNode(q, null);
15        // 如果为遍历的第一次，则保存头结点其引用
16        if (tl == null) {
17            hd = p;
18        }
19        // 将上一个节点的下一个节点指向当前这个节点
20        else {
21            tl.next = p;
22        }
23        // 将 tl 节点指向 p
24        tl = p;
25    }
26
27    // 返回链表的头结点
28    return hd;
29}

1public class HashMapThreadSafe {
2
3    public static void main(String[] args) {
4        // 创建 HashMap，然后使用 Collections.synchronizedMap 包装 HashMap
5        Map<String, String> safeMap = Collections.synchronizedMap(new HashMap());
6    }
7
8}

1public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
2    return new SynchronizedMap<>(m);
3}

 1public int size() {
 2    synchronized (mutex) {return m.size();}
 3}
 4
 5public boolean isEmpty() {
 6    synchronized (mutex) {return m.isEmpty();}
 7}
 8
 9public boolean containsKey(Object key) {
10    synchronized (mutex) {return m.containsKey(key);}
11}
12
13public boolean containsValue(Object value) {
14    synchronized (mutex) {return m.containsValue(value);}
15}
16
17public V get(Object key) {
18    synchronized (mutex) {return m.get(key);}
19}
20
21public V put(K key, V value) {
22    synchronized (mutex) {return m.put(key, value);}
23}
24
25public V remove(Object key) {
26    synchronized (mutex) {return m.remove(key);}
27}
28
29public void putAll(Map<? extends K, ? extends V> map) {
30    synchronized (mutex) {m.putAll(map);}
31}
32
33public void clear() {
34    synchronized (mutex) {m.clear();}
35}

1public class HashMapThreadSafe2 {
2
3    public static void main(String[] args) {
4        // 创建 Hashtable 线程安全集合
5        Map<String, String> safeMap = new Hashtable<>();
6    }
7
8}

1public class HashMapThreadSafe3 {
2
3    public static void main(String[] args) {
4        // 创建 ConcurrentHashMap 线程安全集合
5        Map<String, String> safeMap = new ConcurrentHashMap<>();
6    }
7
8}