数组

• 数组下标表示偏移（offset）；
• 例如数组a[]，那么a[0]表示偏移0个位置，也就是首地址；a[i]表示偏移i个type_size位置，所以a[i]的内存地址只需要通过：a[i]_address = base_address + i * type_size;
• 但是如果数组如果从1开始技数，那么数组元素a[i]的内存地址就会变为：a[i]_address = base_address + (i - 1) * type_size；也就是额外需要CPU做一次减法指令。

• 数组是一种线性表的数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据；
• 计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过寻址公式计算出该元素存储的内存地址；

a[i]_address = base_address + i * data_type_size

误区：

• 数组支持随机访问，根据下标随机访问的时间复杂度为O(1)；
• 数组适合查找操作，但是查找的时间复杂度根据的是算法的时间复杂度；比如：根据二分查找，时间复杂度为O(logn)；
• 链表适合删除、插入操作，根据得知插入删除位置的情况下，对应操作的时间复杂度为O(1)。

• 当数组中存储的数据并没有任何规律，数组只是存储数据的集合。就可以直接将第k个位的数据搬移到数组元素的最后，把新的元素直接放入第k个位置；这种情况时间复杂度就会下降到O(1);
• 所以类似于快排的partition的过程，如果当前值小于pivot，swap(left++，i++，nums)；如果当前值的数据大于pivot，swap(right--，i，nums)；当前值的数据等于pivot，i++。这个交换的过程就用到了改进的操作；

• 将多次删除操作集中在一起执行；也就是删除多个数据，比如a、b、c并不是删除一个就搬运一次数据，而是先记录已经删除的数据，只是记录并不是实际的搬移数据，当数组没有更多空间存储数据时，再触发执行一次真正的删除操作，这样就减少了删除操作导致的数据搬移；
• 应用：jvm标记清除垃圾回收算法的核心思想。