架构视界
主页
企业架构
  • 方案总览
  • 业财一体
  • 企业中台
  • 组织与绩效
  • 流程治理
数据收集与分析
  • 转型总览
  • 信息化阶段
  • 数字化解决方案
  • 智数化解决方案
  • 智能化解决方案
  • 产品设计
  • 项目管理
全栈软件工程
AI 原生软件工程
方法论
博客
  • 资源导航
  • 效率工具
  • 展示专区
主页
企业架构
  • 方案总览
  • 业财一体
  • 企业中台
  • 组织与绩效
  • 流程治理
数据收集与分析
  • 转型总览
  • 信息化阶段
  • 数字化解决方案
  • 智数化解决方案
  • 智能化解决方案
  • 产品设计
  • 项目管理
全栈软件工程
AI 原生软件工程
方法论
博客
  • 资源导航
  • 效率工具
  • 展示专区
  • 标签索引
  • 2024年

    • 勇闯大A:美债与美元周期
    • 勇闯大A:交易纪律与自我管理
    • 勇闯大A:交易系统分层
    • 勇闯大A:买卖点与止损规则
    • 勇闯大A:债券与资金流向
    • 勇闯大A:微观、宏观与周期
    • Mac 开发环境:新机配置清单
    • 勇闯大A:内外盘与换手率
    • 会计管理:财报阅读与管理报表
    • 会计基础:记账原理与分录
    • 财务入门:财务体系全景
  • 2023年

    • 境外投资:泰国 BOI 申请实务
  • 2022年

    • 企业架构:故障管理与分级响应
    • 企业架构:技术债务的识别、度量与偿还
  • 2021年

    • Python 数据分析:员工分布可视化
    • Python 数据分析:IP 访问折线图
    • Python 数据分析:IP 词云图
    • Redis:RediSearch 全文检索
    • Rust 基础:第一个 CLI 程序
    • Rust 基础:所有权机制
    • Rust 基础:函数与控制流
    • Rust 基础:变量与数据类型
    • Rust 基础:入门与开发环境
    • 企业架构:分布式系统设计
    • 企业架构:编程式权限设计
    • JVM 调优:启动参数与 GC 日志
    • MyBatis 批量插入:三种写法对比
    • 测试:Spring Boot 分层 Mock
    • Redis:布隆过滤器判断元素存在
    • Jenkins:安装配置与应用部署
    • WebClient:非阻塞 HTTP 客户端
    • Drone:Docker 部署轻量 CI
    • Spring AOP:操作审计日志落库
    • Redisson:分布式锁与 RedLock
    • MyBatis 拦截器:雪花算法主键
    • Netty:线程模型与网络编程
    • Redis:SCAN 游标遍历大键空间
    • Jenkins:单机部署与升级脚本
    • Mac:Neo4j 与 Jupyter 安装
    • JavaFX:OpenJDK 11 环境配置
    • Mac:用 jenv 管理 JDK 版本
    • Redis:有序集合实现延时队列
    • Spring Boot 日志:MDC 串联链路
    • 定时任务:Spring 调度与 Cron
    • GoAccess:Nginx 日志分析
    • MyBatis 拦截器:慢 SQL 分析
    • Lucene:倒排索引与中文分词
    • 分布式锁:三种实现方案对比
    • 学习技巧:减少学习排斥心理
    • 动态数据源:多租户数据路由
    • Compose:Spring Boot 三件套
    • Java 阻塞队列:源码与用法
    • Redis:Docker Compose 哨兵
    • Redis:Docker Compose 主从
    • 网络通信:TCP/IP 与 HTTP 基础
  • 2020年

    • 延时队列:DelayQueue 与 Redis 实现
    • MySQL 基础:员工库导入实践
    • 雪花算法:分布式 ID 生成
    • Redis:地理位置查询
    • 抓包:Wireshark 与 Tcpdump
    • SPI:JDK 与 Spring 扩展机制
    • ZooKeeper:概念与集群搭建
    • Spring Boot:集成 JMH 基准测试
    • Wireshark:抓包工具入门
    • Compose:Redis 与 MySQL
    • CentOS 7:Docker 安装部署
    • Netty:源码阅读环境搭建
    • MySQL 基础:SQL 常见用法
    • CentOS 7:Selenium 运行环境
    • Nginx:HTTPS 证书配置
    • JMH:基准测试与 Spring Boot 集成
    • Spring Boot:指定 Tomcat 版本
    • Eureka:实例上下线告警
    • 钉钉告警:应用异常与实例上下线
    • JVM:内存布局、类加载与调优
    • Git:rebase 合并多次提交
    • CentOS 7:OpenResty 部署
  • 2019年

    • Redis CLI:macOS 安装与使用
    • Nginx:访问日志格式
    • 工程规范:可维护代码的写法
    • IntelliJ IDEA:常用插件
    • SkyWalking:源码阅读环境搭建
    • Spring Boot:Redis 超时配置
    • gRPC:ProtoBuf 定义与代码生成
    • Arthas:Java 线上问题诊断
    • Redis:缓存穿透与击穿防护
    • Docker 部署:Elasticsearch
    • Docker 部署:MySQL 5.7 单机
    • Spring Redis:字符串命令封装
    • Docker 部署:ZooKeeper 运行
    • Docker 部署:Redis 单机运行
    • Dubbo:Spring Boot 微服务集成
    • CentOS 7:CMake 源码编译安装
    • 性能度量:吞吐量与 QPS 指标
    • Java 递归:从笔试题到经典问题
    • CentOS 7:ELK 日志平台部署
    • CentOS 7:SonarQube 部署
    • Selenium:Chrome 浏览器自动化
    • JJWT:令牌生成与解析测试
    • Spring 源码:阅读环境搭建
    • JUnit 4:注解、断言与参数化
    • JWT:令牌结构与签名机制
    • FastDFS:架构与文件存取机制
    • XPath:XML 文档节点定位
    • Redis 基础:锁、队列与事务
    • Redis 基础:数据类型与命令
    • MyBatis:Slf4j 日志接入
    • MyBatis:H2 单元测试与 SQL 日志
    • 源码阅读:开源项目环境搭建
    • Git 配置:命令清单与作用域
    • Java 核心:面向对象与基础类型
    • Java 核心:关键字、异常与反射
    • Java 核心:多线程基础
    • Java 核心:同步关键字与线程池
    • Java 核心:锁与并发工具
    • Java 核心:语言基础与并发
    • Dubbo:远程调用与服务治理
    • Java 集合:框架总览与实现对比
    • Maven:生命周期与常用命令
    • MyBatis:执行流程与插件机制
    • Spring:IoC 容器与依赖注入
    • Spring:AOP 与自动装配
    • Spring:事务与启动流程
    • Spring:IoC、AOP 与事务
    • Spring MVC:请求分发与注解
    • MySQL:架构与索引
    • MySQL:事务、锁与 MVCC
    • MySQL:日志与 SQL 优化
    • MySQL:架构、事务与优化
    • Redis 基础:持久化与线程模型
  • 2018年

    • Java HashMap:扩容机制与哈希冲突
    • Java 集合:HashSet 去重原理
    • Java 基础:交换两个变量的值
    • Spring MVC:零 web.xml 改造
    • Mac 开发环境:新机配置清单
    • Log4j:日志分级与按业务拆分
    • Modbus:工业通信协议与 RTU 帧
    • MySQL 基础:子查询与连接查询
    • MySQL 基础:库与表操作
    • MySQL 基础:表操作与查询
    • MySQL 基础:约束、引擎与数据类型
    • MySQL 基础:库表、约束与类型
    • Java 集合:Vector 与 Stack
    • Java 集合:Vector 与 Stack
    • RabbitMQ:CentOS 7 单机部署
    • Redis:CentOS 7 单机部署
    • MongoDB:CentOS 7 单机部署
    • Linux:常用系统与运维命令
    • 注册中心:Eureka 与 ZooKeeper
    • MySQL:CentOS 7 单机部署
    • Git 分支:主分支与临时分支
    • CentOS 7:Java 开发环境部署
    • Java 集合:LinkedList 双向链表
    • Java 集合:ArrayList 动态数组
    • Spring AOP:注解方式实现切面
