数组

数组

---

数组如何实现随机访问？

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

线性表（Linear List）：将数据排列成像线一样的结构。线性表上的数据最多只有前和后两个方向，除了数组之外，链表、队列、栈等也是线性表结构。

• 非线性表：（二叉树、堆、图等），在非线性表中数据之间不是简单地前后关系。

连续的内存空间和相同类型的数据：正是因为这两个限制，数组才能支持随机访问。但是为了保证连续性，想要在数组中删除、插入数据就需要做大量的数据搬移工作。

数组根据下标随机访问数组元素

• 当我们创建一个长度为10的int型数组时，计算机就会为该数组分配内存，比如分配了一块连续的内存空间1000~1039，其中受地址就为base_address=1000，这是计算机就会通过地址来访问内存中的数据。当计算机需要访问数组中的某个元素时，就会通过下面的寻址公式，计算出该元素存储的内存地址,，然后直接访问：

  a[i]_address = base_address + i * data_type_size

• 链表与数组：链表适合插入，删除，时间复杂度为O(1)，数组支持随机访问，根据下标随机访问的时间复杂度为O(1)

---

数组中低效的“插入”与“删除”

插入操作

插入操作的时间复杂度分析

• 数组末尾插入：不需要移动元素，时间复杂度为O(1)
• 数组头部插入：所有的数据都需要依次往后移动一位，时间复杂度为O(n)
• 数组中每个位置插入元素的概率是一样的，平均时间复杂度为(1+2+…+n)/n=O(n)。

删除操作（多次删除集中一起，提高删除效率）

与插入操作类似，若要删除第K个位置数据，为了内存连续性，也需要搬移数据。

时间复杂度与插入操作类似：最好情况下时间复杂度为O(1)，如果删除开头元素，则为最坏情况下时间复杂度O(n)，平均情况下时间复杂度也为O(n)

• 在删除数组中元素时，不一定每次都要将数组中的元素删除，可以先记录下来这样每次要输出的元素，删除操作并不是真正的搬移数据，只是将要删除的数据记录下来。当数组中没有足够多的空间时，再触发一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。
  • 扩展：JVM中的标记清除垃圾回收算法的核心思想
    • 算法分为“标记”和“清除”两个阶段：首先标记所需要回收的对象，遍历所有的GC ROOTS，将所有的GC ROOTS可达的对象标记为存活，在标记完成后统一回收所有被标记的的对象。
    • “标记-清除”和清除算法的两个问题：
      1. 效率问题：标记这两个过程的效率并不高效
      2. 空间问题：标记清楚后会产生大量不连续的内存碎片，碎片太多会导致以后程序运行中需要分配较大对象，无法找到足够连续内存二不得不提前触发另一次垃圾收集。

---

数组中的越界问题

int main(int argc,char * argv[]){
    int i=0;
    int a[3]={0};
    for(;i<=3;i++){
        a[i]=0;
        printf("hello world\n");
    }
    return 0;
}

上面的代码会无限打印hello world，数组大小为3，由于for循环条件错误，会导致a[3]越界访问，在C语言中，所有内存空间是可以自由访问，根据数组寻址公式，a[3]会被定为到某块不属于数组的内存地址上，而该地址恰好是存储变量i的内存地址，于是i被重新赋值为0，代码因此会无限循环下去。

• 数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。在Java中，Java本身就会做越界检查，当发现有越界情况时，就会抛出ArrayIndexOutOfBoundsException数组越界异常。

---

容器(ArrayList)与数组选择

ArrayList：可以将很对数组操作的细节封装起来，并且支持动态扩容，当空间不够时，就会自动将空间自动扩容为1.5倍。

• 扩容操作涉及内存申请与数据搬移，是比较耗费时间的，所以最好在创建ArrayList时就是先指定数据大小。

数组使用场景：

• 效率：Java中ArrayList无法存储基本数据类型，需要将基本类型封装，并且自动装箱与拆箱都有性能的消耗，所以在需要高效率的情况下可以选用数组
• 若数据大小已知，并且对数据的操作非常简单，使用不到ArrayList提供的大部分方法，也可以选择数组
• 在使用多维数组时，用数组可以表现的更加直观
• 在非常底层的开发中，比如开发网络框架，性能优化需要做到极致，这是数组就会由于容器

---

为什么在很多编程语言中数组都从0开始编号？

从数组存储的内存模型来看。“下标”确切的定义就是“偏移（offset）”。如果用a来表示数组的首地址，a[0]就是偏移为0的位置，相当于首地址，a[k]就表示为偏移为k个type_size的位置，因此计算a[k]的内存地址为下面公式：

a[k]_address = base_address + k*type_size

若数组从1开始计算，那么计算数组元素a[k]的内存地址就会变为：

a[k]_address = base_address = (k-1)*type_size

对比两个公式，从1开始编号，每次随机访问数组元素都会多一次减法运算，对于CPU来说，就多了一次减法指令。所以从效率方面来看，从0开始编号比从1开始编号效率能提高一些。

• 但是也有很多语言中数组不是从0开始计数的，比如Matlab。在一些语言中还支持负数下标，比如Python。

---