企业官网建设流程全解析

简介：面向Java初学者与进阶者的数据结构与算法学习包，内容覆盖数组、链表、栈、队列、哈希表、树和图等核心结构，以及排序、搜索、动态规划、贪心等常见算法，帮助读者理解数据组织方式与程序效率的关系，适合备战面试、课程学习或项目开发前系统补强。包内共140个文件，压缩后约24.06MB，以48个Java源码和80个class文件为主，另有课件PDF、PPT笔记、表格整理及视频链接说明等。源码对应韩顺平老师数据结构课程中的典型实例，如哈夫曼编码、图遍历、贪心算法、马踏棋盘等，便于对照学习；编译后的class文件可直接运行，辅助验证算法效果。配套的图解与笔记则帮助梳理概念，形成“视频讲解+源码实践+笔记巩固”的完整闭环。目前已有182人浏览学习，适合希望从理论到实战系统掌握Java数据结构和算法的读者。

1. 拿到「Java数据结构分享.zip」之后，先别急着解压

这个标题看起来像一个资源包，但实际上它背后藏着的需求非常具体：要么是准备面试，要么是期末复习，要么是刚学完 Java 基础想补数据结构的短板。一个 zip 压缩包解决了「资料从哪来」的问题，但解决不了「学完能不能用」的问题——我见过太多人解压完看了两章就丢在硬盘里，等到面试问 HashMap 扩容机制时只能说个大概。

这个方案真正要解决的是：把 Java 里最常考、最常用的数据结构，从底层实现到手写代码到面试追问，串成一条能照着练的路线。适合两类人——准备校招社招的 Java 工程师，以及学完 Java 语法但写不出链表反转的初学者。如果你已经能熟练用ArrayList和HashMap，但不清楚它们是怎么用数组和链表实现的，这篇笔记就是给你准备的。

下面我按「先建立知识框架，再动手敲代码，最后排坑」的顺序，把这条路走一遍。核心思路是：数据结构不是靠背的，是靠「手写实现 + 看源码 + 刷题验证」三件事一起做的。

2. Java 里数据结构的选型逻辑：为什么面试总盯着 ArrayList、HashMap 和 ConcurrentHashMap

2.1 三个高频容器的底层真相

Java 集合框架是面试重灾区，但绝大多数人只停留在「会用」层面。先说ArrayList：它底层就是一个Object[]，默认容量是 10，当元素个数超过容量时，会按oldCapacity + (oldCapacity >> 1)扩容——也就是原来的 1.5 倍。这里有个容易忽略的细节：add方法先检查容量，不够就grow，然后才赋值。所以如果你能预估数据量，最好在构造时指定初始容量，否则会频繁扩容、频繁Arrays.copyOf，性能肉眼可见地掉。

LinkedList则是一个双向链表，每个节点有prev、next、item三个字段。它和ArrayList的核心区别不仅在插入删除的复杂度，更在内存占用——每个节点要多存两个指针，64 位 JVM 上开启指针压缩后，一个节点光额外开销就是 16 字节左右。所以不要被「链表插入快」这句话骗了：在 ArrayList 尾部插入，和 LinkedList 尾部插入，实际性能接近，因为 ArrayList 尾部插入大概率不用扩容。而中间插入，LinkedList 需要先遍历找到位置，复杂度也是 O(n)。

再说HashMap，它是数组加链表加红黑树的结构。数组默认容量是 16，负载因子是 0.75，链表转红黑树的阈值是 8，红黑树退化为链表的阈值是 6。这几个数字是面试必问的，但更重要的是理解为什么是 8 和 6——这是时间和空间的权衡。当链表长度到 8 时，平均查找时间已经接近红黑树的优势区间；转成红黑树后每个节点要多存颜色位和父节点引用，所以如果频繁增删导致长度在 6 到 8 之间震荡，就会白白浪费内存。源码里用MIN_TREEIFY_CAPACITY = 64限制了转树的最小容量，如果数组长度没到 64，就算链表超过 8 也不会转树，而是先扩容——这一点很多人会忽略。

2.2 并发场景下的选择：从 Hashtable 到 ConcurrentHashMap

很多人在并发场景下还在用Hashtable，这不算错，但属于「能跑但不够好」。Hashtable直接在方法上加synchronized，相当于所有线程竞争同一把锁，并发一高就全部串行化。ConcurrentHashMap在 JDK 8 里放弃了分段锁，改用CAS + synchronized：put时如果目标桶为空，直接用CAS写入；如果桶不为空，则对桶头节点加synchronized锁。这样锁粒度从整个表降到了单个桶，并发度大幅提升。