← 返回博客

Java HashMap:扩容机制与哈希冲突

2018年8月23日 #后端开发 #Java

HashMap 用平均 O(1) 的读写支撑了大多数键值场景,但它的性能并非没有代价:容量必须是 2 的幂,默认负载因子是 0.75,链表长度达到 8 才树化。这些常量彼此约束。本文沿着一次 put 的路径,解释它们如何共同工作,以及哪些用法会让 HashMap 退化。

HashMap 结构示意

结构:数组、链表与红黑树

HashMap 的主体是一个 Node<K, V>[] table 数组,每个数组位置称为一个桶(bucket)。桶内先以单链表保存冲突元素;当冲突足够多时,链表会转换为红黑树。

常量默认值作用
DEFAULT_INITIAL_CAPACITY16(2⁴)未指定容量时的初始桶数
MAXIMUM_CAPACITY2³⁰允许的最大容量
DEFAULT_LOAD_FACTOR0.75扩容阈值 = 容量 × 负载因子
TREEIFY_THRESHOLD8桶内链表达到该长度时尝试树化
UNTREEIFY_THRESHOLD6树节点减少到该数量时退回链表
MIN_TREEIFY_CAPACITY64容量低于该值时优先扩容,而不是树化

默认配置下,第一次 put 会把表初始化为 16 个桶,扩容阈值是 12。也就是说,第 13 个键值对写入时触发扩容。

