1. HashMap为什么是最常用的集合

适用场景：HashMap是键值对存储的最优解，完美匹配开发工作中的大多数高频数据操作要求。开发中常用来做

  • 接口交互：封装请求 / 响应参数（前后端通用）
  • 本地缓存：临时存热点数据，减少数据库查询
  • 数据转换：List 转 Map，提升处理速度
  • 配置管理：key 对应配置项
  • 统计计数：比如统计单词出现次数、用户访问次数

核心优势：

  • 极致的查询 / 插入 / 删除性能：JDK1.8后，使用数组+链表+红黑树，平均时间复杂度O(1)
  • 方法少，语义清晰：put()、get()、contains()等简单方法即可完成核心逻辑
  • 通用性强，无业务限制：不绑定业务场景，可以用来
    • 做缓存、做临时存储
    • 接口参数封装、返回值封装
    • 去重、统计、映射转换
    • 分布式、单机、后端、前端（JS 对象就是 HashMap）
  • 天然支持扩容：不用关心容量问题，支持自动扩容，避免数组越界、容量不足问题。

2. HashMap的底层结构

HashMap底层结构经历了3次大优化，从简单到高效、解决并发风险、查询慢的问题。

2.1. JDK 1.7

        结构：数组 + 链表

        解决哈希冲突方法：链地址法(头插法，并发有坑)

        存在问题：

         (1) 链表过长 → 查询效率退化到 O (n)

         (2) 多线程扩容会形成环形链表，导致 CPU 100%

         (3) 头插法容易混乱

2.2. JDK 1.8 —— 重大升级

         结构：Node [] 数组 + 单向链表 + 红黑树

         时间复杂度：  正常 O (1)；链表 O (n) ；红黑树 O (logn)。

         优化点：         

           (1) 冲突链表长度 ≥ 8 且数组长度 ≥ 64 → 转为红黑树

                 PS：数组≥64的原因：数组太短，优先扩容，而不是树化，避免浪费性能。

           (2) 红黑树节点 ≤ 6 → 退化为链表

           (3) 链表插入从 头插法 → 尾插法

           (4) 扩容重排逻辑优化，避免环形链表

2.3. JDK 19+ 优化哈希与树化逻辑

        (1) 更智能的树化 / 退化判断

        (2) 哈希计算更均匀

        (3) 性能小幅提升

2.4. HashMap 在1.7和1.8中的区别

        (1) 数据结构：1.7 只有链表；1.8 加了红黑树
        (2) 链表插入：1.7 头插法；1.8 尾插法
        (3) 扩容 rehash：1.7 会重新计算 hash；1.8 用高位判断，更高效
        (4) 哈希算法：1.8 简化了 hash 计算，减少冲突
        (5) 并发风险：1.7 扩容会链表成环；1.8 修复了，但依然线程不安全

2.6. 头插法与尾插法的区别

        (1) 头插法 —— 新元素插入链表头部

                         —— 代码简单

                         —— 链表顺序颠倒， 并发扩容易形成死循环

        (2) 尾插法 —— 新元素插入链表尾部

                         —— 保持原有顺序、不会形成环、线程更安全

                         —— 需要遍历到尾部（JDK1.8 保存了尾节点，几乎无损耗）

        (3) 为什么头插法会形成【环形链表】？

             根本原因：扩容时，链表会逆序 + 多线程并发修改指针

             简化原理：HashMap 扩容时会重新计算哈希，把旧数组的链表迁移到新数组。

            JDK1.7 头插法迁移逻辑：

                a、遍历旧链表 

                b、一个个取下来，重新用头插法插入新数组

                c、结果：链表顺序完全反转

            并发场景下的灾难：线程 1 和 线程 2 同时扩容

                 · 线程 1 处理到一半，挂起

                · 线程 2 完成扩容，链表已经逆序

                · 线程 1 恢复执行，继续头插

                · 指针互相指向对方 → 形成环形链表

              并发的后果：CPU 100% 卡死，服务崩溃因为 get () 查询时会在环里无限循环。