面试里经常追问「为什么 ConcurrentHashMap 不允许 null 值」，这件事其实和并发安全没关系，而是因为get方法里用val == null来判断节点是否被删除——如果put允许 null，就会和「节点不存在」混淆。另外，它的size()不是实时精确值，而是通过sumCount()累加baseCount和CounterCell[]算出来的近似值。这意味着在高并发写入时，你拿到的 size 可能和实际有偏差。

2.3 选型决策表：什么场景用什么

这里想提醒一句：不要为了「显得高级」而过度设计。数据量只有几百条，用什么容器都差不多，真正要优先的是代码可读性和维护成本。选型这事，先满足功能，再考虑性能，最后才是炫技。

3. 手写一个简化版 HashMap：从 put 到 resize 的完整实现

3.1 为什么推荐手写，以及手写前要搞懂的三个锚点

看十遍源码不如自己写一遍。手写 HashMap 的目的不是造一个能上生产的轮子，而是把哈希算法、哈希冲突、负载因子、扩容机制这些概念从「听说过」变成「写在代码里」。我推荐按三个锚点来写：哈希函数怎么算、冲突怎么解决、什么时候扩容、扩容怎么搬数据。这三个问题答清楚了，源码里那些看似晦涩的位运算也就自然顺下来了。

先明确我们要实现的范围：只支持put、get、remove、size，冲突用链地址法，容量固定为 2 的幂次方，负载因子按 0.75。不做红黑树、不做并发支持。目标是能跑通基本逻辑，并且能在注释里说清每一步为什么这么做。

3.2 完整代码：简化版 HashMap