几个使用层面的结论:

  • 允许一个 null 键和任意数量的 null 值,null 键的哈希值按 0 处理,固定落在 0 号桶。
  • 不保证顺序。迭代顺序既不是插入顺序,也不保证多次运行一致;需要顺序时使用 LinkedHashMap。
  • 不是线程安全的。多线程写场景应使用 ConcurrentHashMap,而不是依赖 Collections.synchronizedMap() 的全表锁。

哈希定位:key 进入哪个桶

JDK 8 没有直接使用 hashCode(),而是先做一次扰动:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

高 16 位与低 16 位异或,让高位信息参与后续的取模运算。数组下标通过位运算得到:

int index = (n - 1) & hash; // n 是容量

容量为 2 的幂时,(n - 1) & hash 等价于 hash % n,但位运算更快;这也解释了为什么 HashMap 始终把容量向上取整到 2 的幂。

键的相等性由 hashCode() 与 equals() 共同决定:

  • 两个键 equals 为 true,hashCode 必须相同;否则会出现“明明相等却存了两份”的错误。
  • 作为键的对象在放入后不应改变参与 hashCode() 计算的字段,否则哈希值变化,get 将找不到原节点。
  • 自定义键需要同时正确重写 hashCode() 和 equals(),只重写其中一个都会导致冲突处理异常。

一次 put 的完整流程

put 的实际工作由 putVal 完成,可以拆成六步:

  1. 表未初始化或长度为 0 时,先调用 resize() 创建底层数组。
  2. 用 (n - 1) & hash 定位桶;桶为空则直接新建节点放入。
  3. 桶首节点的 hash 与 key 都相同,记录该节点,走替换流程。
  4. 首节点是树节点,调用 putTreeVal 在红黑树中查找或插入。
  5. 否则遍历链表:找到相同 key 就记录并替换;到达链尾则追加新节点。追加后链表长度达到 8 时调用 treeifyBin。
  6. 如果是新增键值对,size 加一;超过阈值则扩容。

