数据结构选型优化：数组 vs 链表、哈希表的妙用、树与图的场景选择

数据结构选型，说白了就是「怎么存数据才能让程序跑得快」。

我见过太多人上来就用数组，结果插入删除慢成狗。也有人无脑上哈希表，内存爆了还不知道怎么回事。今天咱们就把这几个常用数据结构掰开揉碎，看看它们到底该怎么选。

数组 vs 链表：内存布局决定命运

先问个问题：数组和链表，到底差在哪？

很多人背过「数组连续内存，链表离散存储」。但实际写代码时，这个差异会带来巨大的性能鸿沟。

我做过一个日志系统，一开始用链表存最近 10 万条记录。结果每次遍历都要 200ms 以上，用户翻页卡得要死。换成数组后，遍历时间直接降到 5ms。为什么？因为数组的连续内存让 CPU 预取机制发挥了作用，链表则让 CPU 一直在等内存。

哈希表的妙用：O(1) 查找背后的代价

哈希表，面试必问，项目必用。但你真的用对了吗？

我见过有人用哈希表存 100 个元素，key 是自增整数。你想想看，这场景用数组不香吗？哈希表再快，也有哈希计算的开销，而且内存占用比数组大好几倍。

哈希表真正的价值在于：用空间换时间。当你的 key 不是连续整数，或者需要快速判断「某个值是否存在」时，哈希表就是神器。

但要注意，哈希表不是万能的。我曾经在一个高并发系统里用哈希表做会话管理，结果内存涨到 2GB 还没停下来。后来发现是哈希表扩容机制导致的——每次扩容都要 rehash，内存瞬间翻倍。

树与图的场景选择：从二叉树到邻接表

树和图，很多人觉得难。其实你只要记住一句话：有层级关系用树，有网状关系用图。

树的典型场景：

• 文件系统目录结构
• DOM 树
• 数据库索引（B+ 树）
• 表达式解析（AST）

图的典型场景：

• 社交关系（好友推荐）
• 地图导航（最短路径）
• 依赖分析（构建工具）
• 推荐系统（协同过滤）

我做过一个权限系统，一开始用树结构存组织架构。后来发现权限有交叉（一个人可以属于多个部门），树就搞不定了。换成图结构后，用邻接表存储，查询效率提升了 10 倍。

实际案例对比：从需求到选型

光讲理论没意思，咱们看个真实案例。

需求：做一个在线文档的版本管理功能，需要存储文档的编辑历史。

一开始我用了数组，每次编辑就往数组末尾追加。看起来没问题，对吧？

但用户要求「回退到任意历史版本」，而且文档可能被多人同时编辑。数组的问题就暴露了：

• 插入中间版本 → O(n)
• 查找某个时间点的版本 → 需要遍历
• 多人编辑冲突 → 难以处理

后来我改成链表 + 哈希表的组合方案：

• 链表存储版本链，每个节点指向父版本
• 哈希表以版本 ID 为 key，O(1) 定位任意版本
• 分支版本用树结构管理

这个案例告诉我们：没有最好的数据结构，只有最合适的组合。实际项目中，往往是多种数据结构配合使用，才能达到最优效果。