/** * 简化版 HashMap：数组 + 链表，固定容量，不支持红黑树 */ public class SimpleHashMap<K, V> { /** 桶数组：每个桶存一条链表的头节点 */ private Node<K, V>[] table; /** 当前存储的元素个数 */ private int size; /** 负载因子 */ private final float loadFactor = 0.75f; /** 容量，必须是 2 的幂，方便用位运算替代取模 */ private final int capacity; public SimpleHashMap(int capacity) { // 这里约定调用方传入的就是 2 的幂；实际 JDK 里有 tableSizeFor 做向上取整 this.capacity = capacity; this.table = new Node[capacity]; this.size = 0; } /** 单向链表节点 */ static class Node<K, V> { final int hash; final K key; V value; Node<K, V> next; Node(int hash, K key, V value, Node<K, V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } } /** 扰动函数：让高位也参与低位运算，尽量分散 */ private int hash(K key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** 算出桶下标：capacity 是 2 的幂，所以可以用 & 代替 % 取模 */ private int indexOf(int hash) { return hash & (capacity - 1); } public V put(K key, V value) { int hash = hash(key); int index = indexOf(hash); Node<K, V> head = table[index]; // 情况一：桶是空的，直接放一个新节点 if (head == null) { table[index] = new Node<>(hash, key, value, null); size++; return null; } // 情况二：桶不为空，遍历链表找相同 key，找到就覆盖值 Node<K, V> cur = head; while (cur != null) { if (cur.hash == hash && (cur.key == key || (cur.key != null && cur.key.equals(key)))) { V oldValue = cur.value; cur.value = value; return oldValue; } cur = cur.next; } // 情况三：链表中没有相同 key，就头插法插入（JDK 7 用头插，JDK 8 用尾插） Node<K, V> newNode = new Node<>(hash, key, value, head); table[index] = newNode; size++; // 超过负载因子就扩容 if (size > capacity * loadFactor) { resize(); } return null; } public V get(K key) { int hash = hash(key); int index = indexOf(hash); Node<K, V> cur = table[index]; while (cur != null) { if (cur.hash == hash && (cur.key == key || (cur.key != null && cur.key.equals(key)))) { return cur.value; } cur = cur.next; } return null; } public V remove(K key) { int hash = hash(key); int index = indexOf(hash); Node<K, V> prev = null; Node<K, V> cur = table[index]; while (cur != null) { if (cur.hash == hash && (cur.key == key || (cur.key != null && cur.key.equals(key)))) { if (prev == null) { // 要删的是头节点，直接把桶的指针指向下一个 table[index] = cur.next; } else { // 要删的是中间节点，用前驱节点跳过它 prev.next = cur.next; } size--; return cur.value; } prev = cur; cur = cur.next; } return null; } public int size() { return size; } /** 扩容为原来的两倍，并重新散列所有节点 */ @SuppressWarnings("unchecked") private void resize() { Node<K, V>[] oldTable = table; int oldCapacity = capacity; int newCapacity = oldCapacity << 1; Node<K, V>[] newTable = new Node[newCapacity]; for (int i = 0; i < oldCapacity; i++) { Node<K, V> cur = oldTable[i]; if (cur == null) { continue; } // 遍历旧桶上的整条链表，重新计算每个节点在新数组里的下标 while (cur != null) { Node<K, V> next = cur.next; int newIndex = cur.hash & (newCapacity - 1); // 采用头插法迁移，代码简单，但会反转链表顺序（JDK 7 的经典问题） cur.next = newTable[newIndex]; newTable[newIndex] = cur; cur = next; } } table = newTable; } }

3.3 代码逻辑说明：每个关键点为什么这样写

先看hash方法。hashCode()返回的是一个 32 位整数，而我们拿它和capacity - 1做与运算，如果直接用原始 hashCode，只有低几位起作用——比如容量是 16，capacity - 1是 15，二进制是0000...00001111，那么真正参与下标计算的就只有 hashCode 的低 4 位，高位全部浪费，极易碰撞。所以 JDK 里把高 16 位异或低 16 位，让高位信息也混入低位，这就是h ^ (h >>> 16)的意义。我在代码里同样保留了这个扰动逻辑。

再看indexOf。因为容量约定为 2 的幂，所以hash & (capacity - 1)和hash % capacity在数学上等价，但位运算没有除法，快得多。这个优化在实际生产代码里随处可见，面试时能主动说出来是加分项。

扩容逻辑里有一个反复出现的坑：JDK 7 的头插法在并发扩容时会产生循环链表。因为多线程同时执行resize()时，两个线程可能把一个节点的next指来指去，最终成环。在我的简化版里用的是头插，这在单线程下没问题，但如果你拿这段代码去做并发测试，翻车是必然的。JDK 8 改成尾插就是为了规避这个问题——它不再改变链表原有的相对顺序，即使并发扩容，链表中各节点的前后关系不会被打乱，只在极端情况下可能丢数据，但至少不会死循环。写代码时可以在注释里把这个演进过程写明，面试官问「为什么 JDK 8 改尾插」时，你就能直接接上。

3.4 参数怎么调：容量、负载因子和扰动函数的取舍

如果让你把这个简化版改成可用版本，有两个参数值得折腾一下。一个是负载因子，调低（比如 0.5）会减少哈希冲突、增加扩容频率，内存浪费更多；调高（比如 1.0）会省内存但链表可能变长，查询变慢。另一个是初始容量，如果能预估数据量 N，最好设为N / 0.75 + 1再向上取 2 的幂，这样既能避免扩容又能让负载因子发挥作用。还有一个细节：hash扰动函数在 JDK 8 里保留，但字符串类型的 key 本身就有很好的散列性，所以实际收益有限——真正该关注的是让 key 的hashCode()足够分散，比如用Objects.hash组合多个字段时，避免返回固定值或过于规律的数值。

4. 栈、队列、树的 Java 实现套路：从笔试代码到工程习惯

4.1 用 ArrayDeque 还是 LinkedList？一个被低估的选择

很多人在写栈和队列时会下意识用Stack和LinkedList，但Stack在 JDK 文档里已经被建议不再使用，因为它是继承Vector实现的，所有方法都带锁，性能差且设计混乱。我自己写代码时，栈和队列统一用ArrayDeque。它底层是循环数组，不需要节点对象，内存占用比LinkedList少，且没有锁开销。

工程上还有一个容易被忽略的点：ArrayDeque 不能放 null。因为它的实现里用null表示「这个位置是空的」，如果你真的往里面 push 了 null，后续的poll会把它当成空位跳过，导致逻辑错乱。所以如果你需要存储 null 元素，老老实实用LinkedList。

// 用 ArrayDeque 实现栈：push / pop / peek ArrayDeque<String> stack = new ArrayDeque<>(); stack.push("a"); stack.push("b"); String top = stack.peek(); // b，不移除 String pop = stack.pop(); // b，移除并返回 // 用 ArrayDeque 实现队列：offer / poll / peek ArrayDeque<String> queue = new ArrayDeque<>(); queue.offer("a"); queue.offer("b"); String head = queue.peek(); // a，不移除 String poll = queue.poll(); // a，移除并返回

注意push是在头部插入，offer是在尾部插入。面试经常考「用两个栈实现队列」或「用两个队列实现栈」，这两个题就是围绕push和offer的方向感设计的。写这种题时优先考虑ArrayDeque，因为性能好且代码更简洁。

4.2 手写二叉树遍历：递归改迭代的关键是「模拟栈」

树的题目里，递归写法又短又好懂，但面试官常常追问「能不能用迭代写」——因为递归隐含系统栈调用，深度一大就栈溢出。把递归改成迭代，核心是用一个显式栈来模拟系统栈的压栈和出栈过程。

先看前序遍历。递归的顺序是「根 -> 左 -> 右」，迭代实现可以反过来：先压右子树，再压左子树，这样出栈时就是先左后右。

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } ArrayDeque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); // 先访问根 if (node.right != null) { stack.push(node.right); // 右子树先压栈，后访问 } if (node.left != null) { stack.push(node.left); // 左子树后压栈，先访问 } } return result; }

