2.2 数据结构
← 2.1 编程原则 | 首页 | 下一节: 2.3 整洁代码 →
基础结构
掌握基本类型（int、float、boolean、char/string）和复合类型（数组、矩阵、对象/字典/哈希表、链表、树、图）的适用场景和复杂度特征。
缓存与记忆化（Memoization）
缓存是将频繁访问的数据存储在高读写性能的中间层，避免重复计算或重复读取慢速存储（数据库、网络）。常见层级：CPU L1/L2/L3 缓存 → 内存缓存（如 Redis）→ 磁盘。
记忆化是函数式编程中的特定优化技术：将函数的计算结果缓存起来，后续同一输入直接返回缓存值。前提是该函数必须是纯函数（无副作用，相同输入总是相同输出）。典型的 Fibonacci 数列计算——没有记忆化时时间复杂度 O(2^n)，使用记忆化后降为 O(n)。
栈 vs 堆
| 维度 | 栈（Stack） | 堆（Heap） |
|---|---|---|
| 分配方式 | 函数调用时自动在栈顶分配，函数返回时自动释放 | 运行时动态分配/释放，无强制模式 |
| 结构 | LIFO（后进先出），连续内存 | 任意顺序，非连续，需要簿记跟踪 |
| 速度 | 极快：分配=调整一个指针，通常是一条 CPU 指令 | 慢：需查找合适空闲块、多线程同步、更新分配表 |
| 缓存 | CPU 缓存命中率极高（频繁重用） | 较低（内存分散访问） |
| 线程 | 每个线程独立栈 | 应用级全局资源，需线程安全 |
| 容量 | 固定大小（线程创建时确定） | 可增长，受系统内存限制 |
| 常见问题 | 栈溢出（无限递归、过深调用链、过大局部变量） | 内存泄漏（分配未释放）、碎片化（总空闲足够但无连续块） |
| 用途 | 局部变量、函数参数、返回地址 | new/malloc 分配的对象、需跨函数存活的数据 |
Git vs GitHub 类比
Git 是分布式版本控制系统，一个工具，管理源码历史；GitHub 是 Git 仓库的托管平台，提供 Web 界面、访问控制、Pull Request、Issue 跟踪等协作功能。Arthur Khazbulatov 的精辟类比："Git 和 GitHub 的区别，就像色情片和 PornHub 的区别。"你不需要 GitHub 也能用 Git。
来源
- Stack Overflow — What and where are the stack and heap?: https://stackoverflow.com/a/80113/1213497
- Stack Overflow — Difference between Git and GitHub: https://stackoverflow.com/a/13321586