数组

数组 #

几乎每种语言都有数组这种数据类型，为什么数组的下标都是从 0 开始？

数组的随机访问 #

数组是一种线性表的数据结构，用一组连续的内存空间，来存储一组相同类型的数据。

线性表

线性表就是数据排程一条线一样的结构。线性表上的数据只有前后两个方向。（链表，栈，队列也是线性表结构）。

二叉树，图，堆等是非线性表结构。非线性表中数据不再是简单的前后关系。

连续的内存空间和相同类型的数据

连续的内存空间和相同类型的数据，正式因为这两个限制，才使数组可以实现随机访问。但是这两个限制也让其他的 操作变得效率低下，比如在数组中插入或删除一个值，为了保证数据的连续，就必须进行数据搬移。

例如：一个长度为 10 的 int 类型的数组 a := new([10]int)。计算机给数组 a[10]，分配了一块连续内存空间 1000～1039， 其中，内存块的首地址为 base_address = 1000。

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通 过下面的寻址公式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

data_type_size 表示数组中每个元素的大小。

数组的插入和删除 #

为什么说数组的插入和删除效率低？

比如一个数组的长度为 n，如果要插入一个元素在 k 位置，时间复杂度是多少?

如果在数组的末尾插入，那么不需要移动数据，在末尾加入元素即可，这时是最好时间复杂度，为 O(1)。如果在数组的开头插入元素，那么所有元素一次向 后移动一位，这时是最坏时间复杂度，为 O(n)。由于在每个位置插入的概率是一样的，那么平均时间复杂度为 (1 + 2 + ...n)/n = O(n)。

删除元素和插入元素差不多。如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况 时间复杂度也为 O(n)。如果数组是无序的，多次删除操作可以集中在一起执行。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组 没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

如何避免移动数据 #

如果数组是有序的，那么插入元素就必须移动数据。对于无序的数组，如果要在 k 位置插入元素，为了避免移动数据，可以直接将 k 位置的原数据移动到 数据末尾，把新的元素放在 k 位置。

为什么数组的下标都是从 0 开始 #

下标就是"偏移 (offset)"，上面的例子中数组 a 的首地址是 a[0]，也就是偏移为 0 的位置。a[k] 就表示偏移 k 个 data_type_size 的 位置，那么 a[k] 内存地址为 a[k]_address = base_address + k * data_type_size。

但是如果数组从 1 开始，a[k] 内存地址就是 a[k]_address = base_address + (k - 1) * data_type_size，可以看出 多了一次减法运算， CPU 就多一次减法指令。对于数组这种基础数据结构，少一次操作就可以提高一点效率。

也可能是历史原因，C 语言是从 0 开始，之后的语言也都效仿了 C 语言。

数组越界 # 

func OutOffArray()  {
    i := 0
    var a [3]int
    for ; i <= 3; i ++ {
        a[i] = 0
        fmt.Printf("hello %d.\n", i)
    }
}

数组大小为 3，a[0]，a[1]，a[2]，但是上面的代码循环的结束条件错写为了 i<=3 而非 i<3，所以当 i=3 时，数组 a[3] 访问 越界。

在 Go 中会报错：

panic: runtime error: index out of range [recovered]
        panic: runtime error: index out of range

但是在 C 语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据数组寻址公式，a[3] 也会被定位到某块不属于数组的内存 地址上。数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要 数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。

为什么 Javascript 的数组可以存储不同类型的数据 #

Javascript 基本类型数据都是直接按值存储在栈中的(Undefined、Null、布尔、数字和字符串)，每种类型的数据占用的内存空间的大小是确定的，并由系统 自动分配和自动释放。这样带来的好处就是，内存可以及时得到回收，相对于堆来说，更加容易管理内存空间。

Javascript 引用类型数据被存储于堆中 (如对象、数组、函数等，它们是通过拷贝和 new 出来的），但是引用类型的数据的地址指针是存储于栈中的。 当想要访问引用类型的值的时候，需要先从栈中获得对象的地址指针，然后，在通过地址指针找到堆中的所需要的数据。

Javascript 中数组类型与其他语言不太一样：

  • 数组中可以存放不同的数据结构，可以存放数组、对象、Number、Undefined、Null、String、Symbol、Boolean、Function 等等。
  • 数组的 index 是字符串类型的，之所以你可以通过 arr[1]，获得对应的数据，是因为 Javascript 自动将数字转化为字符串。

Javascript 中数组 JSArray 是继承自 JSObject，也就是说，数组是一个特殊的对象。内部也是 key-value 的存储形式。

JS 的数组是以类似哈希表的方式存在的。key 为 0，1，2，3 ... 这种索引，value 就是数组的元素对于读取操作，哈希表的效率并不高，而修改删除 的效率比较高。

现代浏览器对数组的内存分配进行了优化：

  1. 对于同构的数组，也就是，数组中元素类型一致，会创建连续的内存分配
  2. 对于不同构数组，按照哈希表方式创建
  3. 如果你想插入一个异构数据，那么就会重新解构，以哈希表方式重新创建
  4. 新创建的空数组，默认的创建连续的内存分配

Javascript 中提供了 ArrayBuffer 对象，它可以创建连续的内存。

https://juejin.im/post/5d80919b51882538036fc87d#2