数组

数组三大特性


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

有三个关键词可以辅助我们理解数组,线性表、连续内存空间、相同数据类型

线性表

由零个或多个数据元素组成的有限序列,线性表中的第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱和后继。常见的线性表除了数组,还有链表、队列、栈也是线性表。

有线性表就有非线性表,如:树、堆、图等就是非线性表。

连续内存空间

连续的内存空间,这个存储特性非常重要,它使得硬件对其友好。因为内存空间是连续的,而数组中的每个块的大小又是相等的。所以非常容易推导出公式:数组头存储的物理地址 + 偏移量=指定下标的物理地址。因为直接能够计算出物理地址,因而计算机就无需再寻址可以直接访问内存,因此这个特性也被称为:数组的随机访问特性

我们经常会听到如下结论:数据查询的时间复杂度是O(1),这个结论本身是不太准确的。数组只有在随机访问的情况下,它的时间复杂度才是O(1)。如果是正常的搜索,即使才有性能最优的二分查找,所需的时间复杂度也要O(logn)。

前面讲到了数组连续内存空间带来的益处:提供了随机访问特性。但是有利也有弊,因为要满足数组占用空间的连续性的特性,就需要靠搬迁数据来保证内存空间的连续性

相同的数据类型

这是一个隐性的定义,日常的时候我们几乎不会关注这个点。我们试想一下,如果存储在数组中的数组,包含 int(4)、long(8)、char(2)、byte(1)、double(8)、float(4) 元素的数组,那么计算物理内存地址的时候是多么麻烦的一件事情。

正是因为要去类型一致,所以会存在空间上的浪费。在对内存空间要求高的应用场景下,如:Redis中自建了的ziplist的数据结构,达到了节省空间的目的。

低效的插入删除操作

import java.util.Arrays;

public class Test {
    @org.junit.Test
    public void test() {
        Object[] objects = new Object[5];
        for (int i = 0; i < 5; i++) {
            objects[i] = i;
        }
        System.out.println(Arrays.asList(objects));
        // case 1: 标记清除
        objects[1] = null;
        System.out.println(Arrays.asList(objects));
        // case 2: 执行删除
        Object[] newObjects = new Object[4];
        System.arraycopy(objects, 0, newObjects, 0, 1);
        System.arraycopy(objects, 2, newObjects, 1, 3);
        System.out.println(Arrays.asList(newObjects));
    }
}

// [0, 1, 2, 3, 4]
// [0, null, 2, 3, 4]
// [0, 2, 3, 4]

初始化了样本数据:[0, 1, 2, 3, 4],此时我们希望删除数据1,我们可以怎么操作呢?

  • 直接将对应位置的数值置为 null,删除后的数据如:[0, null, 2, 3, 4],对应代码 case 1。
  • 执行删除操作,然后将后面的数据搬迁,最终数据如:[0, 2, 3, 4],对应代码 case 2。

标记清除的本质是使用空间换时间,我们可以通过触发删除执行的频率来调整性能。删除操作,对应了:新数组申请、数据的拷贝、原数据的释放,相比标记清除算法是一个重量级的操作。

ArrayList 能否完全替代数组?

ArrayList 的优势是官方对 数组的封装,它提供了许多实用的功能,比如:搬迁数据、自动扩容等,种种这些都是手写数组比较困扰的事情。

通常我们的应用场景,使用ArrayList是足够的,但这也不表明数组已无用武之地。因为要使用 ArrayList,就必须要满足 ArrayList 使用的条件。那么在破坏 ArrayList 使用的条件的一些例外情况,则是需要使用数组的。

  • ArrayList 使用泛型,不支持基本类型。高性能场景下(包装类型会自动装箱、拆箱),推荐使用原始类型。
  • 高维数组场景下,选择array[0][0][0][0][0][0][1]对比选择list.get(0).get(0).get(0).get(0).get(0).get(0).get(1),感觉数组更加直观一点。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券