一、入门：HashMap 是什么（小白也能懂）

1. 核心定义（通俗版）

HashMap 是 Java 中一种键值对（Key-Value） 存储容器，你可以把它想象成一本字典：

• 「Key」= 字典里的 “单词”（唯一，不能重复）；
• 「Value」= 单词对应的 “释义”（可以重复）；
• 查释义时，不用从头翻字典，能直接通过 “单词” 快速找到 “释义”—— 这就是 HashMap 的核心优势：查询效率高。

2. 最基础的使用（上手即用）

先看一段最简单的代码，感受 HashMap 的基本操作：

import java.util.HashMap;

public class HashMapBasic {
    public static void main(String[] args) {
        // 1. 创建 HashMap 对象，指定键是字符串类型，值是整数类型
        HashMap<String, Integer> scoreMap = new HashMap<>();

        // 2. 存数据：put(键, 值)
        scoreMap.put("张三", 90);
        scoreMap.put("李四", 85);
        scoreMap.put("王五", 95);

        // 3. 取数据：get(键) —— 通过“张三”直接拿到90
        int zhangSanScore = scoreMap.get("张三");
        System.out.println("张三的分数：" + zhangSanScore); // 输出：张三的分数：90

        // 4. 替换数据：重复put同一个键，会覆盖值
        scoreMap.put("张三", 92);
        System.out.println("张三修改后的分数：" + scoreMap.get("张三")); // 输出：92

        // 5. 判断是否包含某个键：containsKey
        boolean hasLiSi = scoreMap.containsKey("李四");
        System.out.println("是否有李四的分数：" + hasLiSi); // 输出：true

        // 6. 删除数据：remove(键)
        scoreMap.remove("王五");
        System.out.println("删除王五后是否存在：" + scoreMap.containsKey("王五")); // 输出：false

        // 7. 遍历所有键值对
        for (String name : scoreMap.keySet()) { // keySet() 获取所有键
            Integer score = scoreMap.get(name);
            System.out.println(name + "：" + score);
        }
    }
}

核心特点（入门级）：

• 键（Key）唯一，值（Value）可重复；
• 无序（JDK 1.8 前完全无序，1.8 后基本保持插入顺序，但不保证）；
• 允许键 / 值为 null（但键只能有一个 null）。

二、进阶：HashMap 为什么快（底层原理）

1. 核心结构：数组 + 链表 + 红黑树（JDK 1.8 后）

HashMap 的底层不是单纯的数组或链表，而是组合结构：

• 数组（哈希桶 /table）：核心存储结构，每个数组元素是一个 “桶”；
• 链表（解决哈希冲突）：当多个键的哈希值对应同一个桶时，会以链表形式存在；
• 红黑树（优化查询）：当链表长度超过阈值（默认 8），且数组长度≥64 时，链表会转成红黑树（查询效率从 O (n) 降到 O (logn)）。

2. 核心流程：存数据（put）的底层逻辑

• 调用 put(Key, Value) 时，先计算 Key 的哈希值（通过 hashCode() + 扰动函数）；
• 用哈希值计算数组下标（公式：(数组长度-1) & 哈希值），定位到具体的 “桶”；
• 检查桶是否为空：
  • 空 → 直接把键值对封装成节点存入该桶；
  • 非空 → 检查桶内元素类型（链表 / 红黑树）；
• 如果是链表：
  • 遍历链表，判断是否有相同 Key（哈希值相同 + equals() 返回 true）；
  • 有相同 Key → 替换 Value；
  • 无相同 Key → 把新节点加到链表尾部；
  • 检查链表长度：≥8 且数组长度≥64 → 链表转红黑树；
• 如果是红黑树：
  • 查找红黑树中是否有相同 Key；
  • 有 → 替换 Value；
  • 无 → 把新节点插入红黑树；
• 最后检查元素总数是否达到阈值 → 达到则触发扩容。

关键步骤拆解：

（1）计算哈希值

Java 会先调用 Key 的 hashCode() 方法得到一个整数，再通过 “扰动函数”（JDK 1.8 是 (h = key.hashCode()) ^ (h >>> 16)）优化哈希值，减少哈希冲突。

• 为什么要扰动？把哈希值的高位和低位混合，让下标计算更均匀，减少冲突。

（2）计算数组下标

通过公式 (数组长度 - 1) & 哈希值 得到下标（替代取模，效率更高，因为数组长度是 2 的幂时，& 等价于 %）。

• 核心要求：数组长度必须是 2 的幂（默认初始长度 16），这是 HashMap 的重要设计。

（3）处理哈希冲突

当两个不同的 Key 计算出相同的下标，就会发生 “哈希冲突”：

