📚 课程目录第4章数据结构选型

数据结构选型：数组、链表、哈希表、树、图在不同场景下的性能差异

数据结构选型，说白了就是给数据找个合适的「家」。选对了，程序跑得飞快；选错了，优化到吐血也救不回来。我见过太多团队，上来就用哈希表解决一切，结果内存爆了，或者遍历性能惨不忍睹。

今天咱们就把五种最常用的数据结构——数组、链表、哈希表、树、图——掰开揉碎，看看它们各自擅长什么，又怕什么。

数组最大的优势是什么？随机访问 O(1)。你给个下标，它直接通过基址+偏移量算出来，CPU 缓存命中率还高。我当年做游戏引擎时，粒子系统里几千个粒子位置更新，用的就是数组——连续内存，遍历起来那叫一个丝滑。

但数组的痛点也很明显：插入和删除是 O(n)。为啥？因为要挪动后面的元素。你想想看，在数组头部插一个元素，后面所有元素都得往后移一位，数据量大了直接卡死。

我的习惯：如果数据量固定且频繁随机访问，无脑选数组。动态扩容用 std::vector 或 ArrayList，均摊成本很低。

链表的好处是插入和删除快——只要改指针就行，O(1) 搞定。但代价呢？随机访问是 O(n)，你得从头一个个找。而且每个节点还要存指针，内存开销大。

我记得有一次做消息队列，一开始用数组，结果频繁在中间插入优先级消息，性能崩了。换成链表后，插入操作快了 10 倍。但遍历时又发现，链表因为内存不连续，CPU 缓存命中率低，遍历速度比数组慢 3-5 倍。

  核心对比：
  数组：适合「读多写少」的场景
链表：适合「写多读少」且插入位置随机的场景

链表还有个变种——跳表。它通过多层索引把查找优化到 O(log n)，Redis 的有序集合就用它。但实现复杂度高，一般场景用不上。

哈希表，平均 O(1) 的查找、插入、删除，看起来完美？别急，坑在后面。

哈希表的核心是哈希函数 + 冲突解决。我见过最典型的坑是：哈希函数设计不好，大量 key 映射到同一个桶，退化成链表，O(1) 变 O(n)。

另外，内存开销大。哈希表为了保持低冲突率，负载因子通常控制在 0.7 左右，意味着 30% 的内存是空的。如果你存 100 万条记录，实际占用的内存可能是 150 万条的空间。

我曾经踩过的坑：在嵌入式设备上用哈希表存传感器数据，结果内存直接爆了。后来换成数组 + 二分查找，虽然查找慢了点，但内存占用降了 40%。

树结构，尤其是二叉搜索树（BST），把查找、插入、删除都做到了 O(log n)。但前提是树要平衡——退化成链表就完蛋了。

实际工程中，我们很少用裸 BST，而是用红黑树或AVL 树。红黑树是近似平衡，插入删除性能好；AVL 树是严格平衡，查找更快。C++ 的 std::map 和 Java 的 TreeMap 底层都是红黑树。

数据库索引用的则是B+ 树。为什么？因为 B+ 树每个节点可以存多个 key，树的高度低，磁盘 I/O 次数少。你想想看，如果数据库用二叉树，100 万条数据树高约 20 层，每次查询要读 20 次磁盘；B+ 树可能只要 3-4 次。

  选型建议：
  需要有序遍历、范围查询 → 红黑树 / B+ 树
内存数据库、高频插入删除 → 红黑树
磁盘存储、大量数据 → B+ 树

图是最灵活的数据结构，但也是最难用的。社交网络、地图导航、依赖分析，这些场景非图不可。

图的存储方式有两种：邻接矩阵和邻接表。

我做过一个知识图谱项目，节点 100 万，边 500 万。用邻接矩阵？算一下：100 万 × 100 万 = 1 万亿个元素，内存直接爆炸。只能用邻接表，每条边存一次，内存才几百 MB。

我的经验：图算法性能瓶颈往往不在数据结构本身，而在遍历方式。BFS 用队列，DFS 用栈，选错了会导致内存暴涨。我见过有人用递归 DFS 遍历 10 万节点的图，结果栈溢出。

下面这张图总结了不同场景下的数据结构选型路径，你可以把它当作决策参考。

说了这么多，其实就一句话：没有最好的数据结构，只有最合适的。你想想看，哈希表再快，也做不了范围查询；数组再快，也扛不住频繁插入；链表再灵活，遍历起来也慢。

我个人的习惯是：先列出现有的操作类型和频率，再考虑数据规模，最后看内存和并发约束。如果拿不准，就写个 benchmark 跑一下——实践出真知。

  避坑指南：
  别迷信 O(1)——常数项可能很大，哈希函数计算开销不可忽视
别忽略 CPU 缓存——连续内存的数组遍历比链表快 5-10 倍
别忘记内存对齐——结构体数组比对象数组更高效

嗯，数据结构选型就聊到这儿。记住，选型不是一次性的，随着业务变化，数据结构也需要迭代。保持对性能的敏感，比记住任何理论都重要。