Java & Android 集合框架

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在实际的业务开发中，往往不需要我们手写数据结构，而是直接使用标准库的数据结构 / 容器类。

本文是 Java & Android 集合框架系列的第 6 篇文章，完整文章目录请移步到文章末尾~

前言

大家好，我是小彭。

在上一篇文章里，我们聊到了 HashMap 的基本原理，这一节我们来结合 HashMap 的源码做分析。

本文源码基于 Java 8 HashMap，并关联分析部分 Java 7 HashMap。

• Java & Android 集合框架 #5 万字 HashMap 详解，基础（优雅）永不过时 —— 原理篇
• Java & Android 集合框架 #6 万字 HashMap 详解，基础（优雅）永不过时 —— 源码篇

---

思维导图：

---

3. HashMap 源码分析

---

3.1 HashMap 的构造方法

HashMap 有 4 个构造方法：

• 1、带初始容量和装载因子的构造方法： 检查初始容量和装载因子的有效性，并计算初始容量最近的 2 的整数幂；
• 2、带初始容量的构造方法： 使用默认负载因子 0.75 调用上一个构造方法；
• 3、无参构造方法： 设置默认装载因子 0.75；
• 4、带 Map 参数的构造方法： 设置默认装载因子 0.75，并逐个添加 Map 中的映射关系。

可以看到，在 HashMap 的构造方法中并没有创建底层数组，而是延迟到 put 操作中触发的 resize 扩容操作中创建数组。另外，在可以已知存储的数据量时，可以在构造器中预先设置初始容量，避免在添加数据的过程中多次触发扩容。

java复制代码// 带初始容量和装载因子的构造方法
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;
    // 扩容阈值（此处不是真正的阈值，仅仅只是将传入的容量转化最近的 2 的整数幂，该阈值后面会重新计算）
    this.threshold = tableSizeFor(initialCapacity);
}

// 带初始容量的构造方法
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR /*0.75*/);
}

// 无参构造方法
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR /*0.75*/;
}

// 带 Map 的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR /*0.75*/;
    // 疑问 7：为什么不使用 Arrays 工具类整体复制，而是使用 putMapEntries 批量添加？
    // 批量添加
    putMapEntries(m, false);
}

