数据结构与算法技术栈总览

一句话定位：数据结构 = 数据的组织方式（线性/树/图），算法 = 对数据的操作（排序/查找/哈希）。面试主线：线性表与哈希表（栈/队列/链表/散列 + 冲突解决）、树（二叉树 → 平衡 → B/B+ 树）、排序与查找（冒泡/选择/快排 + 二分 + 一致性哈希）。

数据结构地图

大类	结构	核心特性
线性表	栈	LIFO（后进先出），push/pop
线性表	队列	FIFO（先进先出），offer/poll
线性表	链表	插入删除快、遍历慢
散列表	哈希表	O(1) 查找，靠散列函数 + 冲突解决
树	二叉树/完全/满/平衡/红黑树	见概念卡片：树
树	B树/B+树/LSM	B+ 支持范围查询，LSM 减少随机 IO
图	有向/无向	BFS/DFS 遍历

算法地图

大类	算法	复杂度
排序	冒泡排序	O(n²)
排序	选择排序	O(n²)
排序	快速排序	平均 O(nlogn)，最坏 O(n²)
查找	二分查找	O(log n)，需有序
哈希	一致性哈希	节点增减只重定位小部分数据

Java 集合框架映射

接口	实现类	底层
List	ArrayList（数组，随机访问快）	动态数组
List	LinkedList（双向链表，插入删除快）	链表
List	Vector（线程安全）	数组 + synchronized
Set	HashSet	哈希表（HashMap 的 key）
Set	TreeSet	红黑树
Map	HashMap	哈希表（JDK1.8 起 + 红黑树）
Map	ConcurrentHashMap	分段锁/CAS（线程安全）

不变量（必须成立的约束）

栈 LIFO、队列 FIFO、哈希 O(1)、树 O(log n)（平衡时）。
哈希表 O(1) 是平均复杂度，冲突严重时退化。
二分查找前提是有序，且 mid 计算要防溢出（low + (high-low)/2）。

常见误解

以为「ArrayList 就是链表」→ 是数组实现的动态数组（名字误导）。
以为「哈希查找永远 O(1)」→ 冲突严重会退化，需控制装填因子。
以为「B+ 树和 B 树一样」→ B+ 非叶节点只存索引、叶子存全部数据且链表相连，故支持范围查询。

关联