Java & Android 集合框架

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

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

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

前言

大家好，我是小彭。

在上一篇文章里，我们聊到了散列表的整体设计思想，在后续几篇文章里，我们将以 Java 语言为例，分析标准库中实现的散列表实现，包括 HashMap、ThreadLocalMap、LinkedHashMap 和 ConcurrentHashMap。

今天，我们来讨论 Java 标准库中非常典型的散列表结构，也是 “面试八股文” 的标准题库之一 —— HashMap。

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

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

---

思维导图：

---

1. 回顾散列表工作原理

---

在分析 HashMap 的实现原理之前，我们先来回顾散列表的工作原理。

散列表是基于散列思想实现的 Map 数据结构，将散列思想应用到散列表数据结构时，就是通过 hash 函数提取键（Key）的特征值（散列值），再将键值对映射到固定的数组下标中，利用数组支持随机访问的特性，实现 O(1) 时间的存储和查询操作。

散列表示意图

在从键值对映射到数组下标的过程中，散列表会存在 2 次散列冲突：

• 第 1 次 - hash 函数的散列冲突： 这是一般意义上的散列冲突；
• 第 2 次 - 散列值取余转数组下标： 本质上，将散列值转数组下标也是一次 Hash 算法，也会存在散列冲突。同时，这也说明 HashMap 中同一个桶中节点的散列值不一定是相同的。

事实上，由于散列表是压缩映射，所以我们无法避免散列冲突，只能保证散列表不会因为散列冲突而失去正确性。常用的散列冲突解决方法有 2 类：

• 开放寻址法： 例如 ThreadLocalMap；
• 分离链表法： 例如今天要分析的 HashMap 散列表。

分离链表法（Separate Chaining）的核心思想是： 在出现散列冲突时，将冲突的元素添加到同一个桶（Bucket / Slot）中，桶中的元素会组成一个链表，或者跳表、红黑树等动态数据结构。相比于开放寻址法，链表法是更常用且更稳定的冲突解决方法。

分离链表法示意图

影响散列表性能的关键在于 “散列冲突的发生概率”，冲突概率越低，时间复杂度越接近于 O(1)。 那么，哪些因素会影响冲突概率呢？主要有 3 个：

• 因素 1 - 装载因子： 装载因子 (Load Factor) = 散列表中键值对数目 / 散列表的长度。随着散列表中元素越来越多，空闲位置越来越少，就会导致散列冲突的发生概率越来越大，使得散列表操作的平均时间会越来越大；
• 因素 2 - 采用的冲突解决方法： 开放寻址法的冲突概率天然比分离链表法高，适合于小数据量且装载因子较小的场景；分离链表法对装载因子的容忍度更高，适合于大数据量且大对象（相对于一个指针）的场景；
• 因素 3 - 散列函数设计： 散列算法随机性和高效性也会影响散列表的性能。如果散列值不够随机，即使散列表整体的装载因子不高，也会使得数据聚集在某一个区域或桶内，依然会影响散列表的性能。

---

2. 认识 HashMap 散列表

---

2.1 说一下 HashMap 的底层结构？

HashMap 是基于分离链表法解决散列冲突的动态散列表：

• 在 Java 7 中使用的是 “数组 + 链表”，发生散列冲突的键值对会用头插法添加到单链表中；
• 在 Java 8 中使用的是 “数组 + 链表 + 红黑树”，发生散列冲突的键值对会用尾插法添加到单链表中。如果链表的长度大于 8 时且散列表容量大于 64，会将链表树化为红黑树。在扩容再散列时，如果红黑树的长度低于 6 则会还原为链表；
• HashMap 的数组长度保证是 2 的整数幂，默认的数组容量是 16，默认装载因子上限是 0.75，扩容阈值是 12（16*0.75）；
• 在创建 HashMap 对象时，并不会创建底层数组，这是一种懒初始化机制，直到第一次 put 操作才会通过 resize() 扩容操作初始化数组;
• HashMap 的 Key 和 Value 都支持 null，Key 为 null 的键值对会映射到数组下标为 0 的桶中。

2.2 为什么 HashMap 采用拉链法而不是开放地址法？

我认为 Java 给予 HashMap 的定位是一个相对 “通用” 的散列表容器，它应该在面对各种输入场景中都表现稳定。

开放地址法的散列冲突发生概率天然比分离链表法更高，所以基于开放地址法的散列表不能把装载因子的上限设置得很高。在存储相同的数据量时，开放地址法需要预先申请更大的数组空间，内存利用率也不会高。因此，开放地址法只适合小数据量且装载因子较小的场景。

