说说 Java 中 HashMap 的原理？

大家好，欢迎来到IT知识分享网。

在日常开发中，HashMap 算得上是 Java 程序员最常打交道的集合之一。它使用灵活、查询高效，堪称数据存储和检索的“一把好手”。那么它究竟是怎么做到快速存取、又是如何避免不同键（Key）互相“打架”的呢？今天咱们就从底层原理上，聊聊 HashMap 让人又爱又恨的那些“门道”。

一、HashMap的身世：存储 + 哈希的巧妙结合

最初的 HashMap 是基于数组 + 链表来实现的。可以想象一个“带格子的抽屉”，每个格子代表数组中的一个桶（bucket）。当我们往 HashMap 里存入 <Key, Value> 键值对时，底层会先计算 Key 的哈希值（hashCode），然后根据哈希值找到对应的桶位置。如果该桶还没有别的数据，直接将这对键值存进去即可；如果已经有了别的键值，那么就把后来的键值以链表方式“串”在后面。

不过从 Java 8 开始，如果同一个桶中的链表长度超过一定阈值（默认为 8），就会把链表转换成红黑树（Red-Black Tree），以减少最坏情况下链表过长导致的性能损失。红黑树的查询、插入在平均情况下都是 O(log⁡n)O(logn)，而链表的最坏情况需要 O(n)O(n)，这样就能让查询效率更有保障。

二、哈希函数与哈希值：为什么能定位到桶里？

当我们说到哈希（Hash），可能有点抽象。其实简言之，哈希函数就是把任意长度的输入映射到固定长度输出的函数。对 HashMap 而言，其核心在于：给定一个键（Key），我们通过它的 hashCode() 方法获取原始哈希值，然后在底层中进一步混合、扰动等操作，把这个值分散到数组的各个桶里。

在 Java 里，HashMap 的默认扰动函数会做几步位运算，让高位和低位的信息掺和在一起，尽量避免高位“闲置”，从而让数据分布更均匀。一个大目标就是尽量减少哈希碰撞（即不同的键映射到同一个桶上），但完全避免碰撞几乎是不可能的，所以还需要后面提到的链表或红黑树来处理。

三、为何要链表或红黑树？

在理想情况下，每次计算哈希值都能把键均匀地打散到不同的桶里，完美无碰撞。可在实际应用中，总会有不同的键得到相同的哈希值，一起挤到同一个桶里，这就叫做哈希碰撞。

• 链表：如果一个桶里出现多个键值对，就把它们用链表方式连接起来。链表越长，查询就越慢，最坏情况下需要遍历整个链表。
• 红黑树：当链表过长时，会把链表替换成红黑树。红黑树的最坏查询复杂度是 O(log⁡n)O(logn)，相对而言高效得多。

这样做的用意就是：一旦发现碰撞严重，能及时退而求其次，用树形结构替代线性结构，从而把极端情况下的性能劣势降到最低。

四、初始容量和负载因子：为什么要扩容？

如果 HashMap 只有 16 个桶，而你却往里塞了 100 个键，那这 100 个键很大可能会被聚集在某几个桶里，引起长链表或红黑树，效率自然不理想。为此，HashMap 定义了负载因子（Load Factor） ，它的默认值是 0.75，表示当实际元素数达到了容量（桶数） * 0.75 时，就会触发扩容（rehash）。

扩容的过程包括：

1. 分配一个更大的数组（通常是原来容量的 2 倍）。
2. 把旧数组中的元素重新计算位置，放到新的数组里。

扩容虽然能缓解碰撞，但在大规模数据的场景下，这一步的“代价”可不小。所以一般要结合业务场景，合理设置初始容量和负载因子，尽量减少扩容操作带来的性能开销。

五、HashMap的常见操作：增删改查

1. 插入（put）
2. 先计算 Key 的哈希值，定位到对应的桶。
3. 若桶为空，直接放入；若桶有元素，则继续往链表或树里插入。
4. 若发现要插入的键已经存在，就更新对应的值。
5. 查询（get）
6. 同样基于 Key 的哈希值来定位桶，然后在桶里的链表或树中找到对应的键值对，取出 Value。
7. 删除（remove）
8. 先确定哈希值对应的桶，若找到对应键则删除，链表或红黑树会做相应的调整；没有则返回 null。
9. 扩容（resize）
10. 当元素数量超过负载因子 * 当前容量时，会把原有的键值对分散到一个更大的数组里进行存储。

六、常见问题：为什么会出现死循环或数据丢失？

在多线程环境下，若多个线程同时对同一个 HashMap 做插入、扩容等操作，却没有适当的同步措施（例如没有使用
Collections.synchronizedMap 或者 ConcurrentHashMap），就可能造成数据丢失、死循环等让人“头大”的情况。
这是因为多个线程会同时修改数组和链表结构，产生竞态条件，进而破坏底层数据结构的完整性。因此，HashMap 绝非线程安全，需要并发环境下的同学谨慎使用。

七、总结：HashMap的妙处与注意事项

1. 高效的存储和检索
2. 通过“哈希分桶”实现近似 O(1)O(1) 的平均插入和查询效率。
3. Java 8 后期引入红黑树，减少了碰撞严重时的性能衰减。
4. 需要平衡的参数
5. 不要过度依赖默认配置，如果数据量很大且能预估规模，最好在创建 HashMap 时指定合适的初始容量，避免频繁扩容造成的性能浪费。
6. 多线程的警告
7. 在高并发场景中，使用 HashMap 存在风险，务必要采用线程安全的方案（ConcurrentHashMap 或其他同步措施）。
8. 合适的哈希码与键
9. 确保 Key 的 hashCode() 与 equals() 方法“匹配”且尽量合理，能有效分散数据，降低碰撞几率。

后记

HashMap 的原理说到底并不神秘，关键在于理解哈希函数如何发挥作用，以及如何在碰撞不可避免的现实里，用链表或红黑树等结构来完成“碰撞管理” 。此外，更要记住它不是线程安全的。在真实开发中，若想把它用得稳准狠，最好结合实际场景优化容量配置，同时在多线程场景里留意并发安全——只有这样，才能把 HashMap 那一套快速存取的“好身手”发挥到淋漓尽致。