1
Map<String, String> map = new HashMap<>();
2
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
3
while (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
}

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

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

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

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

1
/**
2
 * 默认初始容量。该值必须是 2 的 n 次幂，默认值为 16
3
 */
4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
5

6
/**
7
 * 集合的最大容量。最大不能超过 2^30
8
 */
9
static final int MAXIMUM_CAPACITY = 1 << 30;
10

11
/**
12
 * 默认的负载因子
13
 */
14
static final float DEFAULT_LOAD_FACTOR = 0.75f;
15

16
/**
17
 * 链表转换为红黑树的阈值
18
 */
19
static final int TREEIFY_THRESHOLD = 8;
20

21
/**
22
 * 红黑树还原为链表的阈值
23
 */
24
static final int UNTREEIFY_THRESHOLD = 6;
25

26
/**
27
 * 链表转化为红黑树时对集合容量的限制，如果集合容量小于该值，则链表不会转换为红黑树
28
 */
29
static final int MIN_TREEIFY_CAPACITY = 64;

1
/**
2
 * 存储元素的数组
3
 */
4
transient Node<K,V>[] table;
5

6
/**
7
 * 存放具体元素的集合 (俗称“桶”)
8
 */
9
transient Set<Map.Entry<K,V>> entrySet;
10

11
/**
12
 * 记录当前集合的大小，即记录集合中键值对的数量
13
 */
14
transient int size;
15

16
/**
17
 * 记录集合数据修改次数，用于记录迭代器(Iterator)在遍历过程中集合结构是否发生过变化，如果有则迭代器会快速失败
18
 */
19
transient int modCount;
20

21
/**
22
 * 集合扩容的阈值，当实际大小超过临界值时，会进行扩容
23
 * - ① 如果初始化时给定数组大小的话，通过 tableSizeFor 方法计算，数组大小永远接近于 2 的幂次方
24
 *      比如你给定初始化大小 19，实际上初始化大小为 32，即 2^5
25
 * - ② 如果是通过 resize 方法进行扩容，则阈值大小为: 数组容量 * 负载因子 (capacity * loadFactor)
26
 */
27
int threshold;
28

29
/**
30
 * 集合的负载因子，用于参与阈值计算，控制进行扩容的百分比。
31
 */
32
final float loadFactor;

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

1
/**
2
 * 支持配置初始化容量的构造方法
3
 *
4
 * @param initialCapacity 初始化容量
5
 * @throws IllegalArgumentException 非法参数异常 (如果初始容量为负数或者负载因子为负数，则抛出该异常)
6
 */
7
public 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
 */
8
public 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
 */
9
static 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
 */
7
public 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
 */
7
final 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
 */
4
static 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
 */
10
public 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
 */
11
final 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
 */
11
final 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
 */
6
final 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
 */
7
public 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
 */
11
final 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
 */
6
public 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
 */
7
public 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
 */
8
final 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
 */
7
final 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
 */
7
final 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
}

1
public 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
}

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

1
public int size() {
2
    synchronized (mutex) {return m.size();}
3
}
4

5
public boolean isEmpty() {
6
    synchronized (mutex) {return m.isEmpty();}
7
}
8

9
public boolean containsKey(Object key) {
10
    synchronized (mutex) {return m.containsKey(key);}
11
}
12

13
public boolean containsValue(Object value) {
14
    synchronized (mutex) {return m.containsValue(value);}
15
}
16

17
public V get(Object key) {
18
    synchronized (mutex) {return m.get(key);}
19
}
20

21
public V put(K key, V value) {
22
    synchronized (mutex) {return m.put(key, value);}
23
}
24

25
public V remove(Object key) {
26
    synchronized (mutex) {return m.remove(key);}
27
}
28

29
public void putAll(Map<? extends K, ? extends V> map) {
30
    synchronized (mutex) {m.putAll(map);}
31
}
32

33
public void clear() {
34
    synchronized (mutex) {m.clear();}
35
}

1
public class HashMapThreadSafe2 {
2

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

8
}

1
public class HashMapThreadSafe3 {
2

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

8
}