而分离链表法对于装载因子的容忍度更高，能够适合大数据量且更高的装载因子上限，内存利用率更高。虽然链表节点会多消耗一个指针内存，但在一般的业务场景中可以忽略不计。

我们可以举个反例，在 Java 原生的数据结构中，也存在使用开放地址法的散列表 —— 就是 ThreadlLocal。因为项目中不会大量使用 ThreadLocal 线程局部存储，所以它是一个小规模数据场景，这里使用开放地址法是没问题的。

2.3 为什么 HashMap 在 Java 8 要引入红黑树呢？

因为当散列冲突加剧的时候，在链表中寻找对应元素的时间复杂度是 O(K)，K 是链表长度。在极端情况下，当所有数据都映射到相同链表时，时间复杂度会 “退化” 到 O(n)。

而使用红黑树（近似平衡的二叉搜索树）的话，树形结构的时间复杂度与树的高度有关， 查找复杂度是 O(lgK)，最坏情况下时间复杂度是 O(lgn)，时间复杂度更低。

2.4 为什么 HashMap 使用红黑树而不是平衡二叉树？

这是在查询性能和维护成本上的权衡，红黑树和平衡二叉树的区别在于它们的平衡程度的强弱不同：

平衡二叉树追求的是一种 “完全平衡” 状态：任何结点的左右子树的高度差不会超过 1。优势是树的结点是很平均分配的；

红黑树不追求这种完全平衡状态，而是追求一种 “弱平衡” 状态：整个树最长路径不会超过最短路径的 2 倍。优势是虽然牺牲了一部分查找的性能效率，但是能够换取一部分维持树平衡状态的成本。

2.5 为什么经常使用 String 作为 HashMap 的 Key？

• 1、不可变类 String 可以避免修改后无法定位键值对： 假设 String 是可变类，当我们在 HashMap 中构建起一个以 String 为 Key 的键值对时，此时对 String 进行修改，那么通过修改后的 String 是无法匹配到刚才构建过的键值对的，因为修改后的 hashCode 可能会变化，而不可变类可以规避这个问题。
• 2、String 能够满足 Java 对于 hashCode() 和 equals() 的通用约定： 既两个对象 equals() 相同，则 hashCode() 相同，如果 hashCode() 相同，则 equals() 不一定相同。这个约定是为了避免两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对，引起矛盾。

2.6 HashMap 的多线程程序中会出现什么问题？

• 数据覆盖问题：如果两个线程并发执行 put 操作，并且两个数据的 hash 值冲突，就可能出现数据覆盖（线程 A 判断 hash 值位置为 null，还未写入数据时挂起，此时线程 B 正常插入数据。接着线程 A 获得时间片，由于线程 A 不会重新判断该位置是否为空，就会把刚才线程 B 写入的数据覆盖掉）。事实上，这个未同步数据在任意多线程环境中都会存在这个问题。
• 环形链表问题： 在 HashMap 触发扩容时，并且正好两个线程同时在操作同一个链表时，就可能引起指针混乱，形成环型链条（因为 Java 7 版本采用头插法，在扩容时会翻转链表的顺序，而 Java 8 采用尾插法，再扩容时会保持链表原本的顺序）。

2.7 HashMap 如何实现线程安全？

有 3 种方式：

• 方式 1 - 使用 hashTable 容器类（过时）： hashTable 是线程安全版本的散列表，它会在所有方法上增加 synchronized 关键字，且不支持 null 作为 Key。
• 方法 2 - 使用 Collections.synchronizedMap 包装类： 原理也是在所有方法上增加 synchronized 关键字；
• 方法 3 - 使用 ConcurrentHashMap 容器类： 基于 CAS 无锁 + 分段实现的线程安全散列表；

---

3. HashMap 的属性

---

在分析 HashMap 的执行流程之前，我们先用一个表格整理 HashMap 的属性：

版本	数据结构	节点实现类	属性
Java 7	数组 + 链表	Entry（单链表）	1、table（数组）2、size（尺寸）3、threshold（扩容阈值）4、loadFactor（装载因子上限）5、modCount（修改计数）6、默认数组容量 167、最大数组容量 2^308、默认负载因子 0.75
Java 8	数组 + 链表 + 红黑树	1、Node（单链表）2、TreeNode（红黑树）	9、桶的树化阈值 810、桶的还原阈值 611、最小树化容量阈值 64

HashMap.java

