title: 数据结构与算法
tags: [算法, 数据结构, LeetCode, 2026高频]
created: 2026-05-31
数据结构与算法 — 20K后端必考专题
20K Java后端面试的算法要求:LeetCode中等难度、能手写、能分析复杂度、能关联实际场景。
不是ACM竞赛级别,但也不能只会CRUD。
一、数组与链表
Q001. 如何实现一个LRU缓存?要求get和put都是O(1)
难度:★★★★☆
答案要点:
- HashMap + 双向链表,HashMap存key→Node映射实现O(1)查找
- 双向链表维护访问顺序,最近访问的移到头部,淘汰尾部
- get操作:查找→删除原位置→移到头部;put操作:新元素插头部,超容量时删尾部
- Java中LinkedHashMap已经内置LRU能力:设置accessOrder=true + 重写removeEldestEntry
- 后端场景:Redis的LRU淘汰策略就是这个原理的变体;Guava Cache的expireAfterAccess也是基于访问顺序
Q002. 反转链表(迭代和递归两种方式)
难度:★★☆☆☆
答案要点:
- 迭代:三个指针prev/curr/next,遍历过程中逐个翻转指向,时间O(n)空间O(1)
- 递归:递归到末尾,返回过程中翻转指向,时间O(n)空间O(n)(递归栈)
- 边界处理:空链表、只有一个节点
- 后端场景:链表反转是链表操作的基础,很多高级题(K个一组翻转、回文链表)都依赖这个操作
Q003. 合并两个有序链表
难度:★★☆☆☆
答案要点:
- 双指针分别遍历两个链表,每次取较小的节点接入结果链表,时间O(m+n)
- 用虚拟头节点(dummy)简化头节点处理逻辑
- 递归写法:比较头节点,较小的next指向递归合并剩余部分的结果
- 后端场景:归并排序的合并步骤;多路归并用于外部排序(大文件排序)、多个有序数据源合并
Q004. 如何检测链表中是否有环?找出环的入口节点
难度:★★★☆☆
答案要点:
- 快慢指针法:slow走一步fast走两步,相遇则有环,时间O(n)空间O(1)
- 找环入口:相遇后,一个指针从head出发,一个从相遇点出发,再次相遇即为入口
- 数学证明:设head到入口为a,入口到相遇为b,环长c,则a = (k-1)c + (c-b)
- 后端场景:检测循环依赖(如Spring Bean的循环引用检测)、死锁检测中的环路判断
Q005. 删除链表的倒数第N个节点
难度:★★★☆☆
答案要点:
- 双指针法:fast先走N步,然后slow和fast同步走,fast到末尾时slow指向待删节点的前驱
- 用dummy节点处理删除头节点的边界情况
- 一次遍历完成,时间O(n)空间O(1)
- 后端场景:日志链表中删除旧条目、消息队列中按偏移量删除
Q006. 两数之和(返回数组中两个数的下标,使它们的和等于目标值)
难度:★★☆☆☆
答案要点:
- HashMap一次遍历:遍历时查询target-nums[i]是否已在map中,时间O(n)空间O(n)
- 暴力法双重循环O(n²)不推荐
- 注意:要先查询再put,避免同一元素被使用两次
- 后端场景:哈希查找是最常用的优化手段,对应数据库中Hash索引的思想;电商中"找凑单商品"就是两数之和的变体
二、栈与队列
Q007. 有效的括号(判断括号字符串是否合法)
难度:★★☆☆☆
答案要点:
- 栈:遇到左括号入栈,遇到右括号弹出栈顶比对是否匹配
- 三种不合法情况:左右不匹配、栈空时遇到右括号、遍历完栈非空
- 时间O(n),空间O(n)
- 后端场景:JSON/XML解析器中的括号匹配、表达式求值、SQL解析中的语法校验
Q008. 实现一个最小栈(push/pop/getMin都是O(1))
难度:★★★☆☆
答案要点:
- 辅助栈:一个主栈存数据,一个辅助栈同步存储当前最小值
- push时:辅助栈push min(当前值, 辅助栈顶);pop时两栈同步pop
- 时间O(1),空间O(n)
- 后端场景:监控系统中的滑动窗口最小值查询、限流器中维护时间窗口内的最小请求间隔
Q009. 用栈实现队列(两个栈模拟FIFO)
难度:★★★☆☆
答案要点:
- 两个栈:input栈负责push,output栈负责pop/peek
- pop时如果output为空,把input全部倒入output再弹出
- 均摊时间复杂度O(1)(每个元素最多被转移两次)
- 后端场景:理解栈和队列的关系;消息队列的底层实现可能用到类似思路;理解均摊分析
Q010. 滑动窗口最大值
难度:★★★★☆
答案要点:
- 单调递减双端队列:队列存储下标,维护队列中对应值单调递减
- 遍历时:移除队首过期元素(下标超出窗口),移除队尾小于当前值的元素
- 每个元素最多入队出队各一次,时间O(n)
- 后端场景:滑动窗口限流(如每分钟最多100次请求)、实时数据流中的窗口聚合统计、股票行情中的移动最大值
三、哈希表
Q011. 三数之和(找出数组中和为0的三元组,要求不重复)
难度:★★★★☆
答案要点:
- 排序 + 双指针:固定第一个数,在剩余区间用左右指针夹逼,时间O(n²)
- 去重关键:排序后跳过重复元素(i去重、left/right去重)
- 不能用HashMap做三数之和(去重困难,且排序+双指针更优雅)
- 后端场景:组合搜索、数据匹配问题;面试高频题,考察排序和双指针的综合运用
Q012. 字母异位词分组(将字符串数组按字母异位词分组)
难度:★★★☆☆
答案要点:
- 方法一:排序每个字符串作为key,HashMap分组,时间O(n·klogk)(k为字符串长度)
- 方法二:用26字母计数数组转字符串作为key,时间O(n·k)
- HashMap的key设计是核心:如何将"相同字母不同排列"映射到同一个key
- 后端场景:数据清洗中的重复检测、用户输入归一化、搜索引擎中的query归一化处理
Q013. Top-K频繁元素(返回数组中出现频率前K高的元素)
难度:★★★☆☆
答案要点:
- 方法一:HashMap统计频率 + 小顶堆(PriorityQueue)维护Top-K,时间O(nlogk)
- 方法二:HashMap统计频率 + 桶排序(频率作为下标),时间O(n)
- 方法三:快速选择算法(QuickSelect),平均O(n)
- 后端场景:热搜排行榜(微博热搜、电商热销榜)、日志中Top-K异常IP统计、Redis的Top-K数据结构
Q014. 最长连续序列(在未排序数组中找最长连续元素序列的长度,要求O(n))
难度:★★★★☆
答案要点:
- HashSet存储所有元素,遍历时只从"序列起点"开始向后扩展
- 判断起点:num-1不在set中,说明num是某个连续序列的起点
- 每个元素最多被访问两次,时间O(n)空间O(n)
- 后端场景:用户连续登录天数统计、事件链分析、数据流中的连续性检测
四、二叉树
Q015. 二叉树的层序遍历(逐层从左到右输出)
难度:★★☆☆☆
答案要点:
- BFS用队列实现:每层节点入队,逐层处理,用size控制每层的节点数
- 时间O(n),空间O(最大层宽)
- 变体:自底向上层序遍历(结果reverse)、锯齿形遍历(奇偶层方向交替)
- 后端场景:组织架构树的层级遍历、文件系统目录遍历、消息广播的层级推送
Q016. 二叉树的最大深度
难度:★☆☆☆☆
答案要点:
- 递归(DFS):max(depth(left), depth(right)) + 1,时间O(n)
- 迭代(BFS):层序遍历计数层数
- 迭代(DFS):用栈模拟递归,栈元素附带深度信息
- 后端场景:树形结构深度的基本操作,是很多树题的基础(判断平衡树、最小深度等依赖同样的遍历思路)
Q017. 翻转二叉树(镜像翻转)
难度:★★☆☆☆
答案要点:
- 递归:交换左右子节点,递归翻转左右子树,时间O(n)
- 迭代:层序遍历,每个节点交换左右子节点
- 这就是著名的"Homebrew作者Google面试被拒"的那道题
- 后端场景:决策树翻转、表达式树变换;考察递归思维的直觉性
Q018. 二叉树的最近公共祖先
难度:★★★★☆
答案要点:
- 递归:如果当前节点是p或q则返回当前节点;左右子树分别查找
- 如果左右子树各找到一个,当前节点就是LCA;如果只有一边找到,向上传递
- 时间O(n),空间O(h)(h为树高)
- 有parent指针的变体:转化为链表交叉问题(两个指针分别走完自己的链再走对方的链)
- 后端场景:Git合并提交的公共祖先查找、文件系统的最近公共目录、DOM树的公共父节点
Q019. 二叉树的序列化与反序列化
难度:★★★★☆
答案要点:
- 前序遍历序列化:用null占位(如"1,2,null,null,3,4,null,null,5,null,null")
- 反序列化:用队列或索引逐个恢复,遇到null就返回null子树
- 也可以用层序遍历实现
- 时间O(n),空间O(n)
- 后端场景:树形数据的持久化存储、RPC传输中的对象序列化、JSON树结构的编解码
五、二叉搜索树(BST)
Q020. 验证一棵二叉树是否是合法的BST
难度:★★★☆☆
答案要点:
- 中序遍历判断是否严格递增(BST中序遍历一定有序)
- 递归传递上下界:每个节点的值必须在(min, max)范围内,时间O(n)
- 常见坑:不能只比较节点和左右子节点,必须保证右子树所有节点都大于根
- 后端场景:数据校验(验证有序性)、索引合法性检查
Q021. BST中第K小的元素
难度:★★★☆☆
答案要点:
- 中序遍历:BST中序遍历就是有序序列,第K个即为答案,时间O(k)
- 优化:可在节点中维护左子树节点数(size字段),实现O(h)查找
- 后端场景:排名查询(如数据库ORDER BY + LIMIT的索引实现原理)、排行榜中查找第K名
Q022. BST中范围搜索(给定范围[low, high],返回所有满足条件的节点值)
难度:★★★☆☆
答案要点:
- 中序遍历剪枝:当前节点小于low则只搜右子树,大于high则只搜左子树
- 在范围内则加入结果,并搜索左右子树
- 时间O(n)最坏,但剪枝后平均远小于O(n)
- 后端场景:数据库范围查询的B+树索引原理、时间范围筛选、价格区间搜索
六、排序算法
Q023. 快速排序的原理和实现?最坏情况如何避免?
难度:★★★★☆
答案要点:
- 分治:选pivot,分区(小于pivot放左,大于放右),递归排序子数组
- 时间:平均O(nlogn),最坏O(n²)(已排序数组+每次选第一个作pivot)
- 避免最坏:随机选pivot、三数取中法
- 不稳定排序(交换可能改变相等元素的相对顺序)
- 后端场景:Java的Arrays.sort()对基本类型用双轴快排(Dual-Pivot Quicksort)
Q024. 归并排序的原理?为什么它是稳定排序?
难度:★★★★☆
答案要点:
- 分治:递归拆分成单个元素,然后两两合并有序子数组
- 时间O(nlogn)(所有情况),空间O(n)(需要辅助数组)
- 稳定:合并时遇到相等元素,先放左子数组的,保证相对顺序不变
- 后端场景:Java的Arrays.sort()对对象类型用TimSort(归并+插入排序的优化);外部排序(大文件无法全部装入内存时)
Q025. 堆排序的原理?如何用堆实现Top-K?
难度:★★★★☆
答案要点:
- 先建最大堆(O(n)),然后反复取出堆顶并调整堆,时间O(nlogn),空间O(1)
- 建堆:从最后一个非叶节点开始,自底向上siftDown
- Top-K:维护大小为K的小顶堆,遍历时比堆顶大就替换,时间O(nlogk)
- 不稳定排序
- 后端场景:Java的PriorityQueue底层就是堆;任务调度(定时任务优先队列)、大数据Top-K查询
Q026. Java中Arrays.sort()和Collections.sort()分别用什么排序算法?
难度:★★★☆☆
答案要点:
- Arrays.sort()基本类型:Dual-Pivot Quicksort(双轴快排),不稳定但快
- Arrays.sort()对象类型:TimSort(归并+插入排序优化),稳定
- Collections.sort()内部调用Arrays.sort()(先将List转为数组),也是TimSort
- TimSort:利用数据中已有的有序片段(run),合并时效率更高,最好情况O(n)
- 后端场景:选择排序算法要考虑稳定性需求;理解JDK排序实现有助于性能调优
七、二分查找
Q027. 标准二分查找及其变体(查找第一个/最后一个等于目标的位置)
难度:★★★☆☆
答案要点:
- 基础二分:left=0, right=n-1,mid=(left+right)/2,时间O(logn)
- 查找第一个等于target:nums[mid]>=target时right=mid,最终检查nums[left]==target
- 查找最后一个等于target:nums[mid]>target时right=mid,等于时left=mid+1
- 防溢出:mid = left + (right - left) / 2
- 后端场景:数据库B+树索引查找、有序数组中的范围查询、日志文件中按时间二分查找
Q028. 搜索旋转排序数组(无重复元素)
难度:★★★★☆
答案要点:
- 二分查找变体:mid将数组分成两段,一段有序一段包含旋转点
- 判断哪段有序:如果nums[left]<=nums[mid]则左段有序
- 根据target是否在有序段来决定搜索方向
- 时间O(logn)
- 有重复元素时最坏O(n)(无法判断哪段有序时需线性扫描)
- 后端场景:二分思维的考察重点——不是死记模板,而是理解"每次排除一半"的核心思想
Q029. 在排序数组中查找元素的第一个和最后一个位置
难度:★★★☆☆
答案要点:
- 两次二分:一次找左边界(第一个>=target),一次找右边界(最后一个<=target)
- 左边界:nums[mid]>=target时right=mid-1,最终left即为第一个>=target的位置
- 右边界:nums[mid]<=target时left=mid+1,最终right即为最后一个<=target的位置
- 时间O(logn)
- 后端场景:数据库范围扫描的起点定位、日志中按时间范围定位起始位置、统计某个值的频次(right-left+1)
八、动态规划
Q030. 爬楼梯(每次可以爬1或2阶,到达第n阶有多少种方法)
难度:★★☆☆☆
答案要点:
- dp[i] = dp[i-1] + dp[i-2],到达第i阶的方法=从i-1阶走1步 + 从i-2阶走2步
- 初始条件:dp[1]=1, dp[2]=2
- 空间优化:只需两个变量滚动,空间O(1)
- 本质就是斐波那契数列
- 后端场景:动态规划入门题;理解"状态定义→转移方程→初始条件"的分析框架,后续背包、子序列等题都遵循同样思路
Q031. 0-1背包问题(N个物品,容量为W的背包,求最大价值)
难度:★★★★☆
答案要点:
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]),选或不选第i个物品
- 空间优化:一维数组,j从大到小遍历(防止同一物品被重复选)
- 变体:完全背包(物品无限,j从小到大遍历)、多重背包
- 时间O(N·W),空间O(W)
- 后端场景:资源分配问题、服务器容量规划、优惠券最优组合选择
Q032. 最长递增子序列(LIS)
难度:★★★★☆
答案要点:
- 方法一:dp[i]表示以nums[i]结尾的LIS长度,dp[i]=max(dp[j]+1)其中nums[j]<nums[i],时间O(n²)
- 方法二:贪心+二分维护tail数组,tail[i]表示长度为i+1的LIS的最小末尾元素,时间O(nlogn)
- 方法二的tail数组严格递增,因此可以用二分查找
- 后端场景:最长递增子序列在数据流分析中有应用;面试常考,重点掌握O(nlogn)解法
Q033. 买卖股票的最佳时机(含多种变体)
难度:★★★★☆
答案要点:
- 只能买卖一次:遍历时维护最低价格,更新最大利润,时间O(n)
- 可以买卖多次(不限次数):所有上涨段都买,贪心即可
- 最多买卖两次:两次遍历分别求左半段最大利润和右半段最大利润,再合并
- 通用DP框架:dp[i][k][0/1]表示第i天、交易k次、持有/不持有的最大利润
- 后端场景:DP状态机思想可类比有限状态机(订单状态流转);限流策略也可用DP思路
九、贪心算法
Q034. 跳跃游戏(判断能否到达最后一个位置 / 最少跳跃次数)
难度:★★★☆☆
答案要点:
- 判断能否到达:贪心维护当前能到达的最远位置maxReach,遍历时更新;若i>maxReach则不可达
- 最少跳跃次数:维护当前跳跃范围的边界end和最远可达位置farthest,遍历到end时跳跃次数+1
- 时间O(n),空间O(1)
- 后端场景:贪心思想——每步做局部最优选择;网络路由的最短跳数、任务链的最少步骤
Q035. 无重叠区间(最少删除多少个区间使剩余区间不重叠) / 会议室问题
难度:★★★★☆
答案要点:
- 按区间右端点排序,贪心选择结束最早的区间(留给后面的空间最大)
- 遍历时如果当前区间起点>=上一个选中区间的终点,则选中
- 需要删除的数量 = 总数 - 最多能保留的数量
- 时间O(nlogn)(排序)
- 后端场景:会议室预订系统、资源调度(服务器时间段分配)、航班/酒店排期的区间冲突检测
Q036. 分发糖果(每个孩子至少一颗,评分高的比相邻孩子多)
难度:★★★★☆
答案要点:
- 两次遍历:从左到右保证右边评分高则糖果多,从右到左保证左边评分高则糖果多
- 取两次遍历结果的max
- 时间O(n),空间O(n)
- 后端场景:理解贪心中"双向约束"的处理方式;资源分配中的公平性问题
十、回溯算法
Q037. 全排列(给定不重复的数组,返回所有排列)
难度:★★★☆☆
答案要点:
- 回溯:维护path和used数组,每层选择一个未使用的数字加入path
- 递归树:n!个叶子节点,每个排列长度为n
- 时间O(n·n!),空间O(n)(递归深度)
- 有重复元素时:排序 + 同层剪枝(used[i-1]==false && nums[i]==nums[i-1]则跳过)
- 后端场景:回溯是暴力搜索的框架;排列组合问题在调度、配置生成中有应用
Q038. N皇后问题
难度:★★★★★
答案要点:
- 逐行放置皇后,每列、对角线、反对角线不能冲突
- 用Set或数组记录已占用的列、对角线(row-col相同)、反对角线(row+col相同)
- 回溯:放一个皇后后递归下一行,冲突则回退
- 时间复杂度:O(n!),空间O(n)
- 后端场景:回溯算法的经典考察;约束满足问题(CSP),在调度、资源分配中有类似思路
Q039. 组合总和(候选数组中找出所有和为target的组合,可重复选取)
难度:★★★☆☆
答案要点:
- 回溯 + 剪枝:排序后,每层从start开始选择(允许重复选当前元素)
- 剪枝:如果当前选择后剩余sum < 0则直接跳过后续(排序保证后续更大)
- 时间:指数级(最坏O(2^target))
- 后端场景:组合搜索、商品凑单问题、路径搜索中的剪枝优化思想
十一、图论基础
Q040. 图的BFS和DFS遍历
难度:★★★☆☆
答案要点:
- BFS:队列实现,适合求最短路径(无权图)、层序遍历
- DFS:栈或递归实现,适合连通性检测、路径搜索、环检测
- 邻接表vs邻接矩阵:稀疏图用邻接表O(V+E),稠密图用邻接矩阵O(V²)
- 后端场景:社交网络的好友推荐(BFS扩散)、依赖分析(DFS)、爬虫的URL遍历
Q041. 拓扑排序(课程表问题:能否完成所有课程)
难度:★★★★☆
答案要点:
- Kahn算法(BFS):计算入度,入度为0的入队,依次移除并减小邻居入度
- 如果最终所有节点都被处理则无环,否则存在环(无法完成拓扑排序)
- DFS实现:后序遍历的逆序即为拓扑序列
- 时间O(V+E)
- 后端场景:Spring Bean的依赖注入顺序(Bean依赖关系是有向图,需按拓扑顺序初始化)、构建系统的编译顺序、DAG任务编排(如Airflow任务调度)
Q042. Dijkstra最短路径算法
难度:★★★★☆
答案要点:
- 贪心 + 优先队列:每次取距离最短的未访问节点,更新其邻居的最短距离
- 时间O((V+E)logV)(优先队列),不适用于负权边
- 朴素实现O(V²)适合稠密图
- 后端场景:路由算法、地图导航、网络延迟时间计算(LeetCode 743题)、微服务调用链路的最短路径
十二、字符串
Q043. KMP算法(字符串匹配,在主串中查找模式串)
难度:★★★★★
答案要点:
- 核心思想:匹配失败时利用已匹配信息跳过不必要的比较
- next数组(部分匹配表):next[i]表示模式串前i个字符的最长相等前后缀长度
- 匹配失败时j=next[j](模式串指针回退到最长相等前后缀位置)
- 时间O(m+n),空间O(m)(m为模式串长度)
- 后端场景:字符串搜索、内容过滤、日志关键字匹配;Java的String.indexOf()在JDK中使用的是朴素匹配或优化的BM算法
Q044. 最长公共前缀
难度:★★☆☆☆
答案要点:
- 横向扫描:依次比较相邻两个字符串的公共前缀,逐步缩小
- 纵向扫描:按列比较所有字符串同一位置的字符
- 排序法:排序后只需比较第一个和最后一个字符串的公共前缀
- 时间O(S)(S为所有字符串字符总数)
- 后端场景:Trie前缀树的基础、URL路由匹配(如Spring MVC的路径前缀匹配)、自动补全的前缀匹配
Q045. 字符串反转(反转字符串、反转单词顺序)
难度:★★☆☆☆
答案要点:
- 双指针:左右指针交换,向中间靠拢,时间O(n)空间O(1)
- 反转单词顺序:先整体反转,再逐个单词反转
- Java中注意String不可变,需转为char[]或StringBuilder操作
- 后端场景:回文判断的基础、数据处理中的字符串操作;面试常作为warm-up题
十三、高频设计题
Q046. 实现LFU缓存(最不经常使用)
难度:★★★★★
答案要点:
- 双层HashMap:key→Node映射 + freq→双向链表(同一频率的所有节点)
- minFreq变量跟踪当前最小频率
- get时:查找节点,频率+1,从旧频率链表移到新频率链表
- put时:新节点频率为1,超容量时删除minFreq对应链表的尾部
- 时间O(1)
- 后端场景:Redis的LFU淘汰策略(Redis 4.0+支持allkeys-lfu);比LRU更精准地识别冷热数据
Q047. 实现数据流的中位数查找(MedianFinder)
难度:★★★★☆
答案要点:
- 两个堆:大顶堆存较小的一半,小顶堆存较大的一半
- 维护平衡:两个堆大小差不超过1
- addNum:先加入一个堆,再把堆顶元素移到另一个堆保持平衡,时间O(logn)
- findMedian:堆顶元素(奇数)或两堆顶平均值(偶数),时间O(1)
- 后端场景:实时统计中位数(监控系统响应时间的中位数P50)、数据流分析、A/B测试中的统计指标计算
Q048. 实现Trie前缀树(insert/search/startsWith)
难度:★★★★☆
答案要点:
- 节点结构:26个子节点指针(或HashMap)+ isEnd标志
- insert:逐字符向下创建节点,末尾标记isEnd=true
- search:逐字符查找,最后检查isEnd;startsWith只需检查路径存在
- 变体:统计前缀出现次数、自动补全(存储推荐词列表)
- 后端场景:搜索建议系统(输入框自动补全)、拼写检查、IP路由表的最长前缀匹配、敏感词过滤系统
十四、复杂度分析
Q049. 常见排序算法的时间/空间复杂度和稳定性对比
难度:★★★☆☆
答案要点:
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 |
| 冒泡 | O(n) | O(n²) | O(n²) | O(1) | 稳定 |
| 快排 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 归并 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| TimSort | O(n) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
- 后端场景:选择排序算法时需综合考虑数据规模、是否需要稳定性、是否近乎有序等因素;JDK对不同场景选择不同排序策略
Q050. 什么是均摊分析?以ArrayList和HashMap为例说明
难度:★★★★☆
答案要点:
- 均摊分析:一系列操作中,虽然单次操作可能很耗时(如扩容),但分摊到所有操作后平均仍为O(1)
- ArrayList:add操作通常O(1),触发扩容时O(n)(复制数组),但均摊O(1)。扩容策略:1.5倍
- HashMap:put通常O(1),触发resize时O(n)(rehash所有元素),均摊O(1)。扩容策略:2倍
- 均摊≠平均:均摊是对任意输入的保证,平均是对随机输入的期望
- 后端场景:理解Java集合的底层性能特征,在性能敏感场景(如高频交易、实时计算)中正确评估操作代价;面试中解释"HashMap的put为什么是O(1)"时必须提到均摊分析