一本正经的聊数据结构（2）：数组与向量

前文传送门：

一本正经的聊数据结构（1）：时间复杂度

引言

这个系列没有死，我还在更新。

最近事情太多了，这篇文章也是断断续续写了好几天才凑完。

上一篇我们介绍了一个基础概念「时间复杂度」，这篇我们来看第一个真正意义上的数据结构「数组」。

那为什么题目中还会有一个向量呢？这个是什么东西？

不要急，且听我慢慢道来。

内存

在聊数组之前，需要先了解一个硬件，这个就是我们电脑上内存。

先了解一下内存的物理构造，一般内存的外形都长这样：

上面那一个一个的小黑块就是内存颗粒，我们的数据就是存放在那个内存颗粒里面的。

每一个内存颗粒叫做一个 chip 。每个 chip 内部，是由 8 个 bank 组成的。大致长这样（灵魂画手挖掘机老师开始上线）：

而每一个 bank 是一个二维平面上的矩阵，矩阵中每一个元素中都是保存了 1 个字节，也就是 8 个 bit ，比如这样：

所以准确的来讲，我们的数据就是放在那一个一个的元素中的。

数组

在 C 、C++ 、Java ，都将数组作为一个基础的数据类型内置。

很可惜，在 Python 中未将数组作为一个基础的数据类型，虽然 Python 中的 list 和数组很像，但是我更愿意叫它列表，而不是数组。

那么数组究竟是啥呢，我这里借用下邓俊辉老师「数据结构」中的定义：

若集合 S 由 n 个元素组成，且各元素之间具有一个线性次序，则可将它们存放于起始于地址 A 、物理位置连续的一段存储空间，并统称作数组（ array ） ，通常以 A 作为该数组的标识。具体地，数组 A[] 中的每一元素都唯一对应于某一下标编号，在多数高级程序设计语言中，一般都是从 0 开始编号，依次是 0 号、 1 号、 2 号、 ...、 n - 1 号元素。

其中，对于任何 0 <= i < j < n ， A[i] 都是 A[j] 的前驱（ predecessor ） ， A[j] 都是 A[i] 的后继（ successor ） 。特别地，对于任何 i >= 1， A[i - 1] 称作 A[i] 的直接前驱（ intermediatep redecessor ） ;对于任何 i <= n - 2 ， A[i + 1] 称作 A[i] 的直接后继（ intermediate successor ） 。 任一元素的所有前驱构成其前缀（ prefix ） ，所有后继构成其后缀（ suffix ） 。

概念永远都是这么的枯燥、乏味以及看不懂。

没关系，继续我的非本职工作「灵魂画手」。

首先了解第一个知识点，数组是放在内存里的，内存的结构我们前面介绍过了，那么数组简单理解就是放在一个一个格子里的，就像这样：

实际上不是这么放的哈，简单理解可以先这么理解，这个涉及到内存对齐的知识，有兴趣的同学可以度娘了解下。

便于理解，我在字母 A 后面加上了数字，这个数字理解为编号，并且是从 0 开始的。

这个结构让我想起了糖葫芦：

数组中的数字就像是穿在棍子上的山楂，大晚上的看的有点流口水。

前驱和后继可以看下面这张图：

A3 是 A4 的直接前驱， A5 是 A4 的直接后继，而排在 A4 前面的都叫 A4 的前驱，排在 A4 后面的都叫 A4 的后继。

向量

那么啥是向量（ vector ）呢？

这个东西可以简单理解为数组的升级版，在各种编程语言中，大多数都对向量的实现做了内置，不过很可惜，在 Python 中，向量未成为一个基础的数据结构。

那么我就只能对照着 Java 来聊了，向量这个数据结构在 Java 中的实现是： java.util.Vector ，用过 Vector 的应该都是上古 程序员 了，这个 工具 类是伴随 JDK1.0 就有的，但是后面逐渐的弃用，原因我们后面有机会再聊，就不在这多说了。

第一个要聊的问题是，我们在使用数组的时候有什么不方便的地方？这个问题换一种问法，其实就是为什么我们需要使用向量（vector）。

