开篇语

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

  今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

  我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

前言：一场从数组链表到红黑树的"逆袭"之路

嗨，亲爱的码友们～有没有过这种感觉？
  初学HashMap时，总以为它就是个简单的"数组+链表"拼接体；结果工作中一追源码，发现，哇哦，JDK8以后它居然长出了一棵树？！
  是的，你没看错，HashMap在JDK8进行了重大升级，为了解决性能问题，它完成了从简单粗暴的链表，到优雅高效的红黑树的进化！

今天，就让我带你穿越时空，看看JDK7与JDK8时代的HashMap，底层到底发生了哪些翻天覆地的变化！
警告：含大量细节+生动比喻，阅读需小心上瘾！🤣

一、HashMap的基本概念回顾（一分钟速通版）

HashMap是啥？
——简而言之，HashMap是一个基于哈希表实现的键值对存储容器，可以快速通过键找到对应的值。

主要特性：

• 允许存储null键和null值。
• 线程不安全（注意，不是每个集合都帮你操心并发问题的哈！）
• 元素无序（哈希的本质就是无序映射）
• 查询、插入性能理论上是O(1)！（理想情况啊兄弟，碰撞多了就打脸了）

二、JDK7时代的HashMap底层结构

结构：数组 + 链表（简单粗暴派）

• 数组：Entry[] table，存放链表的头结点。
• 链表：解决哈希冲突（拉链法）。

简单示意图

table（数组）
| 索引0 | -> Entry1 -> Entry2 -> ...
| 索引1 | -> null
| 索引2 | -> Entry3
| 索引3 | -> Entry4 -> Entry5
| ...

每个Entry长这样：

static class Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next; // 链表下一个节点
    final int hash;
}

流程小剧场

• 插入数据时，计算键的hashCode()，然后压缩成数组索引（index = hash & (table.length - 1)）。
• 如果该索引位置为空，直接放；
• 如果已经有元素（冲突了！），就形成链表，把新元素插到链表头部。（注意！JDK7是头插法）

三、JDK8时代的HashMap底层结构

——有人说，JDK8对HashMap做了整容级别的大改动，真的吗？
——当然是真的，而且技术含量拉满！

结构：数组 + 链表 + 红黑树（智慧派）

• 数组：Node[] table，注意名字变了，不叫Entry了，叫Node。
• 链表：当哈希冲突不严重时，还是链表存储。
• 红黑树：当单个链表长度超过8（TREEIFY_THRESHOLD）时，链表转为红黑树，提升查询效率！

新版示意图

table（数组）
| 索引0 | -> Node1 -> Node2 -> ...
| 索引1 | -> TreeNode（红黑树）
| 索引2 | -> null
| 索引3 | -> Node3
| ...

每个Node长这样：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

如果链表变成红黑树，节点类型就变为TreeNode，继承自Node。

变身条件（重要！）：

• 链表长度大于等于8（默认值）；
• 当前数组长度至少64（防止一堆小链表浪费变树的代价）。

如果条件满足，链表将treeify成红黑树，从而将最差查找性能从O(n)优化成O(log n)！

四、对比总结：JDK7 vs JDK8，到底改了什么？

	JDK7	JDK8
冲突解决	纯链表	链表+红黑树
节点结构	Entry	Node (及其子类TreeNode)
插入方式	头插法（易形成链表反转）	尾插法（更符合插入顺序）
扩容机制	重哈希+链表倒置	重哈希+保持顺序一致
多线程风险	高（可能形成死链表，产生死循环）	较小（细节优化了，虽然仍不安全）

小Tips：

• 头插法问题（JDK7）：在多线程情况下可能导致循环链表，进而死循环！（恐怖如斯）
• 尾插法优化（JDK8）：有效减少并发问题，虽然HashMap本质仍是线程不安全的！

五、来一波实际代码验证！

简单插入演示一波，感受一下HashMap在内部的神奇变化～

Map<Integer, String> map = new HashMap<>();
for (int i = 0; i < 20; i++) {
    map.put(i, "val" + i);
}
System.out.println(map);

当然，要想肉眼看出红黑树？不行，你得自己模拟大量哈希冲突（让不同key算出来的index相同）。
要不然，正常使用时，HashMap是懒得“变身”的，树化操作非常罕见。

六、为什么JDK8要加红黑树？

很简单，性能瓶颈！

假设极端情况下，所有元素哈希冲突，全部堆叠在一个链表里，查找一个元素的时间复杂度是O(n)——这对大数据量下的系统简直灾难。
而红黑树查询时间复杂度是O(log n)，所以JDK8把链表转成红黑树，大大提高了极端场景下的查询性能！

一句话总结：链表是懒，红黑树是精！

七、总结升华

如果你要面试或深入掌握HashMap，下面这些点一定要掌握：

• HashMap底层结构是数组+链表（JDK7）/数组+链表+红黑树（JDK8）。
• JDK8优化了冲突处理，防止极端情况下HashMap变得又慢又卡。
• JDK8在链表长度大于等于8且数组长度≥64时才树化，避免小数据无谓开销。
• 线程安全？HashMap天生不是，想要线程安全用ConcurrentHashMap！
• 默认初始容量是16，负载因子0.75，扩容方式是翻倍增长。

结语

看完这篇，是不是觉得HashMap也挺励志的？
从当年简单粗暴的小伙子，到现在优雅高效的精英程序员，它的成长之路，简直就是Java集合框架中的一段传奇！

… …

文末

好啦，以上就是我这期的全部内容，如果有任何疑问，欢迎下方留言哦，咱们下期见。

… …

学习不分先后，知识不分多少；事无巨细，当以虚心求教；三人行，必有我师焉！！！

wished for you successed ！！！

---

⭐️若喜欢我，就请关注我叭。

⭐️若对您有用，就请点赞叭。
⭐️若有疑问，就请评论留言告诉我叭。

---

版权声明：本文由作者原创，转载请注明出处，谢谢支持！