Java 中 HashMap 底层哈希表结构怎么实现-java教程-PHP中文网

java hashmap底层是“数组+链表+红黑树”混合结构：node[] table数组初始容量16，扩容为2的幂；哈希计算用扰动函数提升分布均匀性；冲突时链表存储，长度≥8且数组≥64转红黑树；超负载因子0.75触发扩容并重哈希。

java 中 hashmap 底层哈希表结构怎么实现

Java 中 HashMap 的底层哈希表结构，核心是“数组 + 链表 + 红黑树”的混合实现，JDK 8 及以后版本采用该设计，兼顾查询效率与空间利用率。

数组是哈希表的主干结构

HashMap 内部维护一个 Node<k>[] table</k> 数组，每个数组元素是一个桶（bucket），初始容量为 16，扩容时按 2 的幂次增长（如 32、64…）。键值对通过哈希值定位到具体桶：计算 hash(key) & (table.length - 1) 得到下标。这个位运算等价于取模，但更高效，前提是数组长度必须是 2 的幂。

哈希冲突用链表和红黑树解决

当多个键的哈希值映射到同一数组下标时，发生哈希冲突。HashMap 将冲突元素以链表形式挂在该桶上：

java-enterprise

Java企业开发专家，专注于Spring Boot、微服务架构和JVM优化。适用于：Java语言掌握、

下载

新节点头插或尾插（JDK 8 改为尾插，避免多线程扩容死链）
当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树，提升最坏情况查找性能（从 O(n) 降到 O(log n)）
若红黑树节点数 ≤ 6，则退化回链表

哈希值计算做了扰动处理

为降低低位重复导致的聚集，HashMap 对 key 的原始 hashCode 做了高位参与运算的扰动：

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

这使得高 16 位与低 16 位混合，让哈希分布更均匀，尤其在数组较小时能减少碰撞。

扩容机制保证负载均衡

当元素数量超过 threshold = capacity × loadFactor（默认负载因子 0.75）时触发扩容：

新建两倍容量的数组
所有已有节点重新计算桶位置（因数组长度变化，下标可能改变）
链表或红黑树中的节点被拆分到新数组的原位置或原位置 + 旧容量处（利用 2 的幂特性，仅需判断 hash 的某一位）

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南