HashMap 是 Java 中的一个基于哈希表的 Map 实现，它存储键值对并允许快速的插入、删除和访问操作。HashMap 不保证映射的顺序，即元素的顺序可能会在运行时改变。它是非线程安全的，这意味着在单线程环境中它提供了较好的性能，但在多线程环境中需要额外的同步措施来保证线程安全。HashMap 允许使用 null 作为键和值。在 Java 8 及以后的版本中，HashMap 在内部使用链表和红黑树来解决哈希冲突问题，提高了性能和效率。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 'mvcc' 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号 Solomon 肖哥弹架构获取更多精彩内容

历史热点文章

• 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
  

• 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
  

• 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
  

• Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
  

• 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
  

• 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)
  

1、 HashMap

HashMap 是 Java 中的一个关键数据结构，用于存储键值对。

设计思考：

1. 需求场景：

2. 在各种编程任务中，经常需要将键与值关联起来，以实现快速的数据检索。例如，在数据库应用中，需要根据键（如用户名）快速查找用户信息。

3. 适用于需要快速查找、插入和删除键值对的场景，如缓存实现、查找表等。

4. 现有技术局限性：

5. 数组或链表等线性数据结构在查找特定元素时需要遍历整个结构，导致效率低下。

6. 早期的 Hashtable 类虽然提供了键值对的存储，但它是线程安全的，使用 synchronized 方法或块，这限制了并发性能。

7. 技术融合：

8. HashMap 结合了数组和链表的特点，使用哈希表来存储键值对，并通过哈希函数将键映射到数组的特定位置，从而实现快速的查找。

9. 设计理念：

10. HashMap 旨在提供一个高效的键值对存储结构，它允许快速的插入、删除和查找操作，时间复杂度接近 O(1)。

11. 它不保证映射的顺序，而是根据键的哈希码来存储和检索数据。

12. 实现方式：

13. HashMap 内部使用一个数组来存储桶（bucket），每个桶可以包含一个或多个通过链表或红黑树（Java 8 及以后版本）链接的节点（Node）。

14. 当插入一个新的键值对时，HashMap 会根据键的哈希码来确定它应该存储在哪个桶中，如果发生哈希冲突，则会将新的节点添加到链表或红黑树的末尾。

2、数据结构

图说明：

• HashMap：

• 表示 HashMap 类的实例，是一个基于哈希表的 Map 实现。

• 数组（桶数组） ：

• HashMap 使用一个数组来存储桶（Buckets）。

• 桶：

• 每个桶可以包含多个节点（Node），这些节点存储实际的键值对。

• 链表节点（Node） ：

• 节点存储键值对，并且每个节点都有一个 next 引用，指向同一桶中的下一个节点。

• 红黑树节点（Tree Node） ：

• 当链表长度超过一定阈值时，链表会被转换成红黑树，树节点用于维护具有相同哈希值的节点顺序。

• 键（Key） ：

• 节点中存储的键。

• 值（Value） ：

• 节点中存储的值。

• 下一个节点（Next） ：

• 节点中的引用，指向链表中的下一个节点，用于处理哈希冲突。

• 左子树（Left） ：

• 红黑树节点的左子树引用。

• 右子树（Right） ：

• 红黑树节点的右子树引用。

• 父节点（Parent） ：

• 红黑树节点的父节点引用。

• 负载因子阈值：

• 加载因子阈值，用于决定何时将链表转换为红黑树。

3、 执行流程

图说明：

• 创建 HashMap 实例：初始化 HashMap 对象。

• 插入元素(put) ：执行将键值对插入到 HashMap 的操作。

• 计算键的哈希码：计算插入键的哈希码以确定其在桶数组中的位置。

• 检查是否需要扩容：检查 HashMap 是否需要扩容（即桶数组的大小是否需要增加）。

• 确定桶索引：根据哈希码和桶数组的大小确定桶索引。

• 处理哈希冲突：如果桶中已有元素，则处理哈希冲突，可能是通过链表或红黑树。

• 插入节点：将新节点插入到桶中。

• 查找元素(get) ：执行根据键查找值的操作。

• 遍历桶：遍历桶中的链表或红黑树以查找节点。

• 找到节点：找到包含指定键的节点。

• 返回值：返回找到节点的值。

• 删除元素(remove) ：执行根据键删除键值对的操作。

• 找到节点并删除：找到包含指定键的节点并从桶中删除。

• 更新链表或红黑树：删除节点后，更新链表或红黑树的状态。

4、优点

1. 快速的查找性能：

2. 提供了接近 O(1) 的平均时间复杂度的查找性能。

3. 灵活的键值对存储：

4. 允许使用任意类型的键和值，只要它们正确实现了 equals() 和 hashCode() 方法。

5. 非同步的实现：

6. 不提供内部同步，使得在单线程或可外部同步的情况下性能更优。

5、缺点

1. 线程不安全：

2. HashMap 本身不是线程安全的，需要外部同步来保证线程安全。

3. 对哈希冲突敏感：

4. 在高冲突环境下，链表或红黑树可能会变得较长，影响性能。

5. 不保证顺序：

6. 不保证元素的任何特定顺序，这对于需要有序遍历的场景不适用。

6、使用场景

• 快速查找和存储键值对：

• 适用于需要快速访问和更新数据的场景，如缓存实现。

• 非线程安全环境：

• 在单线程或可以外部同步的环境中，HashMap 提供了高效的键值对存储。

7、类设计

8、应用案例

HashMap 被广泛应用于各种需要快速查找和存储键值对数据的情况。以下是一个具体的应用案例，展示了 HashMap 在学生课程成绩管理系统中的应用：

import java.util.HashMap;
// 学生课程成绩管理类class StudentGradesManagement {    // 使用 HashMap 存储学生的成绩信息，其中键是学生的ID，值是另一个 HashMap    // 内部 HashMap 的键是课程名称，值是对应的成绩    private HashMap<Integer, HashMap<String, Double>> studentGrades;
    public StudentGradesManagement() {        studentGrades = new HashMap<>();    }
    // 添加或更新学生的成绩    public void addOrUpdateGrade(int studentId, String courseName, double grade) {        studentGrades.computeIfAbsent(studentId, k -> new HashMap<>()).put(courseName, grade);    }
    // 获取学生的所有成绩    public HashMap<String, Double> getGrades(int studentId) {        return studentGrades.get(studentId);    }
    // 主方法，用于演示 HashMap 的使用    public static void main(String[] args) {        StudentGradesManagement management = new StudentGradesManagement();
        // 添加学生成绩        management.addOrUpdateGrade(10001, "Math", 85.0);        management.addOrUpdateGrade(10001, "Science", 90.5);        management.addOrUpdateGrade(10002, "Math", 78.0);        management.addOrUpdateGrade(10002, "History", 82.5);
        // 获取并打印学生的成绩        HashMap<String, Double> gradesOfStudent1 = management.getGrades(10001);        System.out.println("Grades of Student 1: " + gradesOfStudent1);
        HashMap<String, Double> gradesOfStudent2 = management.getGrades(10002);        System.out.println("Grades of Student 2: " + gradesOfStudent2);    }}