HashMap数据存储原理详解

Java中的HashMap通过“数组+链表/红黑树”的动态组合结构高效存储键值对：它利用键的hashCode()预计算哈希值，再通过位运算(n-1)&hash实现快速索引定位；当哈希冲突发生时，先以链表形式解决，而当链表长度≥8且数组容量≥64时自动升级为红黑树，将最坏查找性能从O(n)优化至O(log n)；配合默认初始容量16、负载因子0.75的扩容策略，以及null键的特殊处理和Node节点的精巧封装，HashMap在时间效率与空间开销间取得了卓越平衡——读懂它的底层三要素（Node数组、哈希寻址、冲突演化），就真正掌握了Java高性能哈希表的核心逻辑。

HashMap在Java中通过数组加链表（或红黑树）的组合结构存储数据，核心是哈希表实现：先根据键的hashCode()计算索引位置，再处理哈希冲突。

底层是一个Node数组

HashMap内部维护一个Node[] table数组，每个元素是单向链表的头节点（JDK 8起可能是链表或红黑树）。数组长度总是2的幂次（如16、32、64），便于用位运算快速取模：(n - 1) & hash代替hash % n，提升效率。

• 初始容量默认为16，负载因子默认0.75，当元素个数超过capacity × loadFactor（即12）时触发扩容
• 扩容后数组长度翻倍，并重新计算所有键的存储位置（rehash）

键值对封装成Node节点

每个键值对被包装成Node对象，包含四个字段：hash（预存的哈希值）、key、value、next（指向下一个Node的引用）。这个设计避免重复调用key.hashCode()，也支持链表连接。

• 如果两个键的hashCode()相同且equals()返回true，新值会覆盖旧值
• 如果hashCode()相同但equals()为false，则以链表形式存在同一数组槽位

链表转红黑树的阈值机制

当某个数组位置上的链表长度达到8，且当前数组长度≥64时，该链表会转换为红黑树，目的是优化最坏情况下的查找性能（从O(n)降到O(log n)）。若后续删除导致节点数≤6，则退化回链表。

• 阈值8和64是经过大量测试平衡时间与空间开销的经验值
• 红黑树节点类型为TreeNode，继承自Node，额外包含父、子、颜色等字段

put过程简明步骤

调用put(K key, V value)时，实际执行逻辑如下：

• 若key为null，固定放在数组索引0的位置（null的hash定义为0）
• 计算key的hash值（高位参与运算，减少低位相同导致的碰撞）
• 通过(n-1) & hash定位数组下标
• 遍历该位置的链表/树，用equals()比对key，存在则替换value；否则新增节点
• 插入后检查是否需扩容或树化

基本上就这些。理解Node数组、哈希寻址、冲突处理这三层，就能看懂HashMap怎么存数据了。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《HashMap数据存储原理详解》文章吧，也可关注golang学习网公众号了解相关技术文章。