1. 先想明白数据结构在Java里到底是什么做Java开发三五年的人跳槽面试时被问“HashMap为什么线程不安全”“ArrayList和LinkedList什么时候选谁”十有八九会一愣——不是不会是平时写业务代码根本用不到这些细究。但数据结构这个东西恰恰是区分“CRUD熟练工”和“真正理解程序运行逻辑”的分水岭。我自己的体会是数据结构在Java里从来不是一门孤立的课程它藏在三个层面里JDK源码层ArrayList、LinkedList、HashMap、TreeMap这些日常容器每一个都是某种经典数据结构的工业级实现封装了细节但保留了本质。算法应用层排序、二分查找、递归、遍历这些面试手撕题和数据机构408考研题考的其实是“你知不知道在什么场景下选什么结构”。系统设计层缓存淘汰LRU要LinkedHashMap路由表要前缀树任务调度要优先队列——这些都是在真实项目里验证数据结构价值的地方。所以这份笔记我不会从头讲“什么是数组”这种教科书内容而是用“面试源码实战”三合一的视角把Java里最核心的几类数据结构串一遍。适合准备Java面试的人、考研408复习的人以及写了一段时间业务代码但感觉技术深度见顶的开发者。2. 数组与链表ArrayList和LinkedList之争本质是内存布局之争2.1 先看JDK源码怎么选型很多初学者背过“数组查询快、增删慢链表增删快、查询慢”但真正问一句“为什么”能讲清楚的没几个。以ArrayList为例它的底层就是一个Object[]数组初始容量10满了之后扩容到1.5倍oldCapacity (oldCapacity 1)。数组在内存里是连续存储的所以通过下标访问能做到O(1)时间复杂度因为可以直接用“起始地址 下标 × 元素大小”算出内存地址。这就像电影院座位号你告诉我第几排第几座我直接算出位置不用一个一个数。LinkedList则是一个双向链表每个节点Node持有prev和next两个引用。插入删除确实快只要改前后节点的指针就行O(1)。但查找第n个元素时得从头或尾开始一个个遍历O(n)。这就像一根绳子上串了一串珠子你想拿第50颗珠子只能一颗一颗数过去。但有个细节很多人忽略LinkedList的“增删快”是有前提的——前提是你已经持有那个位置的节点引用比如迭代器所在位置。如果你要list.add(index, element)ArrayList因为要System.arraycopy移动元素确实慢但LinkedList也要先node(index)遍历到那个位置两个都是O(n)只是常数不同。2.2 实际开发里的选择建议我自己的经验日常业务代码里90%的场景用ArrayList原因很简单遍历为主遍历数组的缓存命中率远高于链表连续内存对CPU缓存友好链路节点分散容易cache miss。内存占用链表每个节点要额外存两个引用16字节左右的开销数据量大了差别很明显。新增操作如果是“追加到末尾”ArrayList的扩容均摊下来也是O(1)。LinkedList适合什么场景高频在头部插入删除或者需要频繁在迭代过程中增删元素用ListIterator。比如实现一个LRU缓存时LinkedHashMap底层就是哈希表双向链表这个组合是经典中的经典。Java还提供了一个容易被忽视的ArrayDeque这个类同时实现了栈和队列的功能而且性能比LinkedList做栈队列还要好因为环形数组没有节点开销。后面讲栈和队列时会再提它。// 模拟ArrayList扩容逻辑简化版 public boolean add(E e) { ensureCapacityInternal(size 1); elementData[size] e; return true; } private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍扩容 elementData Arrays.copyOf(elementData, newCapacity); }提示面试时如果能说出“扩容是1.5倍、初始容量是10、用Arrays.copyOf拷贝”再加一句“频繁扩容会触发GC压力所以预估数据量大时可以new ArrayList(capacity)”面试官基本就能确认你是真看过源码的。3. 栈、队列与哈希表高频考点的底层逻辑3.1 栈和队列别再用Stack类了Java的Stack类是个历史遗留设计它继承自Vector所有方法都加了synchronized锁性能低而且Vector底层是数组扩容逻辑和ArrayList一样。现代Java写栈和队列推荐用ArrayDequeDequeString stack new ArrayDeque(); stack.push(a); // 入栈 String top stack.peek(); // 看栈顶不弹出 String pop stack.pop(); // 出栈 DequeString queue new ArrayDeque(); queue.offer(a); // 入队 String head queue.peek(); // 看队头 String poll queue.poll(); // 出队ArrayDeque底层是循环数组head和tail两个指针容量按2的幂增长。用数组实现栈队列的经典套路比链表版省内存、更快。这里也埋了个考点为什么ArrayDeque容量必须是2的幂因为取模运算(tail 1) (elements.length - 1)比%高效得多这是位运算在数据结构里的典型应用。栈的应用场景面试必问括号匹配、表达式求值、函数调用栈、浏览器的前进后退。队列的场景生产者消费者、消息队列、BFS广度优先遍历。这些都属于“结构本身很简单但应用极其广泛”的类型。3.2 HashMapJava数据结构面试的头号热门HashMap是面试重灾区它底层结构在JDK 7和JDK 8之间有一次关键演进JDK 7数组 链表头插法JDK 8数组 链表 红黑树尾插法链表长度超过8且数组长度达到64时转红黑树为什么要加红黑树因为极端hash冲突下链表会退化成长链表查询退化成O(n)。红黑树能保证最坏O(logn)。但为什么不直接用树因为树节点TreeNode是普通Node内存占用的两倍左右只在链表确实太长时才转。几个必问的点为什么HashMap线程不安全并发put可能导致数据覆盖、扩容时形成环形链表JDK 7虽然JDK 8改成尾插法解决了环形链表问题但覆盖问题依然存在。所以并发场景用ConcurrentHashMap。为什么容量是2的幂为了让hash (n - 1)等价于hash % n同时位运算更快。扩容时元素要么留在原位置要么移动到“原位置旧容量”的位置这样重hash效率极高。负载因子为什么是0.75这是时间空间的一个折中。负载因子越大空间利用率高但冲突概率增大查询变慢负载因子越小浪费空间但查询快。0.75是Java官方大量测试得出的平衡点。// HashMap的hash扰动函数JDK 8 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这段代码的意思是把hashCode的高16位和低16位做异或让高位的特征也参与到低位运算中降低hash冲突的概率。主要因为数组默认才16位长度直接取模只用了低几位高位特征就浪费了。3.3 LinkedHashMap与TreeMap两个被低估的选手LinkedHashMap在HashMap基础上加了一条双向链表维护插入顺序或者访问顺序。设了accessOrder true之后每次get都会把节点移到链表尾部这天然就是LRU缓存的雏形。很多面试题让手写LRU最简解法就是继承LinkedHashMap并重写removeEldestEntry。TreeMap底层是红黑树key有序支持范围查询subMap、headMap、tailMap。如果业务上需要按key排序或者需要找“最接近某个值的key”ceilingKey/floorKeyTreeMap比遍历HashMap再排序高效得多。4. 树与图二叉树、红黑树到图的遍历链路排除法看的话Java生态里用得最多的树是二叉树家族而算法题里考得最狠的也是二叉树。从数据结构笔记的角度真正需要掌握的是这条链路普通二叉树 → 二叉搜索树BST→ 平衡二叉树AVL→ 红黑树 → 多路搜索树B树/B树。4.1 二叉树的遍历递归和迭代都要会前序、中序、后序、层序这四种遍历是树的基础。递归写法背三行就能写出来但面试如果只让写递归就落了下乘。真正的考点是用栈模拟递归实现前中后序遍历用队列实现层序遍历。一个记忆技巧前序遍历根左右用栈时先压右子节点再压左子节点中序遍历左根右要一路向左压栈弹出来之后处理右子树后序遍历左右根最绕可以用两个栈或者一个栈加prev变量标记。// 迭代实现二叉树的中序遍历 public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; // 一路向左 } cur stack.pop(); result.add(cur.val); // 弹出来时访问 cur cur.right; // 处理右子树 } return result; }层序遍历BFS更简单一个队列就搞定每次循环先取当前层的size然后pop这一层所有节点同时把下一层入队。这个套路也是“树的层次统计”“二叉树最大宽度”等题的基础。4.2 为什么是红黑树而不是AVL树一定有人好奇HashMap的树化、TreeMap底层都是红黑树为什么不是AVL平衡树AVL树是严格平衡的任意节点的左右子树高度差不超过1。查询确实快O(logn)最稳定。问题在于为了维持这种严格平衡插入删除时可能要频繁旋转一次插入可能引发多次旋转导致写操作开销大。红黑树的平衡标准放宽了从根到叶子的最远路径不超过最短路径的2倍也就是“黑色节点数相同红色节点不连续”。它牺牲了一点查询效率换来的是插入删除时最多只需要两次旋转整体吞吐量更高。这背后是一个永恒的设计哲学任何数据结构都不是追求单点最优而是在读写之间找平衡。HashMap选红黑树而不是AVL树本质上也是这个原因。图方面考研数据结构408里图和数组的关系是重点——邻接矩阵是二维数组邻接表是数组链表。BFS的代码套路和树的层序一模一样DFS则是递归的经典应用和树的递归遍历同构。如果树的遍历掌握了图的遍历其实是个顺带的事。5. 排序算法从冒泡到快排理解比背代码重要热搜词里“冒泡排序java”、“java排序”、“排序算法”都是高频搜索显然大家最愁的就是这块。5.1 冒泡排序为什么总被当反面教材冒泡排序的代码每个Java初学者都写过public static void bubbleSort(int[] arr) { for (int i 0; i arr.length - 1; i) { boolean swapped false; for (int j 0; j arr.length - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) break; // 优化没发生交换说明已有序 } }很多人背下来了但不知道为什么用j arr.length - 1 - i这个边界。其实很简单每轮内循环结束后最大的数已经“冒泡”到末尾下一轮就不用管它了所以减去i。加了一个swapped标志位后如果某一轮没有任何交换说明整个数组已经有序提前退出这种优化让最好情况复杂度降到O(n)。面试考冒泡的目的通常不是让你展示性能而是考察基本功和优化意识。能写出“标志位优化”版本的已经超过一半候选人。5.2 快排平均O(nlogn)但最坏O(n²)快速排序是面试手撕的高频题核心思想是分治选一个基准值pivot把小于它的放左边大于它的放右边然后递归处理左右两边。public static void quickSort(int[] arr, int left, int right) { if (left right) return; int pivot partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot 1, right); } private static int partition(int[] arr, int left, int right) { int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; arr[i] arr[j]; while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; return i; }这个单边挖坑法的partition需要重点理解先保存基准值然后把坑填给基准值的位置最后基准值归位。快排的关键问题是基准值怎么选。如果每次选最左端而数组已经有序那么每次分区都极端不均匀递归深度变成n时间复杂度退化成O(n²)。所以工业级快排会用“三数取中”或“随机选基准”来规避这种情况。JDK里的Arrays.sort()对于基本类型用的是DualPivotQuicksort双基准快排对于对象类型用的是TimSort这本身又是一段值得挖的源码故事。5.3 排序算法复杂度全景对照算法平均时间复杂度最坏时间复杂度空间复杂度稳定性核心思想冒泡排序O(n²)O(n²)O(1)稳定相邻交换选择排序O(n²)O(n²)O(1)不稳定每轮选最小插入排序O(n²)O(n²)O(1)稳定扑克牌插法希尔排序O(n^1.3)O(n²)O(1)不稳定分组插入归并排序O(nlogn)O(nlogn)O(n)稳定分治合并快速排序O(nlogn)O(n²)O(logn)不稳定分区递归堆排序O(nlogn)O(nlogn)O(1)不稳定堆调整Arrays.sort(对象)O(nlogn)O(nlogn)O(n)稳定TimSort面试时如果被打乱要求写两个排序一个快排一个归并基本够用。归并排序的“合并两个有序数组”思想还会在“合并K个有序链表”这类题里再次出现所以值得认真写一遍。6. 进阶联想从数据结构笔记到实战决策6.1 数据结构选择题背后的业务逻辑笔记看到这里最该形成的能力不是背出每个结构的时间复杂度而是在拿到一个业务需求时能下意识地问一句这里的数据形态是什么读写比例如何几个实战例子排行榜场景需要按分数排序且频繁增删改查可以选TreeMap或PriorityQueue优先队列本质是堆。IP黑名单/关键词过滤前缀匹配用Trie前缀树Java里用HashMap嵌套也能实现但内存和效率都差一个量级。最近浏览历史固定大小窗口的数据流用环形数组ArrayDeque或者LinkedHashMap实现LRU。6.2 优先队列PriorityQueue被忽视的实用结构PriorityQueue底层是二叉堆不是队列。它保证每次poll出来的都是当前最小或最大的元素时间复杂度O(logn)。// 求数据流中第K大的元素 PriorityQueueInteger minHeap new PriorityQueue(); // 默认小顶堆 for (int num : nums) { minHeap.offer(num); if (minHeap.size() k) { minHeap.poll(); // 弹掉最小的堆顶就是第K大 } }这个套路在“前K个高频元素”“合并K个有序链表”里反复出现。堆排序能排O(nlogn)和快排一样看笔记时值得亲手实现一次siftUp和siftDown理解为什么调整堆只需要O(logn)。6.3 面试答题的结构感最后分享一个面试中回答数据结构问题的通用框架这也是我自己做面试官时判断候选人“真懂还是背题”的参考依据先给本质这个结构解决什么问题底层是用什么实现的数组、链表、树还是哈希。再给复杂度核心操作的时间、空间复杂度是多少为什么。然后给对比和同类结构比优势劣势是什么选它的理由是什么。最后给场景真实项目中哪里用到了它或者手撕一道相关题目证明真的会用。比如问“ArrayList和LinkedList的区别”光说“数组vs链表、查询快vs增删快”只能算及格。能把“扩容机制”“CPU缓存命中”“ArrayDeque替代方案”“迭代器增删场景”串起来讲的才是真正理解了这个结构。数据结构的价值从来不是记住一个结论而是理解一种权衡而这份笔记最重要的作用就是帮你把权衡背后的逻辑链条打通。
1. 先想明白数据结构在Java里到底是什么做Java开发三五年的人跳槽面试时被问“HashMap为什么线程不安全”“ArrayList和LinkedList什么时候选谁”十有八九会一愣——不是不会是平时写业务代码根本用不到这些细究。但数据结构这个东西恰恰是区分“CRUD熟练工”和“真正理解程序运行逻辑”的分水岭。我自己的体会是数据结构在Java里从来不是一门孤立的课程它藏在三个层面里JDK源码层ArrayList、LinkedList、HashMap、TreeMap这些日常容器每一个都是某种经典数据结构的工业级实现封装了细节但保留了本质。算法应用层排序、二分查找、递归、遍历这些面试手撕题和数据机构408考研题考的其实是“你知不知道在什么场景下选什么结构”。系统设计层缓存淘汰LRU要LinkedHashMap路由表要前缀树任务调度要优先队列——这些都是在真实项目里验证数据结构价值的地方。所以这份笔记我不会从头讲“什么是数组”这种教科书内容而是用“面试源码实战”三合一的视角把Java里最核心的几类数据结构串一遍。适合准备Java面试的人、考研408复习的人以及写了一段时间业务代码但感觉技术深度见顶的开发者。2. 数组与链表ArrayList和LinkedList之争本质是内存布局之争2.1 先看JDK源码怎么选型很多初学者背过“数组查询快、增删慢链表增删快、查询慢”但真正问一句“为什么”能讲清楚的没几个。以ArrayList为例它的底层就是一个Object[]数组初始容量10满了之后扩容到1.5倍oldCapacity (oldCapacity 1)。数组在内存里是连续存储的所以通过下标访问能做到O(1)时间复杂度因为可以直接用“起始地址 下标 × 元素大小”算出内存地址。这就像电影院座位号你告诉我第几排第几座我直接算出位置不用一个一个数。LinkedList则是一个双向链表每个节点Node持有prev和next两个引用。插入删除确实快只要改前后节点的指针就行O(1)。但查找第n个元素时得从头或尾开始一个个遍历O(n)。这就像一根绳子上串了一串珠子你想拿第50颗珠子只能一颗一颗数过去。但有个细节很多人忽略LinkedList的“增删快”是有前提的——前提是你已经持有那个位置的节点引用比如迭代器所在位置。如果你要list.add(index, element)ArrayList因为要System.arraycopy移动元素确实慢但LinkedList也要先node(index)遍历到那个位置两个都是O(n)只是常数不同。2.2 实际开发里的选择建议我自己的经验日常业务代码里90%的场景用ArrayList原因很简单遍历为主遍历数组的缓存命中率远高于链表连续内存对CPU缓存友好链路节点分散容易cache miss。内存占用链表每个节点要额外存两个引用16字节左右的开销数据量大了差别很明显。新增操作如果是“追加到末尾”ArrayList的扩容均摊下来也是O(1)。LinkedList适合什么场景高频在头部插入删除或者需要频繁在迭代过程中增删元素用ListIterator。比如实现一个LRU缓存时LinkedHashMap底层就是哈希表双向链表这个组合是经典中的经典。Java还提供了一个容易被忽视的ArrayDeque这个类同时实现了栈和队列的功能而且性能比LinkedList做栈队列还要好因为环形数组没有节点开销。后面讲栈和队列时会再提它。// 模拟ArrayList扩容逻辑简化版 public boolean add(E e) { ensureCapacityInternal(size 1); elementData[size] e; return true; } private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍扩容 elementData Arrays.copyOf(elementData, newCapacity); }提示面试时如果能说出“扩容是1.5倍、初始容量是10、用Arrays.copyOf拷贝”再加一句“频繁扩容会触发GC压力所以预估数据量大时可以new ArrayList(capacity)”面试官基本就能确认你是真看过源码的。3. 栈、队列与哈希表高频考点的底层逻辑3.1 栈和队列别再用Stack类了Java的Stack类是个历史遗留设计它继承自Vector所有方法都加了synchronized锁性能低而且Vector底层是数组扩容逻辑和ArrayList一样。现代Java写栈和队列推荐用ArrayDequeDequeString stack new ArrayDeque(); stack.push(a); // 入栈 String top stack.peek(); // 看栈顶不弹出 String pop stack.pop(); // 出栈 DequeString queue new ArrayDeque(); queue.offer(a); // 入队 String head queue.peek(); // 看队头 String poll queue.poll(); // 出队ArrayDeque底层是循环数组head和tail两个指针容量按2的幂增长。用数组实现栈队列的经典套路比链表版省内存、更快。这里也埋了个考点为什么ArrayDeque容量必须是2的幂因为取模运算(tail 1) (elements.length - 1)比%高效得多这是位运算在数据结构里的典型应用。栈的应用场景面试必问括号匹配、表达式求值、函数调用栈、浏览器的前进后退。队列的场景生产者消费者、消息队列、BFS广度优先遍历。这些都属于“结构本身很简单但应用极其广泛”的类型。3.2 HashMapJava数据结构面试的头号热门HashMap是面试重灾区它底层结构在JDK 7和JDK 8之间有一次关键演进JDK 7数组 链表头插法JDK 8数组 链表 红黑树尾插法链表长度超过8且数组长度达到64时转红黑树为什么要加红黑树因为极端hash冲突下链表会退化成长链表查询退化成O(n)。红黑树能保证最坏O(logn)。但为什么不直接用树因为树节点TreeNode是普通Node内存占用的两倍左右只在链表确实太长时才转。几个必问的点为什么HashMap线程不安全并发put可能导致数据覆盖、扩容时形成环形链表JDK 7虽然JDK 8改成尾插法解决了环形链表问题但覆盖问题依然存在。所以并发场景用ConcurrentHashMap。为什么容量是2的幂为了让hash (n - 1)等价于hash % n同时位运算更快。扩容时元素要么留在原位置要么移动到“原位置旧容量”的位置这样重hash效率极高。负载因子为什么是0.75这是时间空间的一个折中。负载因子越大空间利用率高但冲突概率增大查询变慢负载因子越小浪费空间但查询快。0.75是Java官方大量测试得出的平衡点。// HashMap的hash扰动函数JDK 8 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }这段代码的意思是把hashCode的高16位和低16位做异或让高位的特征也参与到低位运算中降低hash冲突的概率。主要因为数组默认才16位长度直接取模只用了低几位高位特征就浪费了。3.3 LinkedHashMap与TreeMap两个被低估的选手LinkedHashMap在HashMap基础上加了一条双向链表维护插入顺序或者访问顺序。设了accessOrder true之后每次get都会把节点移到链表尾部这天然就是LRU缓存的雏形。很多面试题让手写LRU最简解法就是继承LinkedHashMap并重写removeEldestEntry。TreeMap底层是红黑树key有序支持范围查询subMap、headMap、tailMap。如果业务上需要按key排序或者需要找“最接近某个值的key”ceilingKey/floorKeyTreeMap比遍历HashMap再排序高效得多。4. 树与图二叉树、红黑树到图的遍历链路排除法看的话Java生态里用得最多的树是二叉树家族而算法题里考得最狠的也是二叉树。从数据结构笔记的角度真正需要掌握的是这条链路普通二叉树 → 二叉搜索树BST→ 平衡二叉树AVL→ 红黑树 → 多路搜索树B树/B树。4.1 二叉树的遍历递归和迭代都要会前序、中序、后序、层序这四种遍历是树的基础。递归写法背三行就能写出来但面试如果只让写递归就落了下乘。真正的考点是用栈模拟递归实现前中后序遍历用队列实现层序遍历。一个记忆技巧前序遍历根左右用栈时先压右子节点再压左子节点中序遍历左根右要一路向左压栈弹出来之后处理右子树后序遍历左右根最绕可以用两个栈或者一个栈加prev变量标记。// 迭代实现二叉树的中序遍历 public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); DequeTreeNode stack new ArrayDeque(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { while (cur ! null) { stack.push(cur); cur cur.left; // 一路向左 } cur stack.pop(); result.add(cur.val); // 弹出来时访问 cur cur.right; // 处理右子树 } return result; }层序遍历BFS更简单一个队列就搞定每次循环先取当前层的size然后pop这一层所有节点同时把下一层入队。这个套路也是“树的层次统计”“二叉树最大宽度”等题的基础。4.2 为什么是红黑树而不是AVL树一定有人好奇HashMap的树化、TreeMap底层都是红黑树为什么不是AVL平衡树AVL树是严格平衡的任意节点的左右子树高度差不超过1。查询确实快O(logn)最稳定。问题在于为了维持这种严格平衡插入删除时可能要频繁旋转一次插入可能引发多次旋转导致写操作开销大。红黑树的平衡标准放宽了从根到叶子的最远路径不超过最短路径的2倍也就是“黑色节点数相同红色节点不连续”。它牺牲了一点查询效率换来的是插入删除时最多只需要两次旋转整体吞吐量更高。这背后是一个永恒的设计哲学任何数据结构都不是追求单点最优而是在读写之间找平衡。HashMap选红黑树而不是AVL树本质上也是这个原因。图方面考研数据结构408里图和数组的关系是重点——邻接矩阵是二维数组邻接表是数组链表。BFS的代码套路和树的层序一模一样DFS则是递归的经典应用和树的递归遍历同构。如果树的遍历掌握了图的遍历其实是个顺带的事。5. 排序算法从冒泡到快排理解比背代码重要热搜词里“冒泡排序java”、“java排序”、“排序算法”都是高频搜索显然大家最愁的就是这块。5.1 冒泡排序为什么总被当反面教材冒泡排序的代码每个Java初学者都写过public static void bubbleSort(int[] arr) { for (int i 0; i arr.length - 1; i) { boolean swapped false; for (int j 0; j arr.length - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) break; // 优化没发生交换说明已有序 } }很多人背下来了但不知道为什么用j arr.length - 1 - i这个边界。其实很简单每轮内循环结束后最大的数已经“冒泡”到末尾下一轮就不用管它了所以减去i。加了一个swapped标志位后如果某一轮没有任何交换说明整个数组已经有序提前退出这种优化让最好情况复杂度降到O(n)。面试考冒泡的目的通常不是让你展示性能而是考察基本功和优化意识。能写出“标志位优化”版本的已经超过一半候选人。5.2 快排平均O(nlogn)但最坏O(n²)快速排序是面试手撕的高频题核心思想是分治选一个基准值pivot把小于它的放左边大于它的放右边然后递归处理左右两边。public static void quickSort(int[] arr, int left, int right) { if (left right) return; int pivot partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot 1, right); } private static int partition(int[] arr, int left, int right) { int pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; arr[i] arr[j]; while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; return i; }这个单边挖坑法的partition需要重点理解先保存基准值然后把坑填给基准值的位置最后基准值归位。快排的关键问题是基准值怎么选。如果每次选最左端而数组已经有序那么每次分区都极端不均匀递归深度变成n时间复杂度退化成O(n²)。所以工业级快排会用“三数取中”或“随机选基准”来规避这种情况。JDK里的Arrays.sort()对于基本类型用的是DualPivotQuicksort双基准快排对于对象类型用的是TimSort这本身又是一段值得挖的源码故事。5.3 排序算法复杂度全景对照算法平均时间复杂度最坏时间复杂度空间复杂度稳定性核心思想冒泡排序O(n²)O(n²)O(1)稳定相邻交换选择排序O(n²)O(n²)O(1)不稳定每轮选最小插入排序O(n²)O(n²)O(1)稳定扑克牌插法希尔排序O(n^1.3)O(n²)O(1)不稳定分组插入归并排序O(nlogn)O(nlogn)O(n)稳定分治合并快速排序O(nlogn)O(n²)O(logn)不稳定分区递归堆排序O(nlogn)O(nlogn)O(1)不稳定堆调整Arrays.sort(对象)O(nlogn)O(nlogn)O(n)稳定TimSort面试时如果被打乱要求写两个排序一个快排一个归并基本够用。归并排序的“合并两个有序数组”思想还会在“合并K个有序链表”这类题里再次出现所以值得认真写一遍。6. 进阶联想从数据结构笔记到实战决策6.1 数据结构选择题背后的业务逻辑笔记看到这里最该形成的能力不是背出每个结构的时间复杂度而是在拿到一个业务需求时能下意识地问一句这里的数据形态是什么读写比例如何几个实战例子排行榜场景需要按分数排序且频繁增删改查可以选TreeMap或PriorityQueue优先队列本质是堆。IP黑名单/关键词过滤前缀匹配用Trie前缀树Java里用HashMap嵌套也能实现但内存和效率都差一个量级。最近浏览历史固定大小窗口的数据流用环形数组ArrayDeque或者LinkedHashMap实现LRU。6.2 优先队列PriorityQueue被忽视的实用结构PriorityQueue底层是二叉堆不是队列。它保证每次poll出来的都是当前最小或最大的元素时间复杂度O(logn)。// 求数据流中第K大的元素 PriorityQueueInteger minHeap new PriorityQueue(); // 默认小顶堆 for (int num : nums) { minHeap.offer(num); if (minHeap.size() k) { minHeap.poll(); // 弹掉最小的堆顶就是第K大 } }这个套路在“前K个高频元素”“合并K个有序链表”里反复出现。堆排序能排O(nlogn)和快排一样看笔记时值得亲手实现一次siftUp和siftDown理解为什么调整堆只需要O(logn)。6.3 面试答题的结构感最后分享一个面试中回答数据结构问题的通用框架这也是我自己做面试官时判断候选人“真懂还是背题”的参考依据先给本质这个结构解决什么问题底层是用什么实现的数组、链表、树还是哈希。再给复杂度核心操作的时间、空间复杂度是多少为什么。然后给对比和同类结构比优势劣势是什么选它的理由是什么。最后给场景真实项目中哪里用到了它或者手撕一道相关题目证明真的会用。比如问“ArrayList和LinkedList的区别”光说“数组vs链表、查询快vs增删快”只能算及格。能把“扩容机制”“CPU缓存命中”“ArrayDeque替代方案”“迭代器增删场景”串起来讲的才是真正理解了这个结构。数据结构的价值从来不是记住一个结论而是理解一种权衡而这份笔记最重要的作用就是帮你把权衡背后的逻辑链条打通。
