数据结构入门时间复杂度、数组、二分、哈希、链表、树这是数据结构课的第一天。核心只有一句话数据结构解决的是数据量大了以后操作还快不快的问题。而这节课给出的衡量工具叫时间复杂度。这一篇覆盖的内容比较多按顺序是为什么需要数据结构时间复杂度到底在衡量什么数组为什么下标访问是 O(1)二分查找从 O(n) 到 O(log n)哈希表用算位置绕过排序链表插入快、查找慢的另一种取舍树从链表继续演进学习路线和刷题建议一、先明确数据结构到底解决什么问题1.1 一个生活类比图书馆管理和计算机文件管理其实是一个道理。当书或文件太多时分类存储是提高效率的关键图书馆把文学类放 1 楼、理工类放 2 楼计算机文件按类型分区存放C 盘装系统、D 盘存文档。无序堆砌会导致查找困难必须建立分类体系。就像在图书馆找书要先看导航图用电脑找文件也要靠清晰的目录结构这样才能避免大海捞针式的低效搜索。一句话分类即效率。1.2 数据结构的作用对数据进行整理以提高操作如查找、修改的效率。注意关键词是操作效率不是存储省空间。数据结构首先是为操作服务的。1.3 什么时候需要考虑数据结构老师给了一个很重要的边界数据结构主要解决大规模数据的处理效率问题。当数据量很小时比如 10 个 8 个用什么结构存储差别不大。所以存 10 条配置用数组还是链表无所谓存 1000 万条订单结构选错就是灾难。这也解释了为什么后面分析复杂度时小规模数据可以直接忽略。1.4 不同场景用不同结构课上给了几个典型对应关系场景结构原因数据库底层B 树减少磁盘 I/O支持范围查询磁盘文件索引B 树多叉、矮减少磁头移动内存中的有序存储红黑树查询稳定 O(log n)下标随机访问数组地址可计算O(1)没有最好的数据结构只有最适合这个场景的结构。这句话后面还会反复出现。二、时间复杂度不看跑多久看跑多少次2.1 为什么不能用执行时间衡量算法直觉上A 算法跑 10ms、B 算法跑 20ms那 A 更好。但这个标准不可靠因为有多个不可控变量干扰因素具体表现硬件性能同一算法在不同电脑上时间不同数据随机性某些排列可能碰巧让算法跑得快CPU 调度操作系统决定程序何时获得计算资源调度波动直接影响实测时间编程语言/编译器JIT、GC 都会干扰所以时间复杂度不直接看执行时间而是数操作次数。2.2 时间复杂度衡量的是增长趋势时间复杂度本质上衡量的是算法执行次数随数据量变化的规律。不能脱离数据量谈执行次数——处理 10 万条数据和 1 条数据的执行次数天差地别。在大规模数据场景下我们关注的是执行次数 y 与数据总量 x 的数学关系线性关系y ax b二次关系y ax² bx c常数关系y与x无关执行次数越少算法效率越高。比如y 10x的算法就比y x²更高效。关键点时间复杂度反映的是数据增长时执行次数的变化趋势而非具体的执行数字。2.3 只保留主导项当数据量 X 足够大时其他小项都可以忽略。比如执行次数是11000万零十那个十完全可以忽略我们只看量级的变化。再比如y 3x² 100x 5000当 x 100 万时3x² 3×10¹²100x 10⁸5000 5×10³后两项连第一项的零头都算不上。所以时间复杂度记作O(n²)前面的系数 3、后面的 100x 和 5000 全部丢掉。这就是大 O 记号的含义只保留增长最快的项并去掉常数系数。2.4 常见复杂度排序从优到劣复杂度名称典型场景n 100 万时的量级O(1)常数数组下标访问、哈希查找1O(log n)对数二分查找、平衡树查找20O(n)线性遍历数组、链表查找100 万O(n log n)线性对数归并排序、快速排序平均2000 万O(n²)平方冒泡、选择、插入排序10¹²O(n³)立方三重循环、朴素矩阵乘法10¹⁸O(2ⁿ)指数朴素递归求斐波那契无法计算O(n!)阶乘全排列暴力无法计算2.5 函数图像为什么 log n 最平缓老师用画图的方式对比了三种基本函数函数图像特征含义y 1一条水平线常数复杂度与数据量无关y x斜率为 1 的直线线性增长y x²抛物线上升平方级增长很快就爆掉y log n最平缓位于 y x 下方数据量再大增长也极慢一个容易忽略的点当底数 a 1 时指数函数无意义因为 1 的任何次方都是 1无法形成有效增长曲线。另外对数换底只差一个常数倍log₂n log₁₀n / log₁₀2所以在时间复杂度里底数不影响量级O(log₂n)和O(log₁₀n)都记作O(log n)。2.6 一律按最坏情况算算法复杂度是按最坏情况考虑的。在无序数组里查找元素必须逐个检查。运气好可能第一个就命中但复杂度不能按运气算——最坏情况要查遍整个数组所以是 O(n)。平均情况呢目标在任意位置的概率相同平均要查n/2次量级还是 O(n)。三、数组连续内存带来的 O(1)3.1 核心特征内存连续分配数组元素在物理内存中是紧密相邻的就像排队时人与人之间没有空隙。根据数据类型不同每个元素占用的内存大小会变化类型位数字节数int32 位4 字节long64 位8 字节charJava16 位2 字节boolean1 位逻辑上JVM 实现相关但整体保持连续存储的特性不变。3.2 地址计算公式这是整节课最关键的公式元素地址 数组首地址 下标 × 每个元素占用的字节数举例int[] arr {5, 7, 9, 11}假设首地址是 1000int 占 4 字节下标计算地址值01000 0×41000511000 1×41004721000 2×41008931000 3×4101211注意两个细节数组变量名实际存储的是首个元素的内存地址。比如定义数组 array它的值就是第一个元素的地址。内存寻址的最小单位是字节8 比特所以地址计算都按字节进行。所以访问arr[2]系统只需计算起始地址 2 × 元素大小就能定位不需要遍历一步跳到目标位置这就是 O(1) 随机访问的底层原因。运行时验证ArraySearch.javaint[] arr {5, 7, 9, 11}; System.out.println(数组首地址假设为 1000int 占 4 字节); for (int i 0; i arr.length; i) { System.out.printf(arr[%d] 的地址 1000 %d × 4 %d值 %d%n, i, i, 1000 i * 4, arr[i]); }输出arr[0] 的地址 1000 0 × 4 1000值 5 arr[1] 的地址 1000 1 × 4 1004值 7 arr[2] 的地址 1000 2 × 4 1008值 9 arr[3] 的地址 1000 3 × 4 1012值 113.3 无序数组的查找O(n)如果没有下标只知道要找值等于 10 的元素那就只能从头遍历static int linearSearch(int[] arr, int target) { for (int i 0; i arr.length; i) { if (arr[i] target) return i; } return -1; }最坏情况查 n 次平均情况查 n/2 次复杂度O(n)这种无规划的存储方式虽然实现简单直接在数组末尾追加数据但查找效率低下。3.4 同一个问题的两种解法O(n) vs O(1)求 1 到 X 的累加和解法一for 循环long sum 0; for (int i 1; i n; i) sum i; // 执行 n 次加法 → O(n)解法二等差数列公式long sum (long) (n 1) * n / 2; // 执行 1 次乘除 → O(1)实测n 1 亿for 循环累加 1..10000000027 ms结果 5000000050000000O(n) 等差数列公式 (n1)*n/20 ms结果 5000000050000000O(1) 结果一致true这就是算法优化的意义同一个问题不同解法可能差一个数量级。3.5 数组的局限数组并不是万能的长度固定Java 数组扩容要新建数组 复制中间插入/删除要搬移后续元素O(n)需要连续内存内存碎片多时可能分配失败。这些局限正好由链表来解决。四、二分查找每次砍掉一半4.1 前提数组必须有序无序数组不能二分因为砍一半的前提是如果目标比中间值大那它一定在右半边。这个推理只在有序时成立。4.2 核心逻辑用两个指针left和right圈定查找范围计算中间位置mid (left right) / 2比较arr[mid]和target相等 → 找到返回arr[mid] target→ 目标在右半边left mid 1arr[mid] target→ 目标在左半边right mid - 1重复直到left right—— 此时说明目标不存在代码static int binarySearch(int[] arr, int target) { int left 0, right arr.length - 1; while (left right) { int mid (left right) 1; // 无符号右移避免溢出 if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }4.3 把每一步打出来对[1, 3, 5, 7, 8, 10, 12, 15]查找 6BinarySearchTrace.java查找目标 6数组长度 8 步骤 left right mid arr[mid] 决策 -------------------------------------------------------- 1 0 7 3 7 偏大丢弃右半 → right 2 2 0 2 1 3 偏小丢弃左半 → left 2 3 2 2 2 5 偏小丢弃左半 → left 3 left 3right 2left right说明不存在查找 10步骤 left right mid arr[mid] 决策 -------------------------------------------------------- 1 0 7 3 7 偏小丢弃左半 → left 4 2 4 7 5 10 命中返回下标 5两次比较就命中。数据量越大优势越明显。4.4 复杂度推导第 1 次比较后剩 n/2第 2 次剩 n/4……第 k 次剩n / 2^k。当剩到 1 个元素时n / 2^k 1 2^k n k log₂n所以最多比较⌊log₂n⌋ 1次时间复杂度O(log n)。实测对比ArraySearch.java数据量 n 线性查找(最坏) 二分查找(最坏) log2(n) -------------------------------------------------------------- 1000 1000 9 10 10000 10000 13 13 100000 100000 16 17 1000000 1000000 19 20n 从 1000 涨到 100 万1000 倍线性查找次数涨 1000 倍二分只从 9 次涨到 19 次。4.5 三个必须记住的坑坑 1mid溢出int mid (left right) / 2; // 错误left right 可能溢出 int mid left (right - left) / 2; // 正确 int mid (left right) 1; // 正确无符号右移当left和right都接近Integer.MAX_VALUE时相加会变成负数。坑 2循环条件写成left right会漏掉最后一个元素。必须是left right。坑 3忘记数组必须有序对无序数组二分结果完全随机。4.6 排序的成本不能忽略这是老师特别强调的一点无序数组直接使用有序数组的 O(log n) 算法是不可行的因为排序本身需要额外时间。现实数据往往是无序的。想用二分必须先排序。而常见排序算法冒泡、快速排序等的时间复杂度通常是O(n log n)。所以方案单次查找预处理适合场景线性查找O(n)无只查一次排序 二分O(log n)O(n log n)查很多次如果只查一次排序反而更亏。这就是为什么要根据查询频率选方案。五、哈希表不算排序直接算位置5.1 核心思想既然排序太贵能不能设计一种算法让给定任意数据时直接算出它在数组中的目标位置可以。用数据对数组长度取余下标 key % 数组长度比如数组长度 10数据计算存储下标99 % 10910101010 % 1001212 % 1023333 % 103查找时也遵循同样的规则要查 12 就重新算12 % 10 2直接看下标 2 的位置是否存在该数据。存取时间复杂度都是 O(1)因为不需要遍历直接通过计算定位。关键点存取规则必须严格一致。存的时候怎么算查的时候就得怎么算。5.2 哈希冲突问题来了不同数据可能算出相同位置。比如长度 10 的数组12 和 22 都会落到下标 2。这就是哈希冲突。如果直接覆盖写入原数据就丢了——原本位置存了 12新数据存入后 12 就彻底消失了。5.3 解法一线性探测法遇到冲突就往后顺位存。33 本该存 3 号位但被占了 → 存 4 号位缺点很明显查找时需要一直向后遍历直到遇到空位数组空间有限可能造成数据堆积删除元素会留下空洞处理起来很麻烦。5.4 解法二链地址法拉链法每个数组位置挂一条链表冲突的数据都挂到同一条链上。结构就是数组桶 链表解决冲突查找时先算下标定位到桶遍历这个桶的链表。复杂度分析链表较短时遍历耗时可忽略整体近似O(1)链表过长时退化为O(n)。这就是哈希表最坏情况是 O(n) 的原因。5.5 链表太长怎么办转红黑树Java 的 HashMap 做了优化当链表较短时保持链表结构数据量增多时会自动转为红黑树时间复杂度降到O(log n)。具体阈值JDK 8条件动作链表长度 ≥ 8 且数组容量 ≥ 64链表转红黑树红黑树节点数 ≤ 6退回链表元素数 容量 × 0.75扩容为 2 倍为什么是 8因为链表长度达到 8 的概率已经极低泊松分布此时转树的收益才大于成本。5.6 完整实现HashTableChaining.java实现了一个带扩容的链地址哈希表static class Node { int key; Node next; Node(int key) { this.key key; } } private Node[] buckets; private int size; private int collisions; private static final double LOAD_FACTOR 0.75; /** 取余法算下标。长度取 2 的幂时可以用 key (len-1) 代替 %更快 */ private int indexFor(int key) { return key (buckets.length - 1); } public void put(int key) { int idx indexFor(key); if (buckets[idx] null) { buckets[idx] new Node(key); } else { collisions; Node cur buckets[idx]; while (true) { if (cur.key key) return; // 已存在不重复插 if (cur.next null) break; cur cur.next; } cur.next new Node(key); // 尾插 } size; if (size buckets.length * LOAD_FACTOR) resize(); }实测put(9) → 下标 9 put(1010) → 下标 2 put(12) → 下标 12 put(33) → 下标 1 put(44) → 下标 12 put(25) → 下标 9 put(28) → 下标 12 插入后容量 16元素 7占用桶 4冲突 3 次最长链 3 get(12)桶 12链表走了 1 步 → 命中 get(33)桶 1链表走了 1 步 → 命中 get(999)桶 7链表走了 0 步 → 未命中极端冲突场景所有 key 都是 8 的倍数全部落到 0 号桶全冲突场景容量 8元素 6占用桶 1冲突 5 次最长链 6 get(40)桶 0链表走了 6 步 → 命中6 个元素要走 6 步退化成了 O(n)。扩容过程[扩容] 4 → 8重新散列 4 个元素 [扩容] 8 → 16重新散列 7 个元素 插入 0..9 后容量 16元素 10占用桶 10冲突 0 次最长链 15.7 五个关键细节哈希表牺牲了顺序性。它适合按 key 找 value不适合按范围查。冲突不可避免取余必然撞链地址法是最常用的解法。链表太长会退化所以 Java 8 转红黑树。扩容要重新散列全部元素很贵——能预估容量就先指定初始大小。长度用 2 的幂是为了把%换成更快的位运算 (len - 1)。// 两者等价但位运算更快 key % 16 key 15前提长度必须是 2 的幂否则不等价。六、链表内存不连续靠地址串起来6.1 结构链表节点在物理空间上分散存储每个节点包含两部分域存什么value数据域具体数据next指针域下一个节点的内存地址链表变量head存的是第一个节点的地址是整条链的起点。head → [5|·] → [7|·] → [9|·] → [11|null]6.2 遍历从 head 开始顺着 next 一个个走for (Node cur head; cur ! null; cur cur.next) { System.out.println(cur.value); }当 next 为 null 时说明到链表末尾了。6.3 链表查找为什么是 O(n)因为不能随机访问。数组可以通过下标直接定位任意元素O(1)但链表要找到第 n 个节点必须从头开始逐个遍历。实测LinkedListDemo.javaget(0) 走了 0 步值 5 get(3) 走了 3 步值 11访问第 3 个元素要走 3 步访问第 n 个要走 n 步。6.4 为什么链表不能二分二分查找每次要访问中间节点。在数组里arr[mid]是 O(1)在链表里找到中间节点要遍历 n/2 个节点。所以二分的折半优势完全消失反而更慢。链表的有序性并不能优化查找效率这是链表和数组在访问机制上的本质区别。6.5 插入和删除只改指针链表的优势在这里。头部插入Node node new Node(v); node.next head; // 新节点指向原头 head node; // head 指向新节点只改 2 个指针O(1)。中间插入在 index 位置Node prev head; for (int i 0; i index - 1; i) prev prev.next; // 找前驱O(n) Node node new Node(v); node.next prev.next; // 先接后面 prev.next node; // 再断前面找位置是 O(n)但改指针是 O(1)不需要搬动任何元素。对比数组数组中间插入要把后面所有元素后移一位O(n) 次内存拷贝。6.6 一个必须记住的顺序node.next prev.next; // 先接后 prev.next node; // 再断前顺序反了会怎样如果先prev.next node那原来的prev.next就丢了后面整条链断掉再也找不回来。6.7 双向链表每个节点多存一个pre指针指向前驱static class DoublyNode { int value; DoublyNode pre, next; }好处可以从任意节点向前或向后遍历。 代价每个节点多存一个指针插入删除时要多维护一个指针。实测正向1 2 3 反向3 2 1只要掌握了单向链表的增删改查双向链表就很容易上手主要区别是需要额外处理 pre 指针。6.8 数组 vs 链表完整对比操作数组链表按下标访问O(1)O(n)头部插入O(n) 要后移O(1)中间插入O(n) 要后移O(n) 找位置 O(1) 改指针尾部插入O(1) 均摊O(1)有尾指针时查找某个值O(n)无序/ O(log n)有序二分O(n)内存连续可能扩容搬移分散每个节点多存指针缓存友好度高连续内存CPU 缓存命中率高低节点分散容易缓存未命中最后一行是实际开发中很重要但课上没展开的点数组在真实机器上往往比链表快得多即使理论复杂度一样因为 CPU 缓存喜欢连续内存。七、树从一条链到分叉7.1 为什么需要树链表查找是 O(n)哈希表虽然 O(1) 但丢失了顺序。有没有一种结构既能保持有序又能 O(log n) 查找有就是树。7.2 树的基本概念树结构和现实中的树相反根节点在最上方向下分叉形成子节点。概念含义根节点root最顶层的起始节点父节点上级节点子节点下级节点左子树 / 左孩子左侧分支右子树 / 右孩子右侧分支叶子节点没有子节点的末端节点树高 / 层数从根开始数根是第 1 层分类二叉树每个节点最多两个子节点多叉树子节点数量较多通常超过 100 个。多叉树的优势在于存储大量数据时能保持较低的树高从而提升效率——这就是后面 B 树的思路。7.3 有序二叉树二叉搜索树规则只有一条每个节点的左子节点值 父节点值 右子节点值。构建过程第一个值直接作为根节点后续每个新值从根开始比较比当前节点小就往左走大就往右走直到找到空位插入。比如插入50, 30, 70, 20, 40, 60, 8050 / \ 30 70 / \ / \ 20 40 60 807.4 中序遍历一定有序这是二叉搜索树最重要的性质中序遍历左 → 根 → 右的结果一定是从小到大排列。private void inorder(Node n, StringBuilder sb) { if (n null) return; inorder(n.left, sb); sb.append(n.value).append( ); inorder(n.right, sb); }实测输出中序遍历一定是从小到大20 30 35 40 45 50 60 65 70 807.5 查找每次排除一半子树从根开始比较目标等于当前节点 → 找到目标小于当前节点 → 去左子树找目标大于当前节点 → 去右子树找。每比较一次就排除掉一整棵子树。7.6 树高的数学关系二叉树第 k 层的节点数第 1 层2⁰ 1 第 2 层2¹ 2 第 3 层2² 4 第 k 层2^(k-1)总节点数前 k 层X 2⁰ 2¹ 2² ... 2^(k-1) 2^k - 1反推树高2^k X 1 k ≈ log₂X所以理想情况下树高是 log₂X查找复杂度O(log n)。7.7 但 O(log n) 是有条件的这是整节课最重要的坑普通二叉搜索树的 O(log n) 并不稳定。如果树不平衡比如退化成链表效率会下降到 O(n)。构造一个最坏情况按顺序插入 1, 2, 3, ..., 10。1 \ 2 \ 3 \ ...每个新节点都比上一个大全部挂在右边树变成一条向右的链。实测BinarySearchTree.java 有序插入退化成链表 节点数 10树高 10 —— 已经完全退化成一条向右的链 查找 10比较 10 次命中 查找 11比较 10 次未命中查找 10 要比较 10 次和遍历链表没有区别。数据量放大后的对比数据量 随机树高 有序树高 log2(n) ------------------------------------------------ 100 14 100 6.6 1000 22 1000 10.0 10000 33 10000 13.3注意即使是随机插入树高14/22/33也比理论值 log₂n6.6/10/13.3高不少。因为随机二叉搜索树的平均高度约为3log₂n不是 log₂n。这就引出了下一节课的主题平衡二叉树——插入后强制旋转把树高压回 log n。7.8 二叉搜索树的完整实现static class Node { int value; Node left, right; Node(int value) { this.value value; } } /** 插入从根开始比小往左、大往右直到空位 */ void insert(int v) { if (root null) { root new Node(v); size; return; } Node cur root; while (true) { if (v cur.value) return; // 不存重复值 if (v cur.value) { if (cur.left null) { cur.left new Node(v); size; return; } cur cur.left; } else { if (cur.right null) { cur.right new Node(v); size; return; } cur cur.right; } } } /** 查找返回比较次数 */ int search(int target) { Node cur root; int compares 0; while (cur ! null) { compares; if (target cur.value) return compares; cur (target cur.value) ? cur.left : cur.right; } return -1; }八、学习路线老师给的几条实用建议这部分不是技术但很值钱。8.1 关于力扣必须注册力扣账号才能使用相关资源题目不是最终考核目标而是往年面试真题——这些题目曾被面试官用于现场考察所有题目都能在力扣题库中找到题库题目没按顺序排列但都是基础且规整的练习素材建议从数组、字符串、排序这些即将讲解的类型入手力扣第一题就曾出现在真实面试中。8.2 关于基础基础不牢地动山摇。Java 入门很简单用变量和函数就能开始操作没学过 Java 也不影响学数据结构但前期基础不扎实后续做项目会明显吃力甚至跟不上很多同学后期调班或学习困难根本原因是前期基础没打好随着课程节奏加快需要自主搜索和写项目时基础薄弱就会暴露。8.3 关于课程节奏前期以讲授为主同时布置探索任务后期减少讲解增加自主探索比重这不同于高中应试教育不是所有考试内容都会在课堂直接教需要培养主动探索能力实际求职中大公司往往使用内部定制框架而非 Spring Boot 等教学框架需要培养适应能力。8.4 关于 AI 工具初期学习算法和项目时不要依赖 AI必须等到能一眼识别代码错误的熟练程度后才能将其作为辅助工具。这条建议很实在。AI 能帮你写出能跑的代码但不能替你建立看到这段代码就知道哪里会错的直觉。8.5 关于刷题方法不要死磕想不出就参考 AI 提示或精选题解方法不唯一哈希映射和暴力枚举效率明显不同平台会显示算法效率排名这正是评判标准前期不必过分追求效率先用暴力破解把代码写出来随着学习深入重点转移到优化时间复杂度上。一句话先跑通再跑快。8.6 关于时间分配有疑问随时提问课上不懂可以立即打断高效学习避免重复听课把省下的时间用来实践要么多写项目丰富简历要么直接去实习。九、这一篇的知识地图数据结构 ├─ 目标提高大规模数据的操作效率 ├─ 衡量工具时间复杂度 │ ├─ 不看执行时间硬件/数据/调度不可控 │ ├─ 看执行次数与 n 的函数关系 │ ├─ 只保留主导项去掉系数和低阶项 │ └─ 常见量级O(1) O(log n) O(n) O(n log n) O(n²) │ ├─ 数组 │ ├─ 内存连续 → 地址 首地址 下标 × 元素大小 → O(1) │ ├─ 无序查找 O(n)有序二分 O(log n) │ └─ 中间插入/删除 O(n) │ ├─ 二分查找 │ ├─ 前提有序 │ ├─ left / right / midleft right 终止 │ ├─ 每次砍一半 → O(log n) │ └─ 排序成本 O(n log n)不能白拿 │ ├─ 哈希表 │ ├─ 下标 key % 长度 → 存取 O(1) │ ├─ 冲突线性探测 / 链地址法 │ ├─ 链表过长 → 红黑树 O(log n) │ └─ 用 2 的幂长度 位运算加速 │ ├─ 链表 │ ├─ 节点 value next │ ├─ 查找 O(n)不能二分 │ ├─ 插入/删除改指针 O(1) │ └─ 双向链表多一个 pre │ └─ 树 ├─ 根/父子/叶子二叉树/多叉树 ├─ 有序二叉树左 父 右 ├─ 第 k 层 2^(k-1)总数 2^k - 1 ├─ 理想树高 log₂n └─ 会退化有序插入 → 链表 → O(n)十、关键概念 公式速查概念结论数据结构的作用整理数据提高查找/修改效率时间复杂度的定义执行次数随数据量变化的趋势大 O 的取舍只留最高阶项去掉系数和低阶项复杂度排序O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ)数组地址公式首地址 下标 × 元素字节数int 占用4 字节 / 32 位long 占用8 字节 / 64 位内存寻址最小单位1 字节 8 比特无序数组查找O(n)平均 n/2 次二分查找复杂度O(log n)最多 ⌊log₂n⌋1 次二分终止条件left right二分 mid 写法(left right) 1排序复杂度通常 O(n log n)哈希定位key % 数组长度哈希冲突解法线性探测 / 链地址法Java 8 转红黑树阈值链表 ≥ 8 且容量 ≥ 64负载因子0.75链表节点组成value 域 next 域链表查找O(n)无法二分双向链表多一个 pre 指针二叉树第 k 层节点数2^(k-1)二叉树前 k 层总数2^k - 1二叉搜索树规则左 父 右中序遍历结果一定有序随机二叉搜索树平均高度约 3log₂n退化的最坏高度n变成链表十一、这节课要掌握什么三条主线复杂度是选型工具。看到 O(n²) 就要想办法优化看到 O(log n) 要知道它依赖有序或平衡这个前提。数组和链表是两种基本取舍。数组换随机访问链表换插入删除没有绝对优劣。哈希是用计算换查找。它把 O(n) 降到 O(1)代价是丢失顺序、必须处理冲突。下一节要解决的问题是普通二叉搜索树会退化怎么让它稳定在 O(log n)答案就是平衡二叉树和红黑树。配套代码文件作用demos/data-structures/src/cn/ts/ds/ArraySearch.java地址计算、O(n) vs O(1)、查找次数对比demos/data-structures/src/cn/ts/ds/BinarySearchTrace.java二分查找逐步追踪demos/data-structures/src/cn/ts/ds/HashTableChaining.java取余哈希 链地址法 扩容demos/data-structures/src/cn/ts/ds/LinkedListDemo.java单链表 / 双向链表操作demos/data-structures/src/cn/ts/ds/BinarySearchTree.java二叉搜索树 退化演示编译运行