详解数据结构中的“数组”与编程语言中的“数组”的区别和联系

我会带着你远行 2022-01-19 04:09 126阅读 0赞

在大部分数据结构和算法书籍中，数组作为最基础的数据类型，是最先被介绍的。一般我们都是这么定义数组的。

> 数组这种数据结构，是存储相同数据类型的一块连续的存储空间。  
> 解读一下这个定义的话，那就是：数组中的数据必须是相同类型的，数组中的数据必须是连续存储的。  
> 只有这样，数组才能实现根据下标快速地（时间复杂度是O(1)）定位一个元素。

但是，如果你是一名比较喜欢钻研的程序员，你会发现，在你所熟悉的编程语言中，”数组“这种数据类型，并不一定完全符合上面的定义。比如Javascript这种语言中，数组中的数据不一定是连续存储的，也不一定非得是相同类型，甚至数组可以是变长的。

var arr = new Array(4,'hello', new Date());
    复制代码

除此之外，大部分数据结构和算法书籍中，在讲到二维或者多维数组中数据的存储方式的时候，一般都会这么说:

> 二维数组中的数据，是先按行再按列（或者先按列后按行），依次存储在连续的存储空间中。  
> 如果二维数组定义为a\[n\]\[m\]，那a\[i\]\[j\]的寻址公式为下面这样（先按行后按列存储）：  
> address\_a\[i\]\[j\] = address\_base + (i\*m+j) \* data\_size;  
>

但是，在有些编程语言中，二维数组并不满足上面的说法和寻址公式。比如，Java中的二维数组，第二维可以是不同长度的，而且第二维的三个数组（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，来给你展示一下，几种比较有代表性的数组实现方式。

### 1. C/C++中数组的实现方式 ###

C/C++中的数组，是非常标准的数据结构中的数组，也就是连续存储相同类型的数据的一块内存空间。在C/C++中，不管是基本类型数据，比如int、long、char，还是结构体、对象，在数组中都是连续存储的。我举了一下例子，你可以看下。

int arr[3];
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    复制代码

数组arr中存储的是int基本类型的数据，对应的内存存储方式，如果用画图的方式表示出来的话，就是下面这样子。从图中可以看出，数据是存储在一片连续的内存空间中的。

刚刚讲的是用数组存储基本类型数据的例子，我们再来看：用数组存储struct结构体（或者class对象）的例子。

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';
    复制代码

如果我们把这个结构体数组，用画图的方式表示出来，就是下面这个样子。我们发现，结构体数组中的元素，也是存储在一片连续的内存空间中的。

刚刚讲的都是一维数组的数据存储方式，我们再来看下，二维数组的数据存储方式。注意，多维数组跟二维数组大同小异，我们就拿二维数组来讲解。我们来看下面这段代码。

struct Dog { 
      char a;  
      char b;
    };
    struct Dog arr[3][2];
    复制代码

我们把上面的struct Dog arr\[3\]\[2\]对应的数据存储方式，用图画出来的话，就是下面这样子的。从图中，我们发现，C/C++的二维数组，跟数据结构中二维数组是一样的，数据是先按行后按列，并且是连续存储的。

刚刚我们分析了C/C++的基本数据类型数组、结构体或对象数组、以及二维数组。它们的数据存储方式，完全符合数据结构和算法中数组的定义。

你还知道，在其他哪些编程语言中，数组的定义完全符合数据结构中数组的定义吗？

### 2. Java中数组的实现方式 ###

看完了C/C++中的数组，我们再来看下，Java中的数组。Java中的数组就有点跟数据结构中数组的定义不一样了。我们还是分三种情况来分析。这三种情况分别是：基本数据类型数组、对象数组、二维数组（或多维数组）。

首先，我们先来看下基本数据类型数组，也就是说，数组中存储的是int、long、char等基本数据类型的数据。我们还是拿一段代码来举例。

int arr[] = new int[3];
    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;
    复制代码

如果我们把arr中数据在内存中的存储方式，用图画出来的话，就是下面这个样子的。注意，new申请的空间在堆上，arr存储在栈上。arr存储的是数组空间的首地址。

从图中来看，在Java中，基本数据类型数组还是符合数据结构中数组的定义的。数组中数据是相同类型的、并且存储在一片连续的内存空间中。

看完了基本数据类型数组，我们再来看下对象数组，也就是说，数组中存储的不是int、long、char这种基本类型数据了，而是对象。我们还是拿一个例子来说明。

class Person {  
      private String name;  
      public Person(String name) {
        this.name = name;  
      }
    }
    
    Person arr[] = new Person[3];
    arr[0] = new Person("0");
    arr[1] = new Person("1");
    arr[2] = new Person("2");
    复制代码

在上面的代码中，数组arr中存储是Person对象。同样，我们还是把数组中数据在内存中的存储方式，用画图的方式表示出来。

从图中，你有没有发现，在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。如果我们把这个数组在内存中的存储方式，用图画出来的话，就是下面这个样子。

刚刚这个二维数组存储的是基本数据类型，我们再来看下，如果二维数组中存储的是对象，那又会是怎么的数据存储方式呢？我们还是拿个例子来说明。

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("0");
    arr[1][1] = new Person("1");
    复制代码

在上面的代码中，Person arr\[\]\[\]是一个二维对象数组。对于它在内存中存储方式，你可以在纸上先画下，或者在自己脑海中想下，然后，再来对比一下我画的下面这张图。

我总结一下。在Java这种编程语言中，数组这种数据类型，除了存储基本数据类型的一维数组之外，对象数组、二维数组，都跟数据结构中数组的定义，有很大区别了。

### 3. JavaScript中数组的实现方式 ###

如果我们说，Java中的数组，只是根据语言自己的特点，在数据结构数组基础之上，做的改造的话，那JavaScript这种动态脚本语言中的数组，完全就被改的“面目全非”了。

在开头的时候，我们已经提到过，JavaScript中的数组，可以存储不同类型的数据，数组中的数据也不一定是连续存储的（按照下标随机访问的效率不高），并且还能支持变长数组。这完全就是跟数据结构中数组的定义反着的。如果你是一名Web前端工程师，你应该会对此很困惑吧？

实际上，JavaScript中数组的底层实现原理，已经不是依赖数据结构中的数组了。也就是说，JavaScript中的数组只不过是名字叫数组而已，跟数据结构中数组没啥太大关系。

接下来，我们就来看下，JavaScript中的数组，底层是如何实现的呢？实际上，JavaScript中的数组，会根据你存储数据的不同，选择不从的实现方式。

如果数组中存储的是相同类型的数据，那JavaScript就真的用数据结构中数组来实现。也就是说，会分配一块连续的内存空间来存储数据。

如果数组中存储的是非相同类型的数据，那JavaScript就用类似散列表的结构来存储数据。也就是说，数据并不是连续存储在内存中的。这也是JavaScript数组支持存储不同类型数据的原因。

如果你往一个存储了相同类型数据的数组中，插入一个不同类型的数据，那JavaScript会将底层的存储结构，从数组变成散列表。

如果你熟悉JavaScript，你应该知道，JavaScript为了照顾一些底层应用的开发者，还提供了另外一种数据类型，叫做ArrayBuffer。而ArrayBuffer才符合标准的数据结构中数组的定义。它分配一片连续的内存空间，仅仅用来存储相同类型的数据。

### 最后，总结 ###