数组

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

  • 数组最大的优点：快速查询。scores[2]
  • 数组最好应用于“索引有语意”的情况。

  • 但并非所有有语意的索引都适用于数组。比如身份证号。

    随机访问

    数组要求连续的内存空间和相同类型的数据。正是因为这两个限制，它才支持“随机访问”。根据下标随机访问的时间复杂度为 O(1)。 :::tips a[i]_address = base_address + i * data_type_size :::

    ArrayList能否完全替代数组？

    ArrayList 的优势

  • 将很多数组操作的细节封装起来

  • 支持动态扩容,不需要关心底层的扩容逻辑

因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。

使用数组更合适的场景

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

对于业务开发，直接使用容器就足够。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果是非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移(offset)”。如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置。 :::tips a[k]_address = base_address + k type_size ::: 如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为 :::tips a[k]_address = base_address + (k-1)type_size ::: 从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

二维数组内存寻址

对于 m n 的数组，a [ i ][ j ] (i < m,j < n)的地址为： :::tips address = base_address + ( i n + j) * type_size :::