中序遍历的迭代写法稍微麻烦一点：需要先把左子树一路压到底，然后逐个弹出访问，每弹出一个节点就转去处理它的右子树。

public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); ArrayDeque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 一路走到最左边 while (cur != null) { stack.push(cur); cur = cur.left; } // 此时 cur 为 null，弹出栈顶 cur = stack.pop(); result.add(cur.val); // 转向右子树，如果右子树为空，外层循环会继续弹出父节点 cur = cur.right; } return result; }

这段代码里最容易被问到的就是「为什么外层循环判断条件是cur != null || !stack.isEmpty()」——因为当 cur 为空但栈里还有节点时，说明还有父节点待访问；当 cur 不为空但栈为空时，说明正在往更深层的左子树走。缺一不可。

4.3 树的层序遍历：队列的典型应用场景

层序遍历（BFS）用队列实现，核心是每轮记录当前层的节点数size，然后只弹出size个节点，这样每一层就能单独分隔开。这也是 LeetCode 102 题的解法骨架。

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } ArrayDeque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }

这里的坑在于queue.size()必须在进入 for 循环之前取好，因为每弹出一个节点再 offer 它的孩子，size 就会变。很多人写错就是把queue.size()直接写在 for 循环的条件里，结果每一层弹出的节点数都不对。这道题如果面试官追问「BFS 为什么用队列不用栈」，答案在于队列的先进先出天然保证了同层节点从左到右的访问顺序。

4.4 排序算法的 Java 实现与选型

数据结构里绕不过排序。背口诀没用，要理解每个排序的本质。我一般会让新手亲手写四类：冒泡排序、快速排序、归并排序和堆排序。冒泡排序是教学用，真实项目里没人用；快速排序是工程默认，但要注意轴点选择的退化问题；归并排序是外部排序的基础；堆排序则是优先队列的内部实现。

// 快速排序（Hoare 分区法，随机选轴点避免最坏情况） public void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } // 随机选轴点，避免对近乎有序数组退化成 O(n^2) int pivotIndex = left + new Random().nextInt(right - left + 1); swap(arr, pivotIndex, right); int pivot = arr[right]; int i = left; for (int j = left; j < right; j++) { if (arr[j] < pivot) { swap(arr, i, j); i++; } } // 把轴点放回它最终应该在的位置 swap(arr, i, right); quickSort(arr, left, i - 1); quickSort(arr, i + 1, right); } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

随机选轴点这一步不是锦上添花，而是防翻车的关键。如果数组本身接近有序，固定选最后一个元素当轴点会让分区极度不平衡，时间复杂度退化成 O(n²)。工程实践里常用的优化还有「三数取中」——取左、中、右三个位置的中位数当轴点，效果和随机选接近，但不需要额外的随机数开销。

归并排序则需要额外的 O(n) 辅助空间，它是稳定排序，而快速排序不稳定。这个「稳定 vs 不稳定」的差别在实际场景里很重要——比如先按价格排序再按销量排序，如果排序稳定，第二次排序会保留第一次排序的相对顺序。面试里常问「什么场景用归并不用快排」，答案就是需要稳定性的场景。

5. 避坑指南：Java 数据结构实践中的 5 个高频翻车点

5.1 自定义对象放入 HashSet，equals 不一致导致查不到数据

现象：把同一个「逻辑上相等」的对象放入HashSet后再用另一个相同内容的对象contains，返回 false。

原因：HashSet先通过hashCode()定位到桶，再通过equals()判断是否相同。如果你只重写了equals()而没重写hashCode()，那么内容相同的两个对象会计算出不同的哈希值，被分配到不同的桶里，永远碰不到面。

解决：重写equals()时必须同时重写hashCode()，且保证equals()返回 true 的两个对象hashCode()结果必须一致。常见做法是让 IDE 自动生成这对方法，避免手写失误。

5.2 HashMap 的 key 用可变对象，修改后 get 直接失败

