动态规划：背包、斐波那契、股票问题核心是状态转移方程，空间优化优先；
平衡树：红黑树工业常用，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实现贪心着色最简单，遍历节点，遍历邻接节点排除颜色，选最小可用色。适用：地图染色、任务调度、寄存器分配，是图论经典应用。
