是什么

数据结构：组织和存储数据的方式，以及在这些数据上支持的操作。

为什么重要：不同的组织方式，决定了不同操作的效率。

几个基础结构

数组（Array）

特点：连续内存，通过索引访问。

  • 随机访问：O(1)（因为地址可直接计算）；
  • 插入/删除（中间）：O(n)（需要移动元素）；
  • 查找（无序）：O(n)。

适合：需要频繁随机访问、大小相对固定的场景。

CPU 缓存友好（前文提到过局部性原理）——这使得数组在实践中往往比理论上更快。

链表（Linked List）

特点：节点通过指针连接，内存不连续。

  • 插入/删除（已知位置）：O(1)（只需改指针）；
  • 随机访问：O(n)（必须从头遍历）；
  • 查找：O(n)。

适合：频繁插入删除、不需要随机访问的场景。

缓存不友好——节点分散在内存中，缓存命中率低。这是链表在实践中常常"理论好、实际慢"的原因。

哈希表（Hash Table）

特点：通过哈希函数把键映射到数组位置。

  • 平均查找/插入/删除：O(1)；
  • 最坏情况：O(n)（哈希冲突严重时）。

这是工程中最常用的结构之一——几乎所有语言的字典/Map 都基于它。

关键问题：

  • 哈希函数的质量（分布是否均匀）；
  • 冲突处理（链地址法、开放寻址法）；
  • 负载因子与扩容（负载因子过高时性能下降，需要扩容并重新哈希）。

树（Tree）

二叉搜索树：左子树 < 根 < 右子树。平均查找 O(log n)，但可能退化成链表（如果插入顺序有序）。

平衡树（AVL 树、红黑树）：通过旋转操作维持平衡，保证 O(log n)。

B+ 树：数据库索引的基础（前文提到过）——它的特点是"矮胖"，适合磁盘存储（减少 I/O 次数）。

堆（Heap）

特点：完全二叉树，满足堆性质（父节点大于或小于子节点）。

  • 取最大/最小：O(1)；
  • 插入/删除：O(log n)。

用途：优先队列、Top-K 问题、堆排序。

图（Graph）

特点：节点 + 边，表达复杂的关系。

用途：社交网络、路径规划、依赖分析、推荐系统。

复杂度分析

大 O 表示法描述的是增长趋势（当输入规模 n 增大时，操作次数的量级）。

常见量级（从好到差）：

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

为什么重要：

假设 n = 100 万：

  • O(log n)：约 20 次操作；
  • O(n)：100 万次；
  • O(n²)：1 万亿次（不可接受）。

在数据量大时，选择正确的数据结构，差异是"能不能跑"的区别，而不只是"快一点慢一点"。

一个常见误区

"过度关注算法优化，忽略常数因子。"

大 O 忽略了常数。在实际中：

  • O(n) 的数组遍历（缓存友好）可能比 O(log n) 的树查找（指针跳转、缓存不友好）更快——当 n 不那么大时；
  • 小规模数据下，简单的算法往往更快。

建议：先写清晰正确的代码，用 profiling 找出真正的瓶颈，再优化。

实用建议

  • 掌握常见结构的特性与适用场景，比背诵实现细节更重要；
  • 理解你所用语言的标准库是基于什么实现的（如 Python 的 list 是动态数组，dict 是哈希表；Java 的 HashMap 在冲突严重时会树化）；
  • 在工程中，选择标准库提供的、经过优化的实现，通常优于自己手写。

说明：本文为计算机基础的知识整理。