核心源码如下,注释做了整理:

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. 首次写入或空表:初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 定位桶,空桶直接放入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 与首节点 key 相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 5. 遍历链表:命中则替换,否则追加
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 命中已有 key:按 onlyIfAbsent 决定是否覆盖
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 6. 超过阈值扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

查找路径与之对应:先比较桶首节点,再进入红黑树或遍历链表。平均情况下桶内元素很少,复杂度接近 O(1);最坏情况在树化前是 O(n),树化后降为 O(log n)。

扩容:为什么每次翻倍

默认阈值是 12,写入第 13 个元素时触发 resize()。扩容后的容量是原来的两倍,阈值也随容量同比放大。由于容量始终是 2 的幂,扩容时不需要重新计算每个 key 的完整哈希,只需判断一个额外的高位:

// 原桶中的节点只可能留在 j,或迁移到 j + oldCap
if ((e.hash & oldCap) == 0) {
    // 留在低位链
} else {
    // 迁移到高位链
}

JDK 8 在拆分链表时保留了节点原有的相对顺序,避免旧版本扩容后链表倒置的问题。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
            oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    } else if (oldThr > 0) {
        // 构造时只设置了阈值,首次扩容用它作为容量
        newCap = oldThr;
    } else {
        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;
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    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;
}

扩容是 O(n) 的全量迁移。频繁扩容比查询本身更伤性能,已知数据规模时应当预分配容量:

// 期望存放 expectedSize 个元素,按默认负载因子反推容量
int capacity = (int)(expectedSize / 0.75f) + 1;
Map<String, Object> map = new HashMap<>(capacity);

构造器传入的容量会被 tableSizeFor 向上取整到最近的 2 的幂。传入 10 实际得到 16,传入 17 得到 32。

树化与退化

链表转红黑树需要同时满足两个条件:

  • 单个桶内的链表长度达到 8;
  • 当前表容量不小于 64。

容量不足 64 时,treeifyBin 会先扩容。原因是小表下桶冲突可能只是容量太小,扩容即可分散节点,过早树化反而增加节点体积和维护成本。

树退化为链表的常见时机:

  • 扩容拆分后,某个树桶的节点数降到 6 及以下;
  • 删除节点后树过小,removeTreeNode 触发退化。

负载因子 0.75 下,桶内节点数近似服从泊松分布,长度达到 8 的概率极低,因此 8 是一个兼顾查询性能与内存占用的阈值。本文不展开红黑树的旋转与染色,只讨论它与 HashMap 的交互边界。

常见误区与使用建议

误区一:HashMap 有序。 它不保证顺序,扩容后顺序还可能变化。需要插入顺序用 LinkedHashMap,需要排序用 TreeMap。

误区二:null 键没有风险。 允许 null 键不等于应该使用。业务键使用 null 会掩盖上游数据缺失,也让类型约束失效。

误区三:Collections.synchronizedMap() 等于高并发安全。 它给每个方法加同一把锁,吞吐有限;并发读写应优先 ConcurrentHashMap。

误区四:容量随便写。 频繁写入的场景应按预估规模预分配,减少扩容次数;但也不要盲目设置过大容量,空桶同样占用内存。

误区五:可变对象可以做键。 键对象的字段变化会改变哈希值,导致已存入的映射无法通过 get 找回。键应尽量使用不可变类型。

小结

  • HashMap 是“数组 + 链表 + 红黑树”的组合结构,容量始终为 2 的幂。
  • 哈希定位依赖 (n - 1) & hash,高 16 位扰动用于改善低位分布。
  • put 依次处理初始化、定位、替换、树化与扩容,平均复杂度 O(1)。
  • 扩容按 2 倍进行,桶内节点要么留在原位,要么迁移到 j + oldCap。
  • 线程安全、顺序和可变键是比“时间复杂度”更容易踩的三个坑。
最近更新: 2026/11/20 22:16
Contributors: 庆峰
Prev
Redis 基础:持久化与线程模型
Next
Java 集合:HashSet 去重原理