#技术派的书架#

在 2.1 节中，我们提到了数组是存储相同数据类型的一块连续的存储空间。解读一下：数 组中的数据必须是相同类型的，数组中的数据必须是连续存储的。只有这样，数组才能实现根 据下标快速地访问数据。 有些读者可能会发现，在有些编程语言中，“数组”这种数据类型并不一定完全符合上面 的定义。例如，在 JavaScript 中，数组中的数据不一定是连续存储的，也不一定是相同类型的， 甚至，数组还可以是变长的。

var arr = new Array(4, 'hello', new Date());

在大部分关于数据结构和算法的图书中，在提到二维数组或者多维数组中数据的存储方式 的时候，一般会这样介绍：二维数组中的数据以“先按行，再按列”（或者“先按列，再按行”） 的方式依次存储在连续的存储空间中。如果二维数组定义为 a[n][m]，那么 a[i][ j] 的寻址公式 如式（2-4）所示（以“先按行，再按列”的方式存储）。

但是，在有些编程语言中，二维数组并不满足上面的定义，寻址公式也并非如此。例如， Java 中的二维数组的第二维可以是不同长度的，如下所示，而且第二维的 3 个数组（arr[0]、 arr[1] 和 arr[2]）在内存中也并非连续存储。

int arr[][] = new int[3][];
arr[0] = new int[1];
arr[1] = new int[2];
arr[2] = new int[3];

难道有些关于数据结构和算法的图书里的讲解脱离实践？难道编程语言中的数组没有完全 按照数组的定义来设计？哪个对呢？ 实际上，这两种讲法都没错。编程语言中的“数组”并不完全等同于我们在介绍数据结构 和算法的时候提到的“数组”。编程语言在实现自己的“数组”类型的时候，并不是完全遵循 数据结构中“数组”的定义，而是针对编程语言自身的特点，进行了相应的调整。 在不同的编程语言中，数组这种数据类型的实现方式不大相同。本节利用几种比较典型 的编程语言，如 C、C++、Java 和 JavaScript，向读者介绍一下几种比较有代表性的数组实现 方式。

C/C++ 中数组的实现方式

在 C/C++ 中实现的数组完全符合数据结构中的数组的标准定义，利用一块连续的内存空 间存储相同类型的数据。在 C/C++ 中，无论是基本的类型数据，如 int、long 和 char，还是结 构体、对象，在数组中都是连续存储的。我们通过例子来解释一下。

int arr[3];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;

在上面的代码中，数组 arr 中存储的是 int 类型的数据，对应 的内存存储格式如图 2-6 所示。从图 2-6 中可以看出，数据存储在一 块连续的内存空间中。 在上面的例子中，数组存储的是基本类型数据，下面我们看一 下在利用数组存储对象（在 C 语言中，对象也称结构体（struct））时，数组在内存的存储格式。

struct Dog { 
 char a; 
 char b;
};
struct Dog arr[3];
arr[0].a = '0'; 
arr[0].b = '1';
arr[1].a = '2'; 
arr[1].b = '3';
arr[2].a = '4'; 
arr[2].b = '5';

在上面的代码中，数组 arr 在内存中的存储格式如图 2-7 所示，数据也是存储在连续的 内存空间中的。 上面介绍的是一维数组的存储格式，下面介绍在 C/C++ 语言中多维数组的存储格式。注 意，多维数组与二维数组类似，我们就用二维数组进行讲解。我们看一下下面这段代码。

struct Dog {
 char a;
 char b;
};
struct Dog arr[3][2];

在上面的代码中，struct Dog arr[3][2] 对应的存储格式如图 2-8 所示。从图 2-8 中 可以发现，C/C++ 语言中的二维数组与数据结构中的二维数组是一样的，数据是以“先按行， 再按列”的方式连续存储的。

在上文中，我们分析了C/C++的基本数据类型数组、对象（结构体）数组，以及二维数组， 它们的数据存储格式完全符合数据结构中对数组的定义。

Java 中数组的实现方式

在介绍完 C/C++ 中的数组后，下面看一下 Java 中的数组。Java 中的数组的实现并没有完 全按照数据结构中数组的定义。我们还是分 3 种情况来分析：基本数据类型数组、对象数组和 二维数组（多维数组）。 首先，我们先来看一下基本数据类型数组，也就是说，数组中存储的是 int、long 和 char等基本数据类型的数据。我们还是利用一段代码来进行讲解。

int arr[] = new int[3];
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;

