动态规划：背包、斐波那契、股票问题核心是状态转移方程，空间优化优先；
平衡树：红黑树工业常用，AVL 查询优，Treap 实现简单，B+ 树数据库专属；
图算法：DFS/BFS 遍历，Dijkstra 最短路径，Kruskal/Prim 生成树，Tarjan 求 SCC；
并发工具：CountDownLatch 实现线程等待，是基础同步组件；
高级结构：跳跃表、Trie、并查集、布隆过滤器，对应高并发、字符串、连通性、去重场景。
背包问题以01 背包最经典，动态规划核心是二维 / 一维 dp 数组记录最优解。定义dp[i][j]表示前 i 个物品、背包容量 j 时的最大价值。状态转移：不选第 i 个物品→dp[i-1][j]；选→dp[i-1][j-weight[i]] + value[i]，取最大值。
Java 实现可优化为一维数组倒序遍历，节省空间。核心代码：for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i])。完全背包正序遍历，多重背包拆分处理。该方案时间复杂度 O(nm)，空间复杂度 O(m)，是背包问题的标准解法。
DFS 是递归 / 栈实现的深度遍历，优先走到底再回溯。图用邻接表存储，需布尔数组标记访问节点，避免环。递归版：访问当前节点→标记→递归遍历所有未访问邻接节点；非递归版用 Stack 手动模拟递归栈。
适用：路径查找、连通性判断、拓扑排序。Java 核心代码：递归方法dfs(int u)，遍历邻接表list.get(u)，未访问则递归调用。DFS 代码简洁，适合深度探索，但深度过大会栈溢出，非递归版更稳定。
红黑树是自平衡二叉查找树，核心规则：节点红 / 黑、根黑、叶节点黑、红节点子节点黑、任意节点到叶子的黑高相同。Java 实现需定义节点类（颜色、键值、左右孩子、父节点），实现插入、旋转、变色、平衡调整，删除逻辑更复杂。
JDK 的 TreeMap/TreeSet 底层就是红黑树。手动实现核心：插入后违反规则时，通过左旋、右旋、变色修复平衡。它增删查 O(logn)，平衡开销低于 AVL 树，是工业级常用平衡树。
CountDownLatch 是线程同步工具，让主线程等待子线程完成。使用三步：1. 初始化new CountDownLatch(计数)；2. 子线程调用countDown()计数器 -1；3. 主线程调用await()阻塞等待计数器为 0。
适用：并行任务汇总、服务启动校验。Java 示例：主线程 await，10 个子线程执行完 countDown，主线程继续。它是一次性同步工具，计数器归零无法重置，配合线程池使用，是高并发并行协调的基础组件。
快排是分治法经典实现：选基准值→分区（小左大右）→递归排序左右子数组。Java 实现：定义quickSort方法，partition分区函数交换元素。基准值可选首位、中位、随机（避免有序数组退化）。
核心代码：分区后递归quickSort(arr, left, p-1)和quickSort(arr, p+1, right)。时间平均 O(nlogn)，最坏 O(n²)，空间 O(logn)，是实际开发最快的通用排序算法，JDK Arrays.sort 底层用快排处理基本类型。
二叉查找树（BST）查找遵循左小右大规则：从根节点开始，目标值 < 当前节点→查左子树；>→查右子树；=→查找成功。Java 实现递归 / 非递归两种方式，非递归用循环避免栈溢出。
核心代码：public TreeNode search(TreeNode root, int val)，循环判断值大小遍历子树。BST 查找平均 O(logn)，最坏 O(n)（退化成链表），平衡二叉树可稳定保证 O(logn)，是基础查找数据结构。
BFS 用队列实现层序遍历，适合最短路径、层序遍历。图用邻接表存储，标记数组防重复访问。步骤：入队根节点→标记→循环出队→遍历邻接节点，未访问则入队标记。
Java 核心代码：Queue<Integer> q = new LinkedList<>()，offer 初始节点，while 循环 poll 节点，遍历邻接表。BFS 是最短路径最优解（无权图），无递归栈溢出问题，是图遍历的基础算法。
堆排序基于二叉堆（大顶堆）：1. 把数组构建成大顶堆；2. 交换堆顶和末尾元素，最大值固定；3. 调整剩余元素为堆，重复直到有序。Java 实现：buildHeap建堆，heapify调整堆结构。
核心是 heapify 函数，维护堆性质。时间复杂度 O(nlogn)，空间 O(1) 原地排序，不稳定。适用：大数据量排序、TopK 问题，JDK 优先级队列底层就是堆实现。
归并排序是分治法标准实现：分解→解决→合并。分解：数组拆分为左右两半；解决：递归排序子数组；合并：合并两个有序子数组。Java 实现：mergeSort拆分，merge合并有序数组。
时间复杂度 O(nlogn)，稳定排序，空间 O(n)。适用：大数据外部排序、链表排序。核心是合并逻辑，通过临时数组存储有序元素，是稳定排序中的高效方案。
BST 增删查遵循左小右大：插入→遍历找到空节点插入；查找→循环 / 递归匹配值；删除分三种：叶子节点直接删、单孩子节点替换、双孩子节点用后继节点替换。
Java 实现节点类，封装三个方法。平均复杂度 O(logn)，最坏 O(n)。示例：插入递归判断左右，删除找最小值替换。是动态数据增删查的基础结构，平衡树优化了其性能短板。
Dijkstra 求非负权图单源最短路径，用 ** 优先队列（最小堆）** 优化。步骤：初始化距离数组→源点入队→循环出队最小距离节点→松弛邻接节点→更新距离入队。
Java 实现：邻接表存图，PriorityQueue<int[]>存节点 + 距离，dist[]记录最短路径。时间复杂度 O(ElogV)，是最常用最短路径算法，适用导航、网络路由，无法处理负权边。
斐波那契动态规划避免递归重复计算，分自底向上和备忘录。自底向上：定义 dp 数组，dp[0]=0,dp[1]=1，循环dp[i]=dp[i-1]+dp[i-2]；优化为变量迭代，空间 O(1)。
Java 核心代码：int a=0,b=1; for(int i=2;i<=n;i++){int c=a+b;a=b;b=c;}。时间 O(n)，空间 O(1)，比递归 O(2ⁿ) 高效百倍，是动态规划入门经典案例。
AVL 树是严格平衡二叉查找树，每个节点左右子树高度差≤1（平衡因子）。Java 实现：节点类 + 高度字段，实现增删查 +左旋 / 右旋平衡调整。插入后回溯更新高度，计算平衡因子，失衡则四种旋转修复（左左、右右、左右、右左）。
自平衡核心：通过旋转调整树结构，保证高度差≤1。增删查 O(logn)，平衡严格，旋转频繁，比红黑树查询快、插入慢，适合查询密集场景。
哈希表碰撞：不同 key 哈希值相同。Java 解决用链地址法：数组 + 链表 / 红黑树。哈希值对应数组下标，碰撞元素挂在链表后，链表长度≥8 转为红黑树，≤6 转回链表。
原理：哈希函数计算下标，碰撞时链式存储，红黑树优化长链表查询效率。HashMap 底层就是该方案，时间平均 O(1)。此外还有开放寻址法，Java ThreadLocalMap 用此方案，链地址法是主流。
Java 优先队列（PriorityQueue）底层是最小堆（数组存储完全二叉树）。堆规则：父节点≤子节点，堆顶是最小值。实现：offer 元素上浮调整，poll 元素堆顶替换末尾，下沉调整。
核心：上浮 siftUp、下沉 siftDown 维护堆性质。自定义比较器可实现最大堆。适用：任务调度、TopK、Dijkstra 算法，增删 O(logn)，是最常用的优先级数据结构。
相同：都是自平衡二叉查找树，增删查 O(logn)。不同：AVL严格平衡（高度差≤1），旋转多、查询快；红黑树弱平衡（黑高相同），旋转少、增删快。
存储：AVL 存高度，红黑树存颜色。应用：AVL 适合查询密集；红黑树适合频繁增删，JDK TreeMap/TreeSet、HashMap 用红黑树。红黑树平衡开销更低，工业界更常用。
Trie 是多叉树，节点存字符，路径存字符串，共享前缀节省内存。特点：前缀匹配快、无哈希碰撞、自动去重。Java 实现：节点类（子节点数组、结束标记），实现插入、查找、前缀查询。
应用：自动补全、拼写检查、IP 路由、词频统计、敏感词过滤。时间复杂度 O(k)（k 为字符串长度），是字符串前缀处理的最优数据结构。
并查集解决动态连通性问题，实现合并、查找两大操作，带路径压缩和按秩合并优化。Java 实现：parent 数组存父节点，rank 数组存树高度。find 查找根节点 + 路径压缩，union 合并两棵树。
核心代码：find(int x)递归压缩路径，union(int x,int y)按秩合并。时间复杂度近似 O(1)，适用：朋友圈、连通图、 Kruskal 最小生成树，是最简洁高效的连通性数据结构。
跳跃表是多层有序链表，每层是有序链表，高层链表跳跃底层节点，查询 O(logn)。Java 实现：节点类（值、多层指针），实现插入、删除、查找，随机层数决定节点高度。
Redis ZSet 底层用跳跃表。优势：实现比红黑树简单，并发友好，增删查高效。适合有序集合、范围查询，是高并发有序数据的首选结构。
活动选择：选最多不重叠活动，贪心策略选结束最早的活动。Java 实现：活动数组按结束时间排序→初始化选第一个→遍历选开始时间≥上一个结束时间的活动。
核心：排序 + 贪心选择。时间 O(nlogn)，最优解。适用：会议室安排、课程调度，是贪心算法最经典的入门案例，直观且高效。
B 树：多路平衡树，节点存键 + 数据，叶子节点不连通；B+ 树：非叶子节点仅存键，数据全在叶子节点，叶子链表连通。B+ 树查询更稳定，范围查询极快。
应用：B 树用于文件系统；B+ 树用于 MySQL InnoDB 索引。都是数据库 / 文件系统核心结构，解决磁盘 IO 优化问题，B+ 树更适合关系型数据库索引。
股票 DP 分场景：最多 1 次、无限次、最多 k 次。核心定义dp[i][j]第 i 天状态 j 的最大利润，状态转移：持有 / 不持有。
无限次示例：dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])；dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])。优化为变量迭代，空间 O(1)，时间 O(n)，覆盖所有股票买卖场景。
Trie 内存优化：1. 数组改哈希表，仅存存在的子节点；2. 压缩前缀，合并单分支节点（基数树）；3. 对象复用，共享节点实例；4. 数组紧凑存储，用 byte/char 替代对象。
Java 实现用Map<Character, TrieNode>替代固定数组，大幅节省稀疏节点内存。优化后适合海量字符串存储，如搜索引擎词库、大规模敏感词库。
Prim：点扩展，适合稠密图。用优先队列选最小权边，连接新节点。Kruskal：边排序，适合稀疏图。边按权排序，用并查集判断连通，避免环。
Java 实现：Prim 用邻接表 + 最小堆；Kruskal 用边列表 + 并查集。两者都是 O(ElogE)，生成权值最小的连通树，适用电网、路网、网络布线。
布隆过滤器：二进制数组 + 多个哈希函数，插入：多哈希计算下标置 1；查询：全 1 则存在（有误判）。Java 实现：BitSet 存数组，多个哈希函数计算位置。
优势：空间极小、查询极快；缺点：无法删除、有误判。适用：缓存穿透防护、黑名单过滤、去重，是高并发海量数据去重的核心工具。
Treap=Tree+BST+Heap，二叉搜索树 + 堆性质，节点存键（BST）+ 随机优先级（堆）。插入后按优先级旋转，维持堆性质，自动平衡，无需严格高度判断。
Java 实现：节点 + 优先级，插入后左旋 / 右旋维护堆性质。增删查 O(logn)，实现比 AVL/ 红黑树简单，平衡效果优秀，适合教学、简易平衡树场景。
SCC：有向图中互相可达的子图，三种算法：1. Kosaraju：DFS+ 逆图再 DFS；2. Tarjan：一次 DFS，栈 + 追溯值；3. Gabow：栈优化。
Java 常用 Tarjan 算法，代码简洁，一次遍历求出所有 SCC。适用：有向图连通性、社交网络、推荐系统，是有向图核心算法。
一致性哈希解决分布式缓存扩缩容的哈希倾斜问题。原理：哈希环存节点和数据，数据映射到环上最近节点。增删节点仅影响少量数据，无需全量迁移。
Java 实现：TreeMap 模拟哈希环，tailMap 查找目标节点，虚拟节点优化倾斜。适用：Redis 集群、分布式存储、负载均衡，是分布式系统核心哈希算法。
基数排序是非比较排序，按个位、十位、百位逐位排序，用桶分配收集。Java 实现：按数字 / 字符逐位处理，桶存储临时数据。
时间复杂度 O(k*n)（k 为位数），空间 O(n+k)，稳定排序。适用：整数、字符串排序，数据范围小的场景，比快排更快，如手机号、身份证排序。
延迟传播（懒标记）：线段树区间修改时，标记待更新节点，不立即更新子节点，查询时再向下传播标记。避免重复修改子节点，将区间修改 O(n) 降为 O(logn)。
Java 实现：懒标记数组，pushDown 函数传播标记。适用：区间和、区间最值、区间更新，是处理区间问题的核心优化技术。
图着色：给节点染色，相邻节点颜色不同。分：1. 贪心着色：按顺序染最小可用色；2. 回溯着色：暴力搜索最优解；3. DSatur 算法：优先染饱和度最高的节点。
Java 实现贪心着色最简单，遍历节点，遍历邻接节点排除颜色，选最小可用色。适用：地图染色、任务调度、寄存器分配，是图论经典应用。
