简介：面向Java初学者及进阶者的一套数据结构与算法学习资料包，围绕数组、链表、栈、队列、哈希表、二叉树、图、贪心算法、克鲁斯卡尔算法、马踏棋盘等主题系统整理，并配套尚硅谷韩顺平老师的视频讲解入口、课程课件、手写笔记与图解，帮读者把抽象概念落到代码层面。包内共140个文件，主体为48个Java源文件和80个class编译文件，可直接运行观察算法效果，同时包含pptx课件、pdf文档、xlsx表格与工程配置文件，适合按目录逐章学习。压缩包约24.06MB，已有182人学习使用。通过源码阅读和对照笔记，能获得霍夫曼编码、逆波兰计算器、单链表演示、图遍历等实例的完整代码实现与排错参考，既能用于校招面试准备，也可作为日常开发中复习数据结构的快捷手册。
1. 一份「Java数据结构分享.zip」到底能给你什么
这类压缩包在网盘收藏夹里出现的频率极高，点进去大概率是手写代码、结构图解、复杂度速查表和几道经典算法题的混合体。但它真正值钱的不是压缩包本身，而是里面那根把数组、链表、栈、队列、哈希表、树、堆、图串在一起的线——你能不能在没有任何参考的情况下，把它重新写出来。这篇笔记适合两类人：准备面试但被八股文绕晕的求职者，以及想把数据结构的代码实现变成肌肉记忆的 Java 开发者。我会按这类资源包最常见的骨架，把每个核心结构必须掌握的代码细节、复杂度边界和最容易翻车的地方拆开，帮你把它消化成自己的东西。
2. 先把骨架摸清：一份合格的 Java 数据结构资料包里有什么
2.1 看清单：开箱之后先检查这四类内容
拿到任何一个「Java数据结构分享.zip」，第一步不是看代码，而是看它的目录结构。我判断一份资料是否值得往下读，只看四条：有没有统一接口、有没有测试代码、讲不讲均摊复杂度、是不是 JDK 8 之后的实现。典型的包里，内容大致可以归成下面几类：
| 内容类别 | 常见形式 | 判断质量的关键点 |
|---|---|---|
| 结构实现源码 | .java 文件 | 是否自带泛型，是否处理了扩容和边界 |
| 图解笔记 | .md / .png | 是否画了链表指针变化和哈希冲突过程 |
| 复杂度速查 | 表格 / 卡片 | 是否区分了平均、最坏、均摊复杂度 |
| 配套习题 | 题目 + 答案 | 答案是否只贴代码，还是解释了思路 |
如果一份包里所有代码都是List list = new ArrayList()这种裸类型写法，或者 HashMap 还在讲头插法，那这份资料大概率是七八年前的老货，可以直接弃。反过来，如果它每个结构都给出了接口定义和边界测试，哪怕代码写得丑一点，也值得看完——因为丑代码反而更容易暴露出你对指针移动、扩容时机这些细节的理解。
2.2 学习线：把 8 个核心结构排成一条依赖链
数据结构之间不是孤立的，它们存在天然的依赖关系。常见的做法是先线性后非线性，先简单后复杂。我习惯按这条线推进：
- 数组 → 链表：搞清楚连续内存和离散内存各付出了什么代价。
- 栈、队列：在数组和链表之上加操作限制，学习线就通了一半。
- 哈希表：用数组加链表（或红黑树）解决快速查找的冲突问题。
- 二叉树、堆：引入递归和层级概念，为图打基础。
- 图：把前面的结构当作图的存储和遍历工具。
这条链上，最容易被跳过的其实是「手写链表」。很多看资料的人觉得链表面试不会考完整实现，结果遇到反转链表、环形链表检测时，指针指来指去就是画不清楚。跳过链表直接学 HashMap 的人，也很难真正理解为什么树化阈值是 8 而不是 16。
2.3 第一份能跑的代码：手写泛型动态数组
把资料包放下，先自己写一个精简版 ArrayList。这是检验你有没有吃透「均摊复杂度」的最佳试金石。
public class MyArrayList<T> { private Object[] data; // 真正存元素的数组 private int size; // 已存元素个数，不是数组容量 private static final int DEFAULT_CAPACITY = 10; public MyArrayList() { this.data = new Object[DEFAULT_CAPACITY]; } public MyArrayList(int initialCapacity) { if (initialCapacity < 0) { throw new IllegalArgumentException("容量不能为负数: " + initialCapacity); } this.data = new Object[initialCapacity]; } public boolean add(T value) { ensureCapacity(size + 1); data[size++] = value; return true; } @SuppressWarnings("unchecked") public T get(int index) { checkIndex(index); return (T) data[index]; } public T remove(int index) { checkIndex(index); T old = get(index); int moved = size - index - 1; if (moved > 0) { System.arraycopy(data, index + 1, data, index, moved); } data[--size] = null; // 末尾置空，避免内存泄漏 return old; } private void ensureCapacity(int minCapacity) { if (minCapacity > data.length) { int newCapacity = data.length + (data.length >> 1); if (newCapacity < minCapacity) { newCapacity = minCapacity; } data = Arrays.copyOf(data, newCapacity); } } private void checkIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("index=" + index + ", size=" + size); } } }代码里有两个关键点。第一，data声明为Object[]而不是T[]，因为 Java 泛型在运行期会擦除类型，直接new T[10]根本过不了编译；取元素时强转回去，并靠上层的泛型约束保证类型安全，这是官方 ArrayList 同款的处理方式。第二，扩容用的是data.length + (data.length >> 1)，也就是每次扩到原来的 1.5 倍。
同样是为了避免扩容时「复制整个数组」的开销。倍增太大会浪费内存，倍增太小会频繁触发复制，1.5 是实践下来相对平衡的点。一个更真实的场景：比如你要往这个数组里加 1000 个元素，如果知道量级，直接new MyArrayList(1024)可以省掉约 4 次扩容和 4 次全量复制，这就是调参数的意义。JDK 的常见实现里无参构造并不会立即分配容量为 10 的数组，而是先用一个空数组占位，等到第一次add才真正分配，这是为大量「创建后不使用」的对象省内存，你可以在自己的代码里同样实现这个懒加载逻辑。
3. 哈希表与二叉树：最值得抄也最容易抄错的两块硬骨头
3.1 HashMap 的 put 流程：从 hash 扰动到红黑树化
HashMap 是 Java 数据结构资料包里的必讲内容，也是很多人背了源码却答不出「为什么」。先把两个核心参数放在前面，这是你写代码时要关注的本源。
| 参数 | 默认值 | 作用与触发条件 |
|---|---|---|
| 负载因子 | 0.75 | 元素个数超过容量 × 0.75 时触发扩容 |
| 树化阈值 TREEIFY_THRESHOLD | 8 | 单个桶位链表长度 ≥ 8 且容量 ≥ 64 时转红黑树 |
| 退化阈值 UNTREEIFY_THRESHOLD | 6 | 红黑树节点数 ≤ 6 时退化为链表 |
| 最小树化容量 MIN_TREEIFY_CAPACITY | 64 | 容量 < 64 时只扩容不树化 |
put 一个 key 的完整路径是：先对 key 做 hash 扰动，再把计算出的桶位找出来；如果桶位为空直接放入，不为空则判断是链表还是红黑树，再决定尾插还是树化插入；插入后如果size > 容量 × 0.75，就触发扩容重排。hash 扰动这一步，源码有一段经典写法：
static final int hash(Object key) { int h; // 取 hashCode 之后，把高 16 位异或到低 16 位 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } // 计算桶位下标：容量为 16 时，直接 hash & (16 - 1) int index = hash(key) & (table.length - 1);这段代码解决了一个实际问题：取模运算hash % length和位运算hash & (length - 1)等价的前提是 length 恰好是 2 的幂。HashMap 的容量始终是 2 的幂，所以它能用位运算加速。但 hashCode 的低位如果很相似，直接与运算会让大量 key 挤在同一个桶里；把高 16 位异或进来，相当于在低位混入了高位的随机性，冲突概率大幅下降。字母表上 16 个字符全部具备相同高位、不同低位的情况，这个操作的价值立即就能体现出来。
3.2 二叉树实现：递归遍历与显式栈的边界差
二叉树是递归思想最好的载体，也是新手第一次被 StackOverflow 暴击的地方。先实现一个最简单的二叉搜索树插入与中序遍历：
class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } public void insert(TreeNode root, int value) { if (value < root.val) { if (root.left == null) { root.left = new TreeNode(value); } else { insert(root.left, value); } } else { if (root.right == null) { root.right = new TreeNode(value); } else { insert(root.right, value); } } } public void inOrderRecursive(TreeNode node) { if (node == null) { return; } inOrderRecursive(node.left); System.out.println(node.val); inOrderRecursive(node.right); }递归版代码非常简洁，只做三件事：遍历左子树、打印当前值、遍历右子树。但面试官通常会追问一句：递归的深度上限在哪？默认虚拟机栈的深度受线程栈大小限制，通常在几千层到 1 万层之间，超过就会抛 StackOverflowError。当数据均匀插入时二叉搜索树高度是 log2(n)，1 万个节点也没问题；一旦数据已经有序，你按顺序插入得到的是一棵退化链表，高度等于节点数，5 万个节点就能轻松打爆栈。
显式栈迭代版是必须掌握的第二版本：
public void inOrderIterative(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); System.out.println(cur.val); cur = cur.right; } }核心逻辑是：一路向左把节点压栈，直到究竟，再弹栈打印，然后转向右子树。空间复杂度同样是 O(h)（h 是树高），但好处是栈是你自己控制的，可以预估占用，甚至提前检查剩余空间。这也是很多生产代码不用递归做树遍历的原因——递归栈崩了没法优雅处理，显式栈至少能让你拿到一个异常然后降级。中序的时间复杂度无论如何都是 O(n)，空间复杂度从平均看 O(log n)，最差看 O(n)，资料包里的复杂度速查卡如果在这一点含糊其辞，你要能立刻指出来。
3.3 一张表收住六种结构的复杂度
很多人把八股文背得滚瓜烂熟，一到现场让他写一行代码就露馅。根本原因是没有把「结构怎么存储」和「复杂度为什么是这样」连起来。下面这张表，建议你抄进笔记并默写三遍：
| 结构 | 查找 | 插入 | 删除 | 关键记忆点 |
|---|---|---|---|---|
| 动态数组 | O(1) 索引 / O(n) 按值 | 尾部 O(1) 均摊，中间 O(n) | 尾部 O(1)，中间 O(n) | 移位是删除的主要成本 |
| 单链表 | O(n) | 头插 O(1)，尾插要遍历 | 已知前驱 O(1) | 指针移动比数组快 |
| 栈 | O(n) 查值 | O(1) 压入 | O(1) 弹出 | 只操作栈顶 |
| 队列 | O(n) 查值 | O(1) 入队 | O(1) 出队 | 环形数组实现避免搬移 |
| 哈希表 | O(1) 平均 / O(n) 最坏 | O(1) 平均 | O(1) 平均 | 扩容重排是性能杀手 |
| 二叉搜索树 | O(log n) 平均 / O(n) 退化 | O(log n) / O(n) | O(log n) / O(n) | 有序输入直接退化成链表 |
这张表是面试时回答「选型」的支撑。比如大量「按顺序追加、按下标读取」用数组，「频繁头部插入删除」用链表，「按 key 快速存取」用哈希表，「需要有序遍历且频繁插入」用平衡树。能把选型理由说得比表上更细一层，例如「Java 的 LinkedList 同时实现了 List 和 Deque，所以它既能下标遍历又能双端操作，但代价是每个节点多存两个指针，内存开销翻倍」，这份资料包就算真正有了价值。
4. Java 数据结构自学最常见的 5 个翻车现场与排查方法
4.1 现象：代码编译全是裸类型告警，运行期突然 ClassCastException
这是老资料包最典型的毛病。曾经有同学下载了一份数组实现，里面清一色List list = new ArrayList()，没写泛型。当时没在意，直到从 list 里取出数据强转成自定义类型，运行到一半抛 ClassCastException，而且报错位置和真正出问题的 puts 相隔很远，排查非常痛苦。
原因：泛型在编译期被擦除，不写类型参数等于让编译器放弃检查，任何对象都能混进去，取出来时必须自己记住原来放的是什么类型。
解决：所有容器声明都带上具体类型，List<String>、Map<String, Integer>这些一个都不能少。顺手在编译器打开-Xlint:unchecked，把所有泛型告警清成零再做后续测试。这一步能在编译期把七成的类型骚操作拦住。
4.2 现象：HashMap 数据量到十万级之后，插入和查询越来越慢
某个模拟项目里日志出现规律性卡顿，排查发现统计接口用的 Map 把订单对象当作 key，而订单对象没有重写 hashCode，默认用对象地址，每次重启对象地址全变，相同订单永远取不到旧值，数据越堆越多。
原因：可变对象或者不稳定的 hashCode 是哈希表最隐蔽的杀手。另外，当大量 key 落在同一批低位 hash 上，链表退化到 8 个节点以上，插入变为 O(n)。
解决：key 一律用不可变对象，字符串或包装类型最省心；自定义类做 key 必须同时重写 hashCode 和 equals，并且 hashCode 里只放业务上不可变字段。如果流量确实大，初始容量直接new HashMap<>(expectedSize)，避免连续扩容重排，阈值可以按预期容量 / 0.75估算，让表一次到位。
4.3 现象：手写链表的 add 方法一跑就死循环，CPU 直接拉满
这是一个经典笔试题翻车现场。写单链表尾插时，新节点的next忘记初始化为空，而构造顺序又正好让旧节点的next指向了新节点，两个节点互相循环。调试时去看头节点，视觉上一片健康，就是遍历不到结尾。
原因：链表代码必须把指针的边界想清楚，尾插的核心是「让当前尾节点的 next 指向新节点」，如果新节点的 next 引用了一个旧对象，就形成了环。
解决：每次插入都把新节点next显式置空，再处理前一个节点的指针。更稳妥的做法是写一个最小测试用例，插入 3 个节点之后遍历 10 次，一旦出现重复节点立刻判定有环。这也是为什么养成「每个数据结构的包都配测试」的习惯比什么都重要——没有测试的链表代码，在面试场上只能靠肉眼硬扛。
4.4 现象：递归遍历二叉树，数据一上规模就 StackOverflow
某次性能验证中，把一千万个递增数字加进二叉搜索树，然后做一次中序遍历，结果刚跑到第八层递归就栈溢出。当时第一反应是函数写错了，后来才意识到是树退化了。
原因：数据有序时二叉搜索树高度等于节点数，默认线程栈承载不了这么深的递归。这是结构本身的问题，不是代码写错。
解决：两个方向。方向一，插入前做一次随机打乱，让树尽量平衡；方向上，彻底改用显式栈迭代遍历，把递归栈换成堆内存中的 Deque，堆空间比栈空间宽裕得多。如果资料包里的树又复习了，直接考虑 Jump to Red-Black Tree 或使用现成的 TreeMap 实现，再配合-Xss调整线程栈大小——但调整栈大小只是延缓问题，不是根治。
4.5 现象：ArrayList 频繁 add 导致内存抖动明显
这是大部分资料包都不会提的细节。某跨平台系统处理大批量上报数据时用new ArrayList<>()一路 add，结果 GC 压力陡增，堆内存碎片化。
原因：默认容量只有 10，数据量过百后，每次扩容 1.5 倍都要把旧数组整个复制到新数组。旧数组会一直留在堆里等 GC，复制频繁期，新生代被这种大对象挤爆，触发多次 Full GC。
解决：提前预估条数，new ArrayList<>(expectedSize)把扩容次数压到零到一次。如果实在无法预估，宁可给一个偏大的初始值，也不要让它一次一次地小步扩容。ArrayList 的均摊复杂度 O(1) 能掩盖掉大部分性能损失，但掩盖不了 GC 的压力——这是很多资深的系统排查血泪经验。
5. 让这份资料包升值：把「看过的代码」变成「能跑的模板」
一份 Java 数据结构资源包最终能留下多少价值，取决于你是否把它重构成了自己的模板库。我建议所有拿到这类包的人，做一次如下重构动作，而不是只把 zip 解压放进收藏夹。
给每个结构配「五个一」：一个接口、一个实现、一个复杂度表项、一个边界用例、一道手写题。以动态数组为例，接口就收敛成add / get / remove / size四个方法，实现就是上面那版 MyArrayList，复杂度表项就是「尾部 O(1) 均摊」，边界用例固定写这三个场景：空容器、单元素、扩容阈值附近。手写题则挑一道「按数组实现队列」作为对照。有了这五个一，每个结构都能单独拿出来复习，而不是每次从 8 个结构里大海捞针。
重点强调：每一个实现都要挂一个带断言的验证脚本。比如动态数组的最小验证，用 main 方法就能完成：
public static void main(String[] args) { MyArrayList<Integer> list = new MyArrayList<>(2); if (list.size != 0) { throw new AssertionError("初始大小应为 0"); } list.add(1); list.add(2); list.add(3); // 触发扩容 if (list.get(2) != 3) { throw new AssertionError("扩容后下标访问失败"); } int removed = list.remove(1); if (removed != 2 || list.size != 2) { throw new AssertionError("删除后数据不正确"); } System.out.println("动态数组验证通过"); }注意这里刻意没有用assert关键字，因为 JDK 默认关闭断言开关，很多人写了 assert 跑不出效果还以为自己错了。用if + throw最保险，换任何一台机器都能直接复现。这个验证习惯，是那些只贴代码不贴测试的分享包永远不会教你的。
我自己的习惯是：解压任何一份资料包后，先在旁边建一个verify目录，把所有手写结构的验证脚本放进去；每看完一个结构，就自己实现一遍并跑通验证，然后才看作者的原实现做对比。某次跳过验证直接看答案，结果一个月后发现连 HashMap 的负载因子都记串了。验证用例不是给别人看的，是给三个月后的自己复习用的。
数据结构的功底不是背下来的，是抄一遍、跑一遍、翻车一遍之后长在手上的。希望这份拆解能帮你把「Java数据结构分享.zip」变成真正拉得出来打的弹药库，希望帮到你。
本文还有配套的精品资源，点击获取