在上面的代码中，arr 数组中的数据在内存中的存储格式如图 2-9 所示。注意，new 申请 的空间在堆中，arr 存储在栈中。arr 存储的是数组空间的首地址。 从图 2-9 可以看出，在 Java 中，基本数据类型数组符合数据结构中数组的定义。数组中 的数据是相同类型的，并且存储在连续的内存空间中。 在介绍完基本数据类型数组后，我们再来看一下对象数组，也就是说，数组中存储的不是 int、long 和 char 这些基本类型数据，而是对象。我们还是用一个例子来说明。

public class Person { 
 private String name; 
 public Person(String name) { 
 this.name = name; 
 }
}
Person arr[] = new Person[3];
arr[0] = new Person("Peter");
arr[1] = new Person("Leo");
arr[2] = new Person("Cina");

在上面的代码中，数组 arr 中存储的是 Person 对象。同样，我们还是把数组中的数据 在内存中的存储格式用图表示，如图 2-10 所示。

从图 2-10 中可以看出，在 Java 中，对象数组的存储格式已经与 C/C++ 中的对象数组的存 储格式不一样了。在 Java 中，对象数组中存储的是对象在内存中的地址，而非对象本身。对 象本身在内存中并不是连续存储的，而是散落在各个地方。 在了解了一维数组的存储方式后，我们再来看一下 Java 中的多维数组。在上文提到过， 多维数组与二维数组类似，因此此处还是使用二维数组进行讲解。注意，Java 中的二维数组与 数据结构中的二维数组有很大的区别。在 Java 中，二维数组中的第二维可以是不同长度的。

int arr[][] = new int[3][];
arr[0] = new int[1];
arr[1] = new int[2];
arr[2] = new int[3];

在上面的代码中，arr 是一个二维数组，第一维长度是 3，第二维的长度各不相同：arr[0] 的长度是 1，arr[1] 的长度是 2，arr[2] 的长度是 3。arr 数组在内存中的存储格式如图 2-11 所示。

上面这个二维数组存储的是基本类型的数据，我们再来看一下在二维数组中存储对象时的 数据存储格式。我们还是用一个例子来说明。

Person arr[][] = new Person[3][];
arr[0] = new Person[1];
arr[1] = new Person[2];
arr[2] = new Person[3];
arr[0][0] = new Person("Peter");
arr[1][1] = new Person("Leo");

总结一下，在 Java 中，除基本类型一维数组之外，对象数组、二维数组与数据结构中的 数组的定义有很大区别。

JavaScript 中数组的实现方式

如果 Java 中的数组只是根据语言自身的特点，在数据结构中的数组基础之上做的改造的 话，那么 JavaScript 这种动态脚本语言中的数组完全被改得“面目全非”了。 在本章开头，我们提到过，JavaScript 中的数组可以存储不同类型的数据，数组中的数 据也不一定是连续存储的，并且能支持变长数组。这完全就是与数据结构中的数组的定义相 反的。 实际上，JavaScript 中的数组的底层实现原理已经完全不符合数据结构中的数组的定义了。也就是说，JavaScript 中的数组只不过是名字叫数组而已，与数据结构中的数组几乎没有关系。 接下来，我们就来看一下 JavaScript 中的数组是如何实现的。实际上，JavaScript 中的数 组会根据存储数据的不同，选择不同的实现方式。 如果数组中存储的是相同类型的数据，JavaScript 就真的会用数据结构中的数组来实现。 也就是说，此时会分配一块连续的内存空间来存储数据。 如果数组中存储的是非相同类型的数据，JavaScript 就会用类似哈希表的结构来存储数据。 也就是说，此时数据并不是连续存储在内存中的。这是 JavaScript 中的数组支持存储不同类型 数据的原因。 如果我们向一个存储了相同类型数据的数组中插入一个不同类型的数据，那么 JavaScript 会将底层的存储结构从数组变成哈希表。 实际上，JavaScript 为了“照顾”一些底层应用的开发者，还提供了 ArrayBuffer 这样一种 数据类型。ArrayBuffer 完全符合标准的数据结构中的数组的定义。ArrayBuffer 分配一块连续 的内存空间，仅仅用来存储相同类型的数据。

本文摘自《数据结构与算法之美》

20个经典数据结构与算法，100个真实项目场景案例，300多幅算法手绘图解，一本在手，算法全有，面试大厂不愁！

豆瓣评分9.5，极客时间畅销专栏集结成书，内容更新30%

下一篇

• 链表（上）：如何基于链表实现 LRU 缓存淘汰算法

喜欢请关注+评论+转发哦