• JDK 1.7 及以前：链表采用 “头插法”（新增节点插在链表头部，扩容时可能导致死循环）；
• JDK 1.8 及以后：链表采用 “尾插法”（新增节点插在尾部，解决死循环问题），且链表过长会转红黑树。

 （4） 扩容机制（resize）

   HashMap 的数组长度是固定的，当存储的数据量达到 “阈值”（阈值 = 数组长度 × 负载因子，默   认负载因子 0.75），就会触发扩容：

• 扩容规则：数组长度翻倍（16 → 32 → 64...）；
• 扩容过程：重新计算所有键值对的下标，迁移到新数组中（JDK 1.8 优化了迁移逻辑，下标要么不变，要么是原下标 + 原数组长度，减少计算量）；
• 为什么负载因子是 0.75？平衡 “空间” 和 “时间”：太小（如 0.5）会频繁扩容浪费空间，太大（如 1.0）会导致哈希冲突增多，查询变慢。

三、深入：HashMap 的核心问题（面试高频）

1. HashMap 为什么线程不安全？

• 多线程下扩容可能导致链表成环（JDK 1.7）；
• 多线程同时 put 可能导致数据覆盖；
• 遍历过程中修改（如 remove）会抛出 ConcurrentModificationException（快速失败机制）。
• 替代方案：线程安全的 ConcurrentHashMap（比 Hashtable 效率高）。

2. Key 为什么要重写 hashCode () 和 equals ()？

先记住 HashMap 判断「两个 Key 是否相同」的唯一规则（必须同时满足）：

1. 两个 Key 的 hashCode () 返回值必须相等；
2. 两个 Key 的 equals () 返回值必须为 true。

少任何一个，HashMap 都认为是「不同的 Key」。

先懂 hashCode () 和 equals () 的原生作用

• hashCode ()：给对象生成一个「哈希数字标识」，默认是对象的内存地址（每个 new 出来的对象地址不同，hashCode 就不同）；
• equals ()：默认比较两个对象的内存地址（只有同一个对象，equals 才返回 true）。

场景 1：用自定义对象做 Key，不重写的后果（反例）

比如你用 User 对象做 Key，存「用户 - 分数」：

// 自定义 User 类：不重写 hashCode() 和 equals()
class User {
    String name; // 比如名字是“张三”
    public User(String name) { this.name = name; }
}

public class Test {
    public static void main(String[] args) {
        HashMap<User, Integer> map = new HashMap<>();
        // 存：new User("张三") 作为 Key
        map.put(new User("张三"), 90);
        // 取：new User("张三") 作为 Key
        System.out.println(map.get(new User("张三"))); // 输出：null
    }
}

为什么取到 null？

• 存的时候的 Key：new User("张三") → 内存地址 A → hashCode=A 的地址值 → 桶位置 X；
• 取的时候的 Key：new User("张三") → 内存地址 B → hashCode=B 的地址值 → 桶位置 Y；
• HashMap 认为这是两个不同的 Key（hashCode 不同），所以去桶 Y 里找，自然找不到数据。

生活类比：你第一次去超市存包，用身份证 A（new User ("张三")）开了储物柜 X，存了东西；第二次去取，用了身份证 B（另一个 new User ("张三")），系统认为你是另一个人，开了储物柜 Y，自然找不到东西。

场景 2：只重写 hashCode ()，不重写 equals ()（还是错）

修改 User 类，只重写 hashCode ()：

class User {
    String name;
    public User(String name) { this.name = name; }

    // 只重写 hashCode：基于 name 生成，所以两个“张三”的 hashCode 相同
    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

public class Test {
    public static void main(String[] args) {
        HashMap<User, Integer> map = new HashMap<>();
        map.put(new User("张三"), 90);
        System.out.println(map.get(new User("张三"))); // 还是输出：null
    }
}

为什么还是 null？

• 两个 User ("张三") 的 hashCode 相同 → 定位到同一个桶；
• 但 equals () 还是默认比较内存地址 → 返回 false；
• HashMap 认为桶里的 Key 和你要找的 Key 不同，所以返回 null。

生活类比：你两次用身份证 A 和 B（hashCode 相同，都指向储物柜 X），但系统检查身份证的芯片（equals），发现芯片信息不同，还是不让你取东西。

场景 3：正确做法：同时重写 hashCode () 和 equals ()（正例）

class User {
    String name;
    public User(String name) { this.name = name; }

    // 重写 hashCode：基于 name 生成，保证相同 name 的 hashCode 相同
    @Override
    public int hashCode() {
        return name.hashCode();
    }

    // 重写 equals：比较 name，保证相同 name 的 User 认为是同一个 Key
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true; // 同一个对象，直接返回true
        if (obj == null || getClass() != obj.getClass()) return false; // 不是User类型，返回false
        User user = (User) obj;
        return name.equals(user.name); // 比较名字，名字相同就认为是同一个Key
    }
}

public class Test {
    public static void main(String[] args) {
        HashMap<User, Integer> map = new HashMap<>();
        map.put(new User("张三"), 90);
        System.out.println(map.get(new User("张三"))); // 输出：90，正确！
    }
}