首先，我们在使用数组的时候，需要声明数组的大小，因为程序需要根据我们声明的数组大小去向内存申请空间，这就很尴尬了，如果在一个我并不清楚后续可能会用多少空间的场景中，我就没有办法去声明一个数组，因为数组是定长的。

然后就是数组需要是同一数据类型，比如我一个数组如果放入了数组，那么就不能再放入字符串，就不提更加复杂的数据结构，这完全都是因为数组的特性决定的，因为数组在内存上是连续的。

那么遇到了上面的问题怎么办，当然是解决问题咯，这样，数组的第一个升级版 Vector 就出来了，在创建的时候不需要声明大小，然后放入的数据不一定都要是同一个数据类型，比如我想放数字就放数字，想放集合就放集合，想放字符串就放字符串。

声明一点，向量（ Vector ）的实现是通过数组来实现的。

在 Java 的 Vector 的源代码中可以很清楚的找到证据：

protected Object[] elementData;

动态扩容

这里就会出现第一个问题，数组是定长的，那么向量为什么可以不定长？

当然是向量会自动扩容啦~~~~~

说到自动扩容，不禁让我想起来上面那个糖葫芦，当棍子放不下山楂还想往上放怎么办，当然是把棍子变长点咯：

当然，我们在程序中扩容并不是直接把原有数组加长，因为数组的要求是物理空间必须地址连续，而我们却无法保证，其尾部总是预留了足够空间可供拓展。

所以能想到的做法就是另行申请一个容量更大的数组，并将原数组中的成员集体搬迁至新的空间，比如这样：

那么，问题又产生一个，每次变长（扩容）的时候，变长（扩容）多少合适呢？

因为每次扩容的时候，元素的搬迁都需要花费额外的时间，这对性能是一个损耗，我们并不希望这个损耗过大，那么是不是可以一次扩容扩的足够大呢？当然也不行，这样会造成内存的浪费，虽然内存便宜，但也不是这么浪费的。

比如初始长度是 10 ，第一次扩容直接扩容到 100 ，第二次到 1000 ，这个就太夸张了，这里可以直接参考 JDK 的源码，看下大神是怎么扩容的。

篇幅原因我就不带大家在这看 Java 的源码了，直接说结果，照顾下学 Python 的同学：

在 Java 中 Vector 的初始长度定义为 10 ，当元素个数超过原有容量长度 1 时，进行扩容，每次扩容的大小是原容量的 1 倍，那么就是第一次扩容是从 10 变成了 20 。

至于为什么是扩大 1 倍而不是其他这里就不展开讨论了，实际上 Java 在另一个数据结构列表（ List ）中扩容的大小是 0.5 倍 + 1 。

不同数据类型

还是拿上面的糖葫芦举例子，如果一个杆上只能穿山楂，那么它是一个糖葫芦（数组），但是，只想穿山楂的糖葫芦不是一个好糖葫芦。

但我在吃山楂的同时还想吃臭豆腐，小龙虾，扇贝，生蚝，帝王蟹，成年人的世界，就是我全都要这么朴实无华。

然后糖葫芦开启了超进化模式：

变成了下面这玩意：

这个功能在 Java 中的实现是通过 Object 数组来实现的，因为 Object 在 Java 中是所有类的超类，这个接触过 Java 的同学应该都清楚，如果没有接触过 Java ，可以这么理解，借用道德经里一句话：

道生一，一生二，二生三，三生万物

而这个 Object 就是那个一，由这个一才产生了丰富多彩的 Java 世界，所以 Object 数组是可以转化为任何类型的。

小结

小结一下吧，我们聊了一个最简单的数据结构，数组，还从数组中引申出来了向量（ Vector ），很遗憾，Python 中没有这两个基础数据结构。

在向量（ Vector ）中，我们介绍了向量（ Vector ）的两个不同于数组的特性，一个是动态扩容，还有一个是向量中可以放不同的数据类型，这对比数组极大的方便了我们日常的使用。

顺便说一句，虽然很多数据结构都是基于数组的，包括本文介绍的 Vector ，还有后面会介绍到的列表 List ，但是我们在实际的使用中是很少会直接使用数组的，基本上都是使用数组的超进化体。

参考

https://zhuanlan.zhihu.com/p/83449008