波仔
⚙️ 第四章 让内存化方为圆
📄 一句话概括

数组＝挨着放；地址＝基址 ＋ 下标 × 元素长度，所以按下标取永远一样快，按值找却仍要一个个看。

📝 本节和前面几节的关系

4.3 有了指针这个工具，这一节用它摆出第一个形状：数组。

一、数组就是把数据挨着放

数组的规矩只有一条：所有元素紧挨着排，中间不留缝。 正因为挨着，才有那个著名的换算公式： 元素地址 = 基址 + 下标 × 每个元素占几字节。 比如基址 1000、每个元素 4 字节，那么下标 5 的地址就是 1000 + 5 × 4 = 1020。

二、为什么下标从 0 开始

因为这样算最省事：下标直接就是【要跳几格】。 若从 1 开始，公式得多减一次：基址 + (下标 - 1) × 长度。 省下的这一步乘法不算大事，但它每天要被算几亿亿次，所以约定就这么定下来了。 所以【从 0 开始】不是怪癖，是让换算少一步的设计。

三、快在哪，慢在哪

按下标取快：不管下标是 0 还是 100 万，都是乘一下加一下，花的步骤一样多。 按值找慢：数组自己不会排序也不会建索引，只能从头一个个比，平均要翻一半。 中间插删慢：插一个进去，后面所有元素都得往后挪一格——这是数组最贵的一项操作。 所以数组适合元素个数确定、以【按下标取】为主的场合。

四、它是别的结构的地基

栈、队列、环形缓冲区、堆、哈希表——底层几乎都是数组。 它们在数组之上只加了一条规矩：从哪一头进出、怎么算下标。 这也呼应了章名：内存是方方正正的一串格子，你要什么形状，靠规矩去摆。 下一节先看最简单的一种摆法：进出顺序不同的三个容器。

五、动手 Demo：用好内存先从数组开始

数组＝把一串数据挨着放，于是求地址只要一步乘法： 元素地址 = 基址 + 下标 × 每个元素占几字节。

import array
arr = array.array("i", [10, 20, 30, 40, 50, 60])
base, size = 1000, arr.itemsize
for i, v in enumerate(arr):
    print("下标 %d  值 %d  地址 %d" % (i, v, base + i * size))

实跑输出：

--------------------------------------------------------------------
用好内存先从数组开始
--------------------------------------------------------------------

**数组＝把一串数据挨着放。** 挨着放之后，求第 n 个元素在哪儿只要一步乘法：

    元素地址 = 基址 + 下标 × 每个元素占几字节

  下标     元素值     地址 = 1000 + 下标 × 4
  -------------------------------------------
  0        10         1000
  1        20         1004
  2        30         1008
  3        40         1012
  4        50         1016
  5        60         1020

  两个要点：
    **按下标取数据，不管下标多大多小都一样快**——都是乘一下加一下。
    **但按值找数据仍然要一个个看**——数组自己不会排序、也不建索引。

  这就解释了二分查找的两个前提：**排好序**，以及**能随便跳**。
  数组一跳就到中间；链表却得从头一格一格爬——这正是下一节和再下一节的区别。

每个下标对应的地址都是等差的，公差正好是元素长度。 这就是【按下标取永远一样快】的原因——它只是乘一下加一下。

30 秒实验

  1. 把基址改成 2000、元素大小改成 8，重新算一遍各下标的地址。
  2. 想想一个 4 行的二维数组，第 3 行第 2 列（下标 2、1）该怎么算。

常见误区

  1. 以为数组会帮你找值。它只会按位置给，找值仍要自己遍历。
  2. 以为数组插入和读取一样快。读取是乘一下，插入要搬一串。
自测三问（点开对答案） 1. 数组元素地址怎么算？ —— 基址 + 下标 × 每个元素占的字节数。 2. 为什么下标通常从 0 开始？ —— 这样下标直接就是要跳的格数，换算公式少一步减法。 3. 数组最快和最慢的操作分别是什么？ —— 按下标读取最快（一步乘法）；在中间插入或删除最慢（要搬动后续元素）。

相关笔记