一. Array如何实现随机访问

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

线性表

  • 线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

image.png

非线性表

  • 非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

image.png

随机访问特性


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

因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

Array 在内存中的表现

  • 1). 长度为10的int类型的数组int[] a =new int[10]

image.png

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

a[i]_address = base_address + i data_type_size
数组元素地址 = 起始元素地址 + (元素所在位置 元素内存容量)

结论

1. Array如何实现的随机访问

只需要知道数组的内存地址和要访问第几个元素, 根据寻址公式可以计算出元素在内存中的位置, 直接进行访问

2. 为什么数组元素的起始位置是 0, 而不是1

根据数组寻址公式, 如果起始位置 为 1 那么寻址公式就会成为 a[i]_address = base_address + ( i - 1) * data_type_size
对于CPU来说，就是多了一次减法指令。

二. 低效的”插入”与”删除”

1. 插入操作

1). 移动位置

假设数组的长度为n，现在，如果我们需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来，给新来的数据，我们需要将第k～n这部分的元素都顺
序地往后挪一位。那插入操作的时间复杂度是多少呢？你可以自己先试着分析一下。如果在数组的末尾插入元素，那就不需要移动数据了，这时的时间复杂度为O(1)。但如果在数组的开头插入元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是O(n)。 因为我们在每个位置插入元素的概率是一样的，所以平均情况时间复杂度为(1+2+…n)/n=O(n)。

2). 交互位置

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移k之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第k个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第k位的数据搬移到数组元素的最后，把新的元素直接放入第k个位置。

假设数组a[10]中存储了如下5个元素：a，b，c，d，e。 我们现在需要将元素x插入到第3个位置。 我们只需要将c放入到a[5]，将a[2]赋值为x即可。 最后，数组中的元素如下： a，b，x，d，e，c。

image.png

2. 删除操作

1). 实时删除

跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为O(1)；如果删除开头的数据，则最坏情况时间复杂度为O(n)；平均情况时间复杂度也为O(n)。

2). 统一删除(标记清除)

实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？
我们继续来看例子。数组a[10]中存储了8个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除a，b，c三个元素。
image.png

    1. 为了避免d，e，f，g，h这几个数据会被搬移三次，我们可以先记录下已经删除的数据。
    1. 每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。
    1. 当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。(JVM标记清除垃圾回收算法的核心思想)

3. 数组的访问越界问题

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

容器能否完全替代数组

高级语言用数组会更合适的情况

  • 1.Java ArrayList无法存储基本类型，比如int、long，需要封装为Integer、Long类，而Autoboxing, Unboxing则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
  • 2.如果数据大小事先已知，并且对数据的操作非常简单，用不到ArrayList提供的大部分方法，也可以直接使用数组。
  • 3.还有一个是我个人的喜好，当要表示多维数组时，用数组往往会更加直观。比如Object[][] array；而用容器的话则需要这样定义：ArrayList array。

    总结

    1 对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。

2 但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。