java复制代码public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    // 默认数组容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 疑问 3：为什么最大容量是 2^30 次幂？
    // 疑问 4：为什么 HashMap 要求数组的容量是 2 的整数幂？
    // 数组最大容量：2^30（高位 0100，低位都是 0）
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认负载因子：0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 疑问 5：为什么要设置桶的树化阈值，而不是直接使用数组 + 红黑树？
    // （Java 8 新增）桶的树化阈值：8
    static final int TREEIFY_THRESHOLD = 8;

    // （Java 8 新增）桶的还原阈值：6（在扩容时，当原有的红黑树内数量 <= 6时，则将红黑树还原成链表）
    static final int UNTREEIFY_THRESHOLD = 6;

    // 疑问 6：为什么要在设置桶的树化阈值后，还要设置树化的最小容量？
    // （Java 8 新增）树化的最小容量：64（只有整个散列表的长度满足最小容量要求时才允许链表树化，否则会直接扩容，而不是树化）
    static final int MIN_TREEIFY_CAPACITY = 64;

    // 底层数组（每个元素是一个单链表或红黑树）
    transient Node<K,V>[] table;

    // entrySet() 返回值缓存
    transient Set<Map.Entry<K,V>> entrySet;

    // 有效键值对数量
    transient int size;

    // 扩容阈值（容量 * 装载因子）
    int threshold;		

    // 装载因子上限
    final float loadFactor;

    // 修改计数
    transient int modCount;

    // 链表节点（一个 Node 等于一个键值对）
    static class Node<K,V> implements Map.Entry<K,V> {
        // 哈希值（相同链表上 Key 的哈希值可能相同）
        final int hash;
        // Key（一个散列表上 Key 的 equals() 一定不同）
        final K key;
        // Value（Value 不影响节点位置）
        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 的 hashCode 取 Key 和 Value 的 hashCode
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        // 两个 Node 的 Key 和 Value 都相等，才认为相等
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
		
    // （Java 8 新增）红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        // 父节点
        TreeNode<K,V> parent;
        // 左子节点
        TreeNode<K,V> left;
        // 右子节点
        TreeNode<K,V> right;
        // 删除辅助节点
        TreeNode<K,V> prev;
        // 颜色
        boolean red;

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        // 返回树的根节点
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }
    }
}

LinkedHashMap.java

java复制代码static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

相比于线性表，HashMap 的属性可算是上难度了，HashMap 真卷。不出意外的话又有小朋友出来举手提问了🙋🏻‍♀️：

• 🙋🏻‍♀️疑问 1： 为什么字段不声明 private 关键字？（回答过多少次了，把手给我放下）
• 🙋🏻‍♀️疑问 2： 为什么字段声明 transient 关键字？（回答过多少次了，把手给我放下）
• 🙋🏻‍♀️疑问 3：为什么最大容量是 2^30？

因为 HashMap 要求散列表的数组容量是 2 的整数幂 ，而 int 类型能够表示的最大 2 的整数幂就是 2^30，即高位第 31 位是 1，低位都是 0。

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

这个问题我们下面再回答。

• 🙋🏻‍♀️疑问 5：为什么要设置桶的树化阈值，而不是直接使用数组 + 红黑树？

其实，红黑树是 “兜底” 策略，而不一定是最优策略。

首先，红黑树节点本身的内存消耗是链表节点的 2 倍。其次，红黑树在添加和删除数据时需要维护红黑树的性质，会增加旋转等操作。所以，当桶的节点数很低时，并不能体现出红黑树的优势（类似于 Arrays.sort 在子数组长度小于 47 时用插入排序而不是快速排序）。

再结合散列分析的数据统计，在装载因子上限为 0.75 且平均负载因子为 0.5 HashMap 中，桶长度的出现频率符合泊松分布，大部分的桶分布在 0 ~ 3 的长度上，长度大于 8 的桶的出现频率低于千万分之一。

综上所述，为了避免在小桶中使用红黑树，HashMap 在桶的长度大于等于 8 时才会树化为红黑树。并且在扩容再散列时，如果桶的长度小于等于 6，也会还原为链表。

散列冲突数据统计

bash复制代码# 装载因子上限为 0.75、平均负载因子为 0.5，且散列函数随机性良好时，不同长度桶的出现频率
0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million # 低于千万分之一

• 🙋🏻‍♀️疑问 6：为什么要在设置桶的树化阈值后，还要设置树化的最小容量？

这是为了避免无效的树化。

在散列表的容量较低时，添加数据时很容易会触发扩容。此时，一部分原本已经树化的桶会由于长度下降而退还回链表。因此，红黑树为树化操作设置了最小容量要求：如果链表长度达到树化阈值，但散列表整体的长度未达到最小容量要求，那么就直接扩容，而不是在桶上树化。

---

后续源码分析，见下一篇文章：Java & Android 集合框架 #6 万字 HashMap 详解，基础（优雅）永不过时 —— 源码篇。

---

版权声明

本文为稀土掘金技术社区首发签约文章，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 交流社群~

本文转载自: 掘金

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