// 疑问 8：tableSizeFor() 的函数体解释一下？
// 获取最近的 2 的整数幂
static final int tableSizeFor(int cap) {
    // 先减 1，让 8、16 这种本身就是 2 的整数幂的容量保持不变
    // 在 ArrayDeque 中没有先减 1，所以容量 8 会转为 16
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 /*tableSizeFor() 方法外层已经检查过超过 2^30 的值，应该不存在整型溢出的情况*/
        : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

小朋友总是有太多问号，举手提问🙋🏻‍♀️：

🙋🏻‍♀️疑问 7：为什么带集合的构造方法不使用 Arrays 工具类整体复制，而是使用 putMapEntries 批量添加？

首先，参数 Map 不一定是基于散列表的 Map，所以不能整体复制。其次，就算参数 Map 也是 HashMap，如果两个散列表的 length 长度不同，键值对映射到的数组下标也会不同。因此不能用 Arrays 工具类整体复制，必须逐个再散列到新的散列表中。

🙋🏻‍♀️疑问 8：tableSizeFor() 的函数体解释一下？

其实，HashMap#tableSizeFor() 函数体与 ArrayDeque#calculateSize() 函数体相似，也是求最近的 2 的整数幂，即 nextPow2 问题。区别在于 HashMap 在第一步对参数 cap - 1，而 ArrayDeque 没有这一步，会将 8、16 这种本身就是 2 的整数幂的容量翻倍。

tableSizeFor() 中经过五轮无符号右移和或运算，将 cap 转换为从最高位开始后面都是 1 的数。再执行 +1 运算，就求出了最近的 2 的整数幂（最高有效位是 1，低位都是 0）。

java复制代码n = 0 0 0 0 1 x x x x x     //n
n = 0 0 0 0 1 1 x x x x     //n |= n >>> 1;
n = 0 0 0 0 1 1 1 1 x x     //n |= n >>> 2;
n = 0 0 0 0 1 1 1 1 1 1     //n |= n >>> 4;
n = 0 0 0 0 1 1 1 1 1 1     //n |= n >>> 8;（这一步对 n 没有影响了）
n = 0 0 0 0 1 1 1 1 1 1     //n |= n >>> 16;（这一步对 n 没有影响了）
n = 0 0 0 1 0 0 0 0 0 0     //n + 1（进位，得到最近 2 的整数幂）

3.2 HashMap 的哈希函数

将 HashMap#put 方法中，有一个重要的步骤就是使用 Hash 函数计算键值对中键（Key）的散列值。HashMap#put 的执行流程非常复杂，为了降低理解难度，我们先分析 HashMap#hash 方法。

Hash 函数是散列表的核心特性，Hash 函数是否足够随机，会直接影响散列表的查询性能。在 Java 7 和 Java 8 中，HashMap 会在 Object#hashCode() 的基础上增加 “扰动”：

• Java 7： 做 4 次扰动，通过无符号右移，让散列值的高位与低位做异或；
• Java 8： 做 1 次扰动，通过无符号右移，让高 16 位与低 16 位做异或。在 Java 8 只做一次扰动，是为了在随机性和计算效率之间的权衡。

HashMap#hash

java复制代码public V put(K key, V value) {
    return putVal(hash(key) /*计算散列值*/, key, value, false, true);
}

// Java 7：4 次位运算 + 5次异或运算
static final int hash(int h) {
    h ^= k.hashCode(); 
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
 }

// 疑问 9：为什么 HashMap 要在 Object#hashCode() 上增加扰动，而不是要求 Object#hashCode() 尽可能随机？
// 为什么让高位与低位做异或就可以提高随机性？
// Java 8：1 次位运算 + 1次异或运算
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

小朋友总是有太多问号，举手提问🙋🏻‍♀️：

• 🙋🏻‍♀️疑问 9：为什么 HashMap 要在 Object#hashCode() 上增加扰动，而不是要求 Object#hashCode() 尽可能随机？

这是兜下限，以保证所有使用 HashMap 的开发者都能获得良好的性能。而且，由于数组的长度有限，在将散列值映射到数组下标时，会使用数组的长度做取余运算，最终影响下标位置的只有散列值的低几位元素，会破坏映射的随机性（即散列值随机，但映射到下标后不随机）。

因此，HashMap 会对散列值做位移和异或运算，让高 16 位与低 16 位做异或运算。等于说在低位中加入了高位的特性，让高位的数值也会影响到数组下标的计算。

到这里，基本可以回答上一节剩下的疑问 4：

• 🙋🏻‍♀️疑问 4：为什么 HashMap 要求数组的容量是 2 的整数幂？

这是为了提高散列值映射到数组下标的计算效率和随机性，原因有 3 个：

1、提高取余操作的计算效率：

如果数组的容量是 2 的整数幂，那么就可以将取余运算 |hash % length| 替换为位运算 hash & (length - 1) ，不管被除数是正负结果都是正数。 不仅将取余运算替换为位运算，而且减少了一次取绝对值运算，提高了索引的计算效率。

java复制代码10  % 4 = 2
-10 % 4 = -2      // 负数
10  & (4 - 1) = 2
-10 & (4 - 1) = 2 // 正数

2、数组长度是偶数能避免散列值都映射到偶数下标上：

如果数组的长度是奇数，那么 (length - 1) 的结果一定是偶数，即二进制最低 1 位是 0。这就会导致 hash & (length - 1) 的结果一定是偶数，即始终会映射到偶数下标中，不仅浪费了一般数组空间，也会增大冲突概率。

3、保留所有的低位特征：

数组长度 length 为 2 的整数幂对应 (length - 1) 正好是高位为 0，低位都是 1 的低位掩码，能够让影响映射的因素全部归结到散列值上。

3.3 HashMap 的添加方法

HashMap 直接添加一个键值对，也支持批量添加键值对：

• put： 逐个添加或更新键值对
• putAll： 批量添加或更新键值对

不管是逐个添加还是批量添加，最终都会先通过 hash 函数计算键（Key）的散列值，再通过 putVal 添加或更新键值对。

putValue 的流程非常复杂，我将主要步骤概括为 5 步：

• 1、如果数组为空，则使用扩容函数创建（说明数组的创建时机在首次 put 操作时）；
• 2、(n - 1) & hash：散列值转数组下标，与 Java 7 的 indexFor() 方法相似；
• 3、如果是桶中的第一个节点，则创建并插入 Node 节点；
• 4、如果不是桶中的第一个节点（即发生哈希冲突），需要插入链表或红黑树。在添加到链表的过程中，遍历链表找到 Key 相等（equals）的节点，如果不存在则使用尾插法添加新节点。如果链表节点数超过树化阈值 8，则将链表转为红黑树。
• 5、如果键值对数量大于扩容阈值，则触发扩容。

HashMap#put

java复制代码// 添加或更新键值对
public V put(K key, V value) {
    return putVal(hash(key) /*计算散列值*/, key, value, false, true);
}

// 批量添加或更新键值对
public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

// 批量添加或更新键值对
// evict：是否驱逐最早的节点（在 LinkedHashMap 中使用，我们先忽略）
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) {
            // 如果数组为空，则先初始化 threshold 扩容阈值
            float ft = ((float)s / loadFactor) + 1.0F;
            // 扩容阈值上限
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        } else if (s > threshold)
            // 参数 Map 的长度大于扩容阈值，先扩容（如果扩容后依然不足，在下面的 putVal 中会再次扩容）
            // 这里应该有优化空间，批量添加时可以直接扩容到满足要求的容量，避免在 for 循环中多次扩容
            resize();
        // 逐个添加 Map 中的键值对
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            // hash(key)：计算 Key 的哈希值
            // pubVal：添加或更新键值对
            putVal(hash(key), key, value, false, evict);
        }
    }
}