现象：把一个对象当作 key 放进 HashMap，之后修改了这个对象的某个字段，再用同一个对象去get，返回 null。

原因：HashMap在 put 时根据当时的hashCode()计算好桶下标并存储。对象字段变了，hashCode()也变了，但桶下标不会重新计算，get时计算出的新下标和存储时的下标不一致，自然找不到。

解决：HashMap 的 key 必须是不可变对象，最稳妥的是用String或Integer。如果业务上必须用自定义对象，就把参与hashCode()的字段设为final，或者在对象生命周期内禁止修改那些字段。

5.3 ArrayList.subList 返回的视图，修改后带崩原列表

现象：用list.subList(0, 2)拿到子列表，往里面add一个元素后，原列表的 size 变了，或者抛ConcurrentModificationException。

原因：subList返回的不是独立副本，而是原列表的一个视图，即一个内部类SubList，它持有parent引用。对子列表的修改会映射到原列表上；如果子列表创建后原列表被结构性修改（比如add或remove），子列表的modCount检测就会失败，抛出并发修改异常。

解决：如果不需要联动修改，直接new ArrayList<>(list.subList(0, 2))拷贝一份。如果业务上需要视图机制，就要保证子列表生命周期内原列表不要做结构性修改。

5.4 LinkedList 的 get(int index) 慢得离谱，循环里就别用

现象：对一个大 size 的LinkedList执行for (int i = 0; i < list.size(); i++) { list.get(i); }，性能极差，甚至比ArrayList慢两个数量级。

原因：LinkedList.get(i)内部要从头或尾开始遍历到第 i 个节点，复杂度 O(n)，整个 for 循环下来就是 O(n²)。而ArrayList.get(i)是数组下标访问，O(1)。

解决：遍历LinkedList一律用迭代器或 for-each。如果需要随机访问，不该选LinkedList。血泪经验是：用对容器比优化代码更有效。

5.5 Arrays.asList 得到的 List 不能 add，也不能 remove

现象：List<String> list = Arrays.asList("a", "b")后调用list.add("c")，抛出UnsupportedOperationException。

原因：Arrays.asList返回的是java.util.Arrays$ArrayList，它内部的set支持，但add和remove未实现，因为底层是定长数组。

解决：需要可变列表时，写成new ArrayList<>(Arrays.asList("a", "b"))。另外要注意，Arrays.asList里如果有基本类型数组，比如int[]，它会把整个数组当成一个元素，list 的长度是 1 而不是数组长度——用Arrays.stream(arr).boxed().collect(Collectors.toList())能正确转换。

6. 进阶技巧：用调试器「读」出数据结构的状态变化

数据结构这一块，最有效的学习方法不是反复抄代码，而是「打断点看状态」。我手写数据结构时有一个固定习惯：把table数组或链表节点设为主要观察对象，在put和resize的关键行打上断点，用 IDE 的调试模式逐步推进，亲眼看着节点怎么挂到桶上、链表怎么迁移到新数组。这一步比任何教程都管用，因为你能直观地看到「引用到底指向谁」。

具体做法是：在手写的SimpleHashMap里，给put的Node<K, V> newNode = new Node<>(hash, key, value, head)这行打断点，然后在调试器的 Variable 面板里展开table数组，逐一查看每个桶的链式结构。你会在resize的循环里看到链表顺序被头插法反转——这个现象只看代码是体会不到的，用调试器一眼就明白了。

另一个值得练的技巧是给hash方法打断点，观察同一个 key 在扩容前后hash & (capacity - 1)的结果变化：旧下标可能是 3，新下标可能是 3 或 19，因为容量从 16 变成 32，参与位运算的低位多了一位。这种「看得到」的规律性，会让 HashMap 的扩容不再是个黑匣子。

如果你跟着这个方案走，我的建议是给自己定一个三周计划：第一周手写SimpleHashMap并调通，第二周手写二叉树遍历的四种形式（前中后序加层序），第三周把排序算法的递归和迭代版本都写一遍，重点看递归深度和栈溢出边界。最后再回头去看 JDK 源码，你会发现原来那些看不懂的位运算和分支判断，拆开以后全部是你手写时踩过的坑。

这个方向值不值得投入，我的答案是：值得，但要带着目的去学。数据结构不是背名词，而是建立一种「看到可操作场景就能反射出对应结构」的直觉。希望这篇笔记能把你的资料包变成真正能用起来的工具——第一步，就是把 zip 解压后，挑一个数据结构，然后和我一样，打开调试器，亲手看它跑起来。

本文还有配套的精品资源，点击获取