3. HashMap怎么解决hash冲突的问题？

(1) 采用链地址法：相同 hash 值的元素挂在同一个链表上
(2) 1.8 当链表长度 ≥8 且数组长度 ≥64 时，转为红黑树，提高查询效率

4. HashMap JDK1.8的扩容机制？

  • 尾插法

       → 保持链表顺序、不反转 → 不会成环、不会死循环

       → 用 loHead/loTail/hiHead/hiTail 两条链表分别迁移

  • 扩容规则：容量 ×2（始终是 2 的幂）

       → hash & (newCap-1)（求下标）只有两种结果 → 原索引 j  或者  新索引  j + oldCap 

       → (e.hash & oldCap) == 0 （判断是否需要移动位置）JDK1.8 扩容最高效的设计

            等于 0 → 留在原位置

            不等于 0 → 去 j + oldCap 新位置

        → 不用重新全量哈希，性能极高！

  • 链表不反转、红黑树会拆分

       →  链表长度 ≥8 且数组≥64 → 链表转为红黑树

       → 红黑树节点 ≤6 → 退化为链表

5. HashMap为什么要使用红黑树？

  • 链表太长时，查询时间复杂度 O (n)
  • 红黑树查询 O (logn)，大幅提升极端情况下的性能
  • 防止哈希冲突攻击导致服务宕机

6.HashMap JDK1.8相关方法核心代码

6.1 get 方法 —— 查找（不插入、不扩容、不树化）

流程总结

1. 对 key 算 hash

2. 算下标：(n - 1) & hash

3. 如果数组位置为空 → 返回 null

4. 位置不为空：

        — 第一个节点就是 key → 直接返回

        — 是红黑树 → 树查找

        — 是链表 → 遍历链表查找

5. 找不到 → 返回 null

即 ： 算 hash → 算下标 → 头节点匹配？→ 树查找 / 链表遍历 → 返回结果

核心逻辑
  1.  计算下标 ： (n - 1) & hash
  2.  查头节点，匹配直接返回
  3.  是红黑树 ： 走红黑树查找（O (logn)）
  4.  是链表 ： 遍历查找（O (n)）
  5.  都没找到 ： 返回 null
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // 1. 计算数组下标：hash & (tab.length-1)
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 2. 检查第一个节点是不是目标 key
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        // 3. 有后续节点
        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; // 没找到
}

6.2 put 方法 —— 插入（会扩容、会树化、会尾插）

流程总结

1. 对 key 算 hash

2. 算下标 (n-1)&hash

3. 位置空 → 直接放

4. 位置不空：

        —— 是 key 相同 → 覆盖

        —— 是红黑树 → 树插入

        —— 是链表 → 尾插法

5. 链表长度≥8 → 树化

6. 元素数量超阈值 → 2 倍扩容

即： 算 hash → 算下标 → 空位置直接放 → 冲突尾插 → 链表≥8树化 → 超阈值2倍扩容