// 最终都会走到 putVal方法：

// hash：Key 的散列值（经过扰动）
// onlyIfAbsent：如果为 true，不会覆盖旧值
// evict：是否驱逐最早的节点（在 LinkedHashMap 中使用，我们先忽略）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 数组
    Node<K,V>[] tab; 
    // 目标桶（同一个桶中节点的散列值有可能不同）
    Node<K,V> p; 
    // 数组长度
    int n;
    // 桶的位置
    int i;
    // 1. 如果数组为空，则使用扩容函数创建（说明数组的创建时机在首次 put 操作时）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. (n - 1) & hash：散列值转数组下标，与 Java 7 的 indexFor() 方法相似
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 3. 如果是桶中的第一个节点，则创建并插入 Node 节点
        tab[i] = newNode(hash, key, value, null);
    else {
        // 4. 如果不是桶中的第一个节点（即发生哈希冲突），需要插入链表或红黑树
        // e：最终匹配的节点
        Node<K,V> e; 
        // 节点上的 Key
        K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            // 4.1 如果桶的根节点与 Key 相等，则将匹配到根节点
            // p.hash == hash：快捷比较（同一个桶中节点的散列值有可能不同，如果散列值不同，键不可能相同）
            // (k = p.key) == key：快捷比较（同一个对象）
            // key != null && key.equals(k)：判断两个对象 equals 相同
            e = p;
        else if (p instanceof TreeNode)
        // 4.2 如果桶是红黑树结构，则采用红黑树的插入方式
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 4.3 如果桶是链表结构，则采用链表的插入方式：
            // 4.3.1 遍历链表找到 Key 相等的节点
            // 4.3.2 否则使用尾插法添加新节点
            // 4.3.3 链表节点数超过树化阈值，则将链表转为红黑树
            for (int binCount = 0; ; ++binCount) {
                // 尾插法（Java 7 使用头插法）
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 链表节点数超过树化阈值，则将链表转为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到 Key 相等的节点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 4.4 新 Value 替换旧 Value（新增节点时不会走到这个分支）
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 访问节点回（用于 LinkedHashMap，默认为空实现）
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 修改记录
    ++modCount;
    // 5. 如果键值对数量大于扩容阈值，则触发扩容
    if (++size > threshold)
        resize();
    // 新增节点回调（用于 LinkedHashMap，默认为空实现）
    afterNodeInsertion(evict);
    return null;
}

// -> 4.2 如果桶是红黑树结构，则采用红黑树的插入方式
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
    ...
}

