数据结构其实没忘：从数组、链表到树和哈希，重新理解一遍底层原理

大学里学《数据结构》时很多人都有一种感觉数组、链表、栈、队列、树、哈希表好像都学过但工作几年以后只记得名字细节已经忘得差不多了。其实数据结构没那么玄乎。它解决的问题始终只有两个数据怎么放数据怎么找。不同的数据结构本质上就是在“查询速度、插入速度、删除速度、空间占用”之间做取舍。下面用比较直观的方式把大学里最常见的数据结构重新串起来。一、数组为什么下标访问这么快数组可以理解成一排连续的储物柜[10][20][30][40][50] 0 1 2 3 4它最大的特点是内存连续。假设第一个元素地址是1000每个int占 4 个字节那么arr[0] → 1000 arr[1] → 1004 arr[2] → 1008 arr[3] → 1012所以访问arr[i]时并不需要从头开始找。CPU 可以直接计算元素地址 起始地址 i × 元素大小因此数组按下标访问的时间复杂度是O(1)但数组的缺点也来自“连续存储”。比如[10][20][30][40]现在要在 20 后面插入 25[10][20][25][30][40]后面的 30、40 都得往后挪。所以数组查询快随机插入删除相对慢。这也是ArrayList底层为什么适合“读多写少”的原因之一。二、链表为什么插入快查询却慢链表不是把数据连续放在一起而是10 → 20 → 30 → 40 → null每个节点除了数据还保存下一个节点的地址。可以想成寻宝第一张纸告诉你第二张纸在哪第二张纸再告诉你第三张纸在哪。因此插入节点非常方便。原来20 → 30想插入25只需要变成20 → 25 → 30本质只是修改几个指针。但问题也很明显。如果想找第 1000 个节点不能直接node[1000]只能第1个 ↓ 第2个 ↓ 第3个 ↓ ... ↓ 第1000个所以链表随机访问是O(n)这就是数组和链表最核心的区别数组靠连续内存换来了快速定位链表靠指针换来了灵活插入。三、栈为什么函数调用离不开它栈最容易理解成一摞盘子先放进去的在下面 后放进去的在上面只能从顶部拿Push Push Push Pop所以栈遵循后进先出LIFO。程序里的函数调用就是非常典型的栈。例如main() ↓ methodA() ↓ methodB()执行到methodB()时调用栈大概可以理解成| methodB | | methodA | | main |methodB执行完Pop methodB然后回到methodA。这也是为什么无限递归最终会出现StackOverflowError因为调用栈不断增长A ↓ A ↓ A ↓ A ...最后栈空间用完。所以栈不是课堂上的抽象概念它实际上直接参与了程序执行。四、队列为什么消息系统天然像它队列就像排队买奶茶A → B → C → D谁先来谁先处理。因此先进先出FIFO。这和很多系统中的任务处理模型非常像。例如请求A 请求B 请求C ↓ 消息队列 ↓ 消费者依次处理Kafka、RabbitMQ、RocketMQ虽然内部实现远比普通队列复杂但从业务抽象上看依旧是在解决任务暂存 顺序消费 削峰。栈和队列的底层实现其实并不固定。它们既可以用数组实现也可以用链表实现。因此严格来说栈和队列更多是一种访问规则。五、哈希表HashMap为什么查询这么快假设现在要保存一亿个用户userId → User如果用普通数组逐个查找效率太低。哈希表的思路是先通过 Hash 函数算出数据应该放在哪。例如hash(zhangsan) 1024那么直接去1024号位置找。可以理解成快递柜。你不用挨个柜子找包裹而是系统直接告诉你A区 18号柜所以正常情况下哈希表查询非常快O(1)但有个问题不同 Key 可能算出相同位置。例如hash(A) 10 hash(B) 10这就是Hash 冲突。Java HashMap 的经典处理方式是数组 ↓ 桶 ↓ 链表 / 红黑树大概可以理解成bucket[10] ↓ A → B → C如果一个桶里的数据越来越多链表查询会越来越慢。因此 Java 8 中当满足一定条件时会把长链表转换成红黑树从而把极端情况下的查询效率从O(n)改善到O(log n)所以 HashMap 本质上不是单纯的“Hash”。而是数组 Hash函数 冲突解决结构。六、树为什么数据库索引喜欢用树普通二叉搜索树可以理解成50 / \ 30 80 / \ / \ 20 40 60 90查找 6050 ↓ 比50大往右 ↓ 80 ↓ 比80小往左 ↓ 60不需要扫描所有数据。理想情况下查询复杂度O(log n)问题是如果数据插入顺序不好10 \ 20 \ 30 \ 40树就退化成链表。于是出现了AVL树红黑树这些自平衡树。它们的目标都是别让树长得太歪。七、为什么 MySQL 索引不是普通二叉树而是 BTree因为数据库和内存程序不一样。数据库最大的问题之一是磁盘 IO 很贵。普通二叉树一个节点只有两个孩子。如果有几百万条数据树可能很高根 ↓ 节点 ↓ 节点 ↓ 节点 ↓ 节点查询一次可能需要多次磁盘读取。BTree 的核心思想是一个节点放更多 Key让树变得特别矮。例如一个节点一次可以存1000个索引那么几千万数据可能只需要三四层。于是查询根节点 ↓ 中间节点 ↓ 叶子节点只需要很少的磁盘 IO。而且 BTree 的叶子节点通常还是有序链表10 → 20 → 30 → 40 → 50所以特别适合WHERE id BETWEEN 1000 AND 2000这种范围查询。这也是 MySQL InnoDB 索引选择 BTree 的重要原因。八、堆PriorityQueue为什么能快速找到最大值或最小值堆不是 JVM 的“堆内存”那个堆。数据结构里的堆本质是一棵特殊的完全二叉树。例如最小堆1 / \ 3 5 / \ 7 9特点是父节点永远不大于子节点。因此最小值永远在根节点。查最小值O(1)插入和删除通常是O(log n)典型场景就是从100万条数据中找Top100没必要把100万条全部排序。维护一个大小为100的堆即可。所以排行榜、定时任务调度、TopK问题经常会见到堆。九、这些数据结构到底该怎么选可以简单记成数据结构最大特点常见场景数组随机访问快ArrayList链表插入删除灵活链式结构栈后进先出函数调用、表达式计算队列先进先出任务队列、消息处理哈希表Key查询快HashMap、缓存树有序查询TreeMap、数据库索引堆快速获取最大/最小值PriorityQueue、TopK但真正理解数据结构之后你会发现没有哪种数据结构是绝对最好的。例如数组为什么不直接替代链表因为数组查询快但插入成本高。HashMap查询为什么很快因为它付出了更多空间同时不天然保证有序。树为什么不用O(1)查询因为它换来了有序性、范围查询能力以及更稳定的查找效率。数据结构设计本质一直是在做取舍。十、工作以后为什么还需要懂数据结构因为很多我们每天使用的东西底层其实都离不开它ArrayList → 动态数组 LinkedList → 双向链表 HashMap → 数组 链表 红黑树 TreeMap → 红黑树 PriorityQueue → 堆 MySQL索引 → BTree Redis List → 链表 / Listpack Redis ZSet → Hash 跳表如果只会调用 API很多问题只能停留在“它为什么突然慢了”理解数据结构之后会进一步想到是不是 Hash 冲突太严重是不是发生了大量数组扩容是不是遍历链表导致复杂度上升为什么数据库范围查询可以利用索引为什么 TopK 不应该直接全量排序这时候大学里学的数据结构才真正和工程实践连起来。总结回头看数据结构其实不用重新背一遍教材。记住一条主线就够了数据结构解决的核心问题就是数据如何组织以及为了某种操作更快我们愿意付出什么代价。数组用连续空间换来了随机访问。链表用指针换来了灵活插入。哈希表用额外空间换来了快速查找。树用层级结构换来了有序搜索。堆牺牲完整排序能力换来了快速找到极值。所以真正重要的不是记住数组 O(1) 链表 O(n) 树 O(log n)而是理解为什么它能做到这个复杂度。一旦底层原理想通了大学里那些看起来零散的数据结构其实就会重新连成一张完整的图。