核心逻辑
  1.  计算数组下标 ： i = (n - 1) & hash
  2.  哈希冲突 ： 尾插法插入链表 p.next = newNode(...)
  3.  链表长度 ≥8 转红黑树 ：  if (binCount >= 7) treeifyBin()
  4.  插入成功后判断是否扩容 ：  if (++size > threshold) resize()
  5.  数组容量不足 ： 2倍扩容 resize()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 1. 如果数组为空，第一次put，初始化数组（resize）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 2. 计算下标：i = (n - 1) & hash
    // 如果当前位置为空，直接新建节点放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    // 3. 当前位置有元素（哈希冲突）
    else {
        Node<K,V> e; K k;

        // 3.1 如果key完全相同，直接覆盖（后面会替换value）
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // 3.2 如果是红黑树，树插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // 3.3 否则是链表，遍历链表
        else {
            for (int binCount = 0; ; binCount++) {
                // 找到链表尾部，插入新节点（尾插法！）
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);

                    // ======================
                    // 【面试必考】链表长度 >=8 树化
                    // ======================
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果链表中找到相同key，退出准备覆盖
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 4. key已存在，覆盖value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    // 修改次数+1
    ++modCount;

    // ======================
    // 【扩容判断】size > 阈值 就扩容
    // ======================
    if (++size > threshold)
        resize();

    afterNodeInsertion(evict);
    return null;
}

6.3 resize 方法（扩容、尾插法迁移数据）

流程总结

1. 计算新容量 = 旧容量 ×2（2倍扩容）

2. 创建新的数组

3. 遍历旧数组的每个位置

4. 单个节点 → 直接重新计算下标放入新数组

5. 红黑树节点 → 拆分迁移

6. 链表节点：

        —— 通过 e.hash & oldCap 分成两条链表

        —— 一条留在原位置

        —— 一条移到 j + oldCap

7. 尾插法保持顺序，不反转、不成环

8. 用新数组替换旧数组

即：2倍扩容 → 新建数组 → 拆分链表 → 尾插保序 → 替换数组

核心逻辑
  • 扩容：newCap = oldCap << 1 → 2 倍扩容
  • 位置判断：e.hash & oldCap → 0 留原位置，非 0 去 j+oldCap
  • 链表迁移：尾插法， 顺序不变，不成环
final Node<K,V>[] resize() {
    // 1. 旧数组信息
    Node<K,V>[] oldTab = table;
    int oldCap = oldTab.length;
    
    // 2. 【核心】新容量 = 旧容量 * 2
    int newCap = oldCap << 1; 
    Node<K,V>[] newTab = new Node[newCap];
    table = newTab;

    // 3. 遍历旧数组迁移数据
    for (int j = 0; j < oldCap; j++) {
        Node<K,V> e = oldTab[j];
        if (e == null) continue;

        // ================================
        // 【最核心：链表迁移 + 尾插法】
        // ================================
        Node<K,V> loHead = null, loTail = null;
        Node<K,V> hiHead = null, hiTail = null;
        Node<K,V> next;

        do {
            next = e.next;
            // 【核心公式】判断扩容后位置
            if ((e.hash & oldCap) == 0) {
                // 尾插法，保持原顺序
                if (loTail == null) loHead = e;
                else loTail.next = e;
                loTail = e;
            } 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;
}

7. HashMap为什么在多线程环境下是线程不安全的？

HashMap线程 不安全的核心原因：无锁+并发冲突。HashMap的设计目标是单线程高性能，所以：

  • 没有加 synchronized 或 Lock 锁
  • 多线程同时写数据时，操作会互相覆盖、打断
  • 底层数组 + 链表 / 红黑树结构，在扩容时最容易出致命问题

线程不安全的典型场景：

  • 数据覆盖：多线程环境下，多个线程同时put数据，且key的哈希值相同
  • 扩容引发死循环：JDK7扩容使用的是头插法，多线程并发易形成环形链表。JDK8使用尾插法，修复了死循环的问题，但仍然线程不安全
  • 数据丢失：多线程同时修改链表 / 红黑树结构时，节点插入、移动被打断，导致部分节点没有被正确挂载，最终明明 put 了数据，却 get 不到
# java # 数据结构 # 开发语言
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

四天蒸发近2000亿，宇树科技股价近乎“腰斩”；苹果举办库克告别派对：9月1日正式卸任CEO；Anthropic两款新Claude模型曝光 | 极客头条

avatar AI编程社区
cover

Claude Code反超GitHub Copilot登顶第一、90%程序员已用上Agent，最新AI编码调查报告来了

avatar AI编程社区
cover

如何用好 Claude Code 写后端代码

avatar AI编程社区