// -> 链表节点数超过树化阈值，则将链表转为红黑树
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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 = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

小朋友总是有太多问号，举手提问🙋🏻‍♀️：

• 🙋🏻‍♀️疑问 10：为什么 Java 8 要将头插法改为尾插法？

HashMap 不考虑多线程同步，会存在多线程安全问题。当多个线程同时执行 put 操作并且触发扩容时，Java 7 的头插法会翻转链表的顺序，有可能会引起指针混乱形成环形链表，而 Java 8 使用尾插法，在扩容时会保持链表原本的顺序。

• 🙋🏻‍♀️疑问 11：解释一下 p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))？

这个问题等价于问 HashMap 如何确定键值对的位置：

1、首先，HashMap 会对键 Key 计算 hashCode() 并添加扰动，得到扰动后的散列值 hash。随后通过对数组长度取余映射到数组下标中；

2、然后，当数组下标的桶中存在多个节点时，HashMap 需要遍历桶找到与 Key 相等的节点，以区分是更新还是添加。为了提高效率，就有了 if 语句中的多次判断：

2.1 p.hash == hash 快捷判断： 同一个桶中节点的散列值有可能不同，如果散列值不同，键一定相等：

2.2 (k = p.key) == key 快捷判断：同一个对象；

2.3 key != null && key.equals(k) 最终判断：判断两个键 Key 是否相等，即 equals 相等。

综上所述，HashMap 是通过 hashCode() 定位桶，通过 equals() 确定键值对。

HashMap#put 执行流程

3.4 HashMap 的扩容方法

在 putVal 方法中，如果添加键值对后散列值的长度超过扩容阈值，就会调用 resize() 扩容，主体流程分为 3步：

• 1、计算扩容后的新容量和新扩容阈值；
• 2、创建新数组；
• 3、将旧数组上的键值对再散列到新数组上。

扩容分为 2 种情况：

• 1、首次添加元素： 会根据构造方法中设置的初始容量和装载因子确定新数组的容量和扩容阈值在无参构造方法中，会使用 16 的数组容量和 0.75 的扩容阈值；
• 2、非首次添加： 将底层数组和扩容阈值扩大为原来的 2 倍，如果旧容量大于等于 2^30 次幂，则无法扩容。此时，将扩容阈值调整到整数最大值。

再散列的步骤不好理解，这里解释下：

• 3.1 桶的根节点，直接再散列；
• 3.2 以红黑树的方式再散列，思路与 3.3 链表的方式相似；
• 3.3 以链表的形式再散列：hash & oldCap 就是获取 hash 在扩容后新参与映射的 1 个最高有效位。如果这一位是 0，那么映射后的位置还是在原来的桶中，如果这一位是 1，那么映射后的位置就是原始位置 + 旧数组的容量。

java复制代码oldCap     = 0 0 0 0 1 0 0 0 0 0 // 32
oldCap - 1 = 0 0 0 0 0 1 1 1 1 1 // 32
newCap     = 0 0 0 1 0 0 0 0 0 0 // 64
newCap - 1 = 0 0 0 0 1 1 1 1 1 1 // 64
                     ^
                     增加 1 个有效位参与映射

HashMap#resize

