在Java里HashMap存取数据的基本流程_Java哈希映射原理说明

本篇文章向大家介绍《在Java里HashMap存取数据的基本流程_Java哈希映射原理说明》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

put()先判null键存table[0]，否则扰动hash、位运算算下标，空桶直插，否则遍历链表/树用equals()比key；get()性能取决于哈希分布，最理想O(1)，冲突时链表O(n/2)、红黑树O(log n)；链表≥8且数组≥64才树化，退化阈值为6；null键唯一且固定table[0]，扩容触发rehash，遍历首选entrySet()。

put() 是怎么把键值对塞进数组里的

调用 put(key, value) 时，HashMap 不是直接往数组里一扔就完事。它会先判断 key 是否为 null：如果是，强制存到 table[0] 链表头；否则走标准哈希流程。

• 调用 key.hashCode() 得到原始哈希码
• 经扰动函数处理：(h = key.hashCode()) ^ (h >>> 16)，让高位参与运算，减少低位冲突
• 用位运算算下标：index = (table.length - 1) & hash（要求 table.length 是 2 的幂）
• 若 table[index] 为空，新建 Node 直接放入；否则遍历链表或红黑树，用 equals() 比较 key —— 注意：只在 hash 相同的前提下才触发 equals()

get() 查数据为什么不是 O(1) 就一定快

get(key) 看似一步到位，但实际性能高度依赖哈希分布和冲突处理。它先算出 index，再在对应桶里线性查找（链表）或二分查找（红黑树）。

• 最理想：无冲突 → 直接 table[index] 取值 → 真·O(1)
• 常见情况：链表长度 ≤ 7 → 逐个 equals() 对比 → 平均 O(n/2)，n 是链表长
• 恶化情况：链表转红黑树后仍频繁命中同一桶 → 退化为 O(log n)，但比 O(n) 好
• 致命陷阱：若自定义 key 类没重写 hashCode() 和 equals()，或两者逻辑不一致，get() 可能永远找不到已存的值

为什么链表要升级成红黑树，且阈值是 8

这个设计是空间与时间的权衡结果。JDK 8 引入红黑树，不是为了“更炫”，而是解决极端哈希碰撞下的性能雪崩。

• 链表查找平均 O(n/2)，最坏 O(n)；红黑树稳定在 O(log n)
• 阈值设为 8：基于泊松分布统计，当负载因子 0.75 时，链表长度 ≥ 8 的概率 ≈ 0.00000006，极低 → 升级是小概率事件，不常触发
• 但必须同时满足两个条件才升级：链表长度 ≥ 8 且 table.length ≥ 64；否则先扩容，避免过早树化浪费内存
• 反向操作：当树中节点 ≤ 6 时，自动退化回链表 —— 树结构有额外指针开销，短数据没必要

新手最容易忽略的三个底层细节

很多 bug 不是语法错，而是对 HashMap “信任过头”导致的隐性失效。

• null 键只能有一个，且永远落在 table[0]；但 null 值可以无限多个 —— 如果业务逻辑依赖 “null 值代表未初始化”，得自己加 guard
• 扩容不是静默的：当 size > capacity × loadFactor（默认 0.75），会触发 resize()，重建整个 table 数组并 rehash 所有元素 —— 此刻并发 put() 可能引发死循环（JDK 7）或数据丢失（JDK 8+ 修复但仍有风险）
• 遍历时用 entrySet() 而非 keySet() + get()：后者每次 get() 都重新算 hash、找桶、查链表，性能差一倍以上

真正卡住人的，往往不是“会不会用 put/get”，而是某次线上 get() 返回 null 时，你得立刻判断：是真没这个 key？是 key 的 hashCode() 实现错了？还是刚被另一个线程 resize 中断了？—— 这些都藏在那行看似简单的 map.get("uid") 后面。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~