核心逻辑：

• hashCode () 保证相同 Key 定位到同一个桶；
• equals () 保证同一个桶里能匹配到真正相同的 Key。

补充概念

1. 哈希值：给 Key 发的 “身份证号”

你可以把哈希值理解成：给每个 Key 生成的唯一（尽量唯一）数字身份证。

• 比如：Key 是 “张三”，通过哈希算法（就像一套固定的编码规则）算出哈希值是 10086；
• Key 是 “李四”，算出哈希值是 10087；
• 核心作用：把 “字符串 / 对象” 这类不好直接定位的 Key，转换成 “数字”，方便后续找位置。

2. 桶：数组里的 “小格子”（就是数组的每个元素）

2.1、先给哈希桶下一个「人话定义」

哈希桶（也叫「桶」），就是 HashMap 底层数组里的每一个单独的位置 / 格子—— 你可以把整个 HashMap 想象成一个「格子柜」，哈希桶就是这个柜子里的「单个小格子」，存放键对值。

2.2、用「超市储物柜」彻底讲懂哈希桶

生活中的超市储物柜	HashMap 里的哈希桶
一整排带编号的储物柜（比如 0-15 号）	HashMap 底层的数组（默认长度 16，对应 0-15 号桶）
单个储物柜（比如 5 号柜）	单个哈希桶（数组下标为 5 的那个元素）
往储物柜里放东西	往哈希桶里存 Key-Value 数据
用取件码找对应的储物柜	用 Key 的哈希值计算对应的桶下标，找到目标桶

关键可视化（你在脑子里画这个图）：

HashMap 底层数组（哈希桶数组）：
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
| 桶0 | 桶1  | 桶2  | 桶3  | 桶4  | 桶5  | 桶6  | 桶7  | 桶8  | 桶9  | 桶10 | 桶11 | 桶12 | 桶13 | 桶14 | 桶15 |
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
  ↑     ↑     ↑     ↑     ↑     ↑
  |     |     |     |     |     |
存数据  空    空    空    空   存数据
（Key1）                     （Key2）

• 这个数组的每个格子就是一个哈希桶；
• 每个桶里可以存数据（Key-Value），也可以是空的；
• HashMap 做的核心事，就是「把数据放到对应的桶里」「从对应的桶里拿数据」。

2.3、哈希桶的核心作用（为什么要有桶）

没有桶的话，你存数据只能像普通数组那样「从头往后排」，找数据要一个个遍历（比如找 Key=“张三”，要从第一个元素查到第 10 个），效率极低。

哈希桶的核心价值：通过「编号定位」替代「遍历查找」

1. 存数据时：给 Key 算一个「桶编号」，直接把数据放进这个编号的桶里（不用排队）；
2. 取数据时：再给 Key 算一次「桶编号」，直接去这个桶里拿数据（不用遍历）；

比如：

• 存 “张三 - 90”：算出来桶编号是 5 → 直接放进桶 5；
• 取 “张三” 的分数：算出来桶编号是 5 → 直接去桶 5 里拿，一步到位。

2.4、哈希桶的「本质」和「特点」

1. 本质：哈希桶就是数组的「单个元素位置」，是 HashMap 存储数据的「最小单元」；
2. 特点：
   • 每个桶都有唯一的「下标编号」（0、1、2...），编号是哈希桶的「身份证」；
   • 桶可以是空的（没存数据），也可以存数据；
   • 桶的数量 = 数组的长度（默认 16，扩容后翻倍成 32、64...）。

3. 链表：解决 “快递柜不够用” 的临时方案

哈希冲突的本质：两个不同的 Key，算出的哈希值对应同一个桶（快递柜）。比如：

• Key “张三”→ 哈希值 10086 → 桶编号 5；
• Key “张三丰”→ 哈希值 20086 → 算出来也进桶编号 5；这就是哈希冲突（两个 Key 抢同一个桶）。

这时链表就派上用场了：你可以把链表想象成 “快递柜里的挂钩”—— 桶 5 里挂第一个挂钩（挂 “张三” 的包裹），再挂第二个挂钩（挂 “张三丰” 的包裹），挂钩之间串成一串，这就是链表。

• 特点：挂的越多（链表越长），找包裹时需要逐个翻挂钩（遍历链表），速度越慢（O (n)）。

4. 红黑树：把 “长挂钩串” 换成 “分类货架”

当链表长度超过 8 个（挂钩挂了 8 个包裹），再找包裹就要翻 8 次，效率太低。红黑树就是把这串挂钩换成 “分类货架”：把 8 个包裹按规则排序，找的时候不用逐个翻，而是 “二分查找”（比如先看中间的，再判断往左 / 右找），速度从翻 8 次降到翻 3 次左右（O (logn)）。