java复制代码// 扩容
final Node<K,V>[] resize() {
    // 旧数组
    Node<K,V>[] oldTab = table;
    // 旧容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧扩容阈值
    int oldThr = threshold;
    // 新容量
    int newCap = 0;
    // 新扩容阈值
    int newThr = 0;
    // 1. 计算扩容后的新容量和新扩容阈值
    // 旧容量大于 0，说明不是第一次添加元素
    if (oldCap > 0) {
        // 如果旧容量大于等于 2^30 次幂，则无法扩容。此时，将扩容阈值调整到整数最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 数组容量和扩容阈值扩大为原来的 2 倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 旧容量为 0，需要初始化数组
    else if (oldThr > 0)
        // （带初始容量和负载因子的构造方法走这里）
        // 使用构造方法中计算的最近 2 的整数幂作为数组容量
        newCap = oldThr;
    else {
        // （无参构造方法走这里）
        // 使用默认 16 长度作为初始容量
        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;
    // 2. 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // 3. 将旧数组上的键值对再散列到新数组上
    if (oldTab != null) {
        // 遍历旧数组上的每个桶
        for (int j = 0; j < oldCap; ++j) {
            // 桶的根节点
            Node<K,V> e;
            // 桶的根节点不为 null
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 3.1 桶的根节点，直接再散列
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 3.2 以红黑树的方式再散列，思路与 3.3 链表的方式相似
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 3.3 以链表的形式再散列
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 3.3.1 若散列值新参与映射的位为 0，那么映射到原始位置上
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 3.3.2 若散列值新参与映射的位为 0，那么映射到原始位置 + 旧数组容量的位置上
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

3.5 HashMap 的获取方法

HashMap 的获取方法相对简单，与 put 方法类似：先通过 hash 函数计算散列值，再通过 hash 取余映射到数组下标的桶中，最后遍历桶中的节点，找到与键（Key）相等（equals）的节点。

HashMap#get

java复制代码// 获取 Key 映射的键值对
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key)/*计算散列值*/, key)) == null ? null : e.value;
}

// 通过 Key 的散列值和 Key 获取映射的键值对
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 先检查根节点
        if (first.hash == hash && ((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);
            // 以链表的方式检索
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

HashMap#get 示意图

3.6 HashMap 的移除方法

HashMap 的移除方法是添加方法的逆运算，HashMap 没有做动态缩容。

HashMap#remove

java复制代码public V remove(Object key) {
    Node<K,V> e;
    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;
    // 定位到散列值对应的数组下标
    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;
        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);
            }
        }
        // node 不为 null，删除 node 节点
        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)
                // 以链表的方式删除（删除跟节点）
                tab[index] = node.next;
            else
                // 以链表的方式删除（删除中间节点）
                p.next = node.next;
            ++modCount;
            --size;
            // 删除节点回调（用于 LinkedHashMap，默认为空实现）
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

HashMap#remove 示意图

3.7 HashMap 的迭代器

Java 的 foreach 是语法糖，本质上也是采用 iterator 的方式。HashMap 提供了 3 个迭代器：

• EntryIterator： 键值对迭代器
• KeyIterator： 键迭代器
• ValueIterator： 值迭代器

在迭代器遍历数组的过程中，有可能出现多个线程并发修改数组的情况，Java 很多容器类的迭代器中都有 fail-fast 机制。如果在迭代的过程中发现 expectedModCount 变化，说明数据被修改，此时就会提前抛出 ConcurrentModificationException 异常（当然也不一定是被其他线程修改）。

其实，这 3 个迭代器都是 HashIterator 的子类，每个子类在 HashIterator#nextNode() 中获取不同的值：

java复制代码final class KeyIterator extends HashIterator implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

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

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

// 非静态内部类
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;
        // 记录底层数组
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            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;
        Node<K,V> e = next;
        // 检查修改记录
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        // TreeNode 也会用 next 指针串联
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }
		...
}

基于这 3 个迭代器，HashMap 的遍历方式就分为 3 种：

java复制代码// 1. 直接遍历节点
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Entry<String, Integer> next = iterator.next();
}

// 2. 遍历 Key，再通过 Key 查询 Value（性能最差，多一次查询）
Iterator<String> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {
    String key = keyIterator.next();
}

// 3. 直接遍历 Value
Iterator<Integer> valueIterator = map.values().iterator();
while (valueIterator.hasNext()) {
    Integer value = valueIterator.next();
}

// foreach 是语法糖
for (Map.Entry<String, Integer> entry : map.entrySet()) {
}
// 编译后：
Iterator var2 = map.entrySet().iterator();
while(var2.hasNext()) {
    Entry<String, Integer> entry = (Entry)var2.next();
}

