从零开始编号的数组

1. 如何实现随机访问

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

数组

两个关键点:线性表、连续的内存空间和相同类型的数据

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。除了数组,链表、队列、栈等也是线性表结构。而与它相对立的是非线性表,比如二叉树、堆、图等。在非线性表中,数据之间并不是简单的前后关系。

连续的内存空间和相同类型的数据。正是因为这两个限制,数组才有了一个堪称「杀手锏」的特性:「随机访问」。但是,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

根据下标随机访问数组元素的时间复杂度为 O(1)。随机访问和查找不一样,即便是排好序的数组,用二分查找,时间复杂度也是 O(logn)。随机访问有个寻址公式:

1
a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小,base_address 是内存块的首地址。

从数组存储的内存模型上来看,「下标」最确切的定义应该是「偏移量」,a[0] 就是偏移为 0 的位置,也就是首地址。

2. 低效的插入和删除

插入和删除需要移动数据,时间复杂度都是 O(n)。

例外情况:

  1. 当数组中存储的元素不要求有序时,如果要插入到第 k 个位置,那么把该位置的数据放到数组末尾,新元素放到第 k 位。比如原数组:[a, b, c, d],把 x 插入到第 2 位,数组变为 [a, x, c, d, b]。
  2. 删除元素时,标记被删除的数据,并不会真正地搬移数据,当数组没有更多的空间时,触发一次真正删除操作,这样就大大减少了数据移动。这其实就是 JVM 标记清除垃圾回收算法的核心思想。

3. 警惕数组访问越界

Java 语言会做数据越界检查,而 C 语言不会。数组越界时一般都会出现莫名其妙的逻辑错误,debug 的难度非常的大。所以写代码的时候一定要警惕数组越界。

4. 容器能否完全代替数组

ArrayList 最大的优势就是可以将很多数组操作的细节封装起来支持动态扩容

每次存储空间不够的时候,ArrayList 会将空间自动扩容为原来的 1.5 倍大小。扩容操作比较耗时,涉及内存申请和数据搬移。所以,如果事先能确定需要存储的数据大小,最好在创建 ArrayList 的时候事先指定数据大小

1
2
ArrayList<String> a = new ArrayList<>(666); // 推荐
ArrayList<String> b = new ArrayList<>(); // 不推荐

更适合用数组的场景:

  1. ArrayList 无法存储基本类型,比如 int,需要封装为 Integer 类,而装箱、拆箱则有一定的性能消耗,所以如果特别关注性能,或者想使用基本类型,就可以选用数组。

  2. 如果数据大小事先已知,并且对数据的操作非常简单,用不到 ArrayList 提供的大部分方法,也可以直接使用数组。

  3. 当表示多维数组时,用数组往往会更加直观。比如 Object[][] array;而用容器的话则需要这样定义:ArrayList array。

本文标题:从零开始编号的数组

文章作者:落英坠露

发布时间:2019年04月17日 - 20:04

最后更新:2019年04月17日 - 22:04

原始链接:https://isuperqiang.cn/2019/04/17/从零开始编号的数组/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏是一种行为艺术