3.8 HashMap 的序列化过程

HashMap 重写了 JDK 序列化的逻辑，只把 table 数组中有效元素的部分序列化，而不会序列化整个数组。

java复制代码// 序列化过程
private void writeObject(java.io.ObjectOutputStream s) throws IOException {
    int buckets = capacity();
    s.defaultWriteObject();
    // 写入容量
    s.writeInt(buckets);
    // 写入有效元素个数
    s.writeInt(size);
    // 写入有效元素
    internalWriteEntries(s);
}

// 不关心键值对所在的桶，在反序列化会重新映射
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    Node<K,V>[] tab;
    if (size > 0 && (tab = table) != null) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                s.writeObject(e.key);
                s.writeObject(e.value);
            }
        }
    }
}

3.9 HashMap 的 clone() 过程

HashMap 中的 table 数组是引用类型，因此在 clone() 中需要实现深拷贝，否则原对象与克隆对象会相互影响：

java复制代码public Object clone() {
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    // 重置变量
    result.reinitialize();
    // 深拷贝
    result.putMapEntries(this, false);
    return result;
}

4. 总结

---

今天，我们分析了 HashMap 的设计思路和核心源码，内容很多，收获也很多。其中，红黑树的部分我们没有展开讨论，这部分我们留到下一篇文章里讨论。请关注。

---

一道题目：

在网上看到一道题目，问题挺有迷惑性的：

• 准备用 HashMap 存 1w 条数据，在构造时传 1w 容量，在添加时还会触发扩容吗？（答案是不会）
• 准备用 HashMap 存 1k 条数据，在构造时传 1k 容量，在添加时还会触发扩容吗？（答案是会）

这是想考对 HashMap 容量和扩容阈值的理解了。在构造器中传递的 initialCapacity 并不一定是最终的容量，因为 HashMap 会使用 tableSizeFor() 方法计算一个最近的 2 的整数幂，而扩容阈值是在容量的基础上乘以默认的 0.75 装载因子上限。

因此，以上两种情况中，实际的容量和扩容阈值是：

• 1w： 10000 转最近的 2 的整数幂是 16384，再乘以装载因子上限得出扩容阈值为 12288，所以不会触发扩容；
• 1k： 1000 转最近的 2 的整数幂是 1024，再乘以装载因子上限得出扩容阈值为 768，所以会触发扩容；

---

版权声明

本文为稀土掘金技术社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

参考资料

• 数据结构与算法分析 · Java 语言描述（第 5 章 · 散列）—— [美] Mark Allen Weiss 著
• 算法导论（第 11 章 · 散列表）—— [美] Thomas H. Cormen 等 著
• 数据结构与算法之美（第 18~22 讲） —— 王争 著，极客时间 出品
• Java：这是一份详细&全面的HashMap 1.7 源码分析 —— Carson 著
• Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？ —— Carson 著
• 都说 HashMap 是线程不安全的，到底体现在哪儿？ —— developer 著
• 漫画：高并发下的HashMap —— 程序员小灰 著
• 面试官：”准备用HashMap存1w条数据，构造时传10000还会触发扩容吗？” —— 承香墨影 著
• 散列算法 —— Wikipedia
• Poisson Distribution —— Wikipedia

推荐阅读

Java & Android 集合框架系列文章目录（2023/07/08 更新）：

• #1 ArrayList 可以完全替代数组吗？
• #2 说一下 ArrayList 和 LinkedList 的区别？
• #3 CopyOnWriteArrayList 是如何保证线程安全的？
• #4 ArrayDeque：如何用数组实现栈和队列？
• #5 万字 HashMap 详解，基础（优雅）永不过时 —— 原理篇
• #6 万字 HashMap 详解，基础（优雅）永不过时 —— 源码篇
• #7 如何使用 LinkedHashMap 实现 LRU 缓存？
• #8 说一下 WeakHashMap 如何清理无效数据的？
• #9 全网最全的 ThreadLocal 原理详细解析 —— 原理篇
• #10 全网最全的 ThreadLocal 原理详细解析 —— 源码篇

数据结构与算法系列文章：跳转阅读

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有