数组是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
如何实现随机访问?
因为数组是线性表,连续的内存和相同的数据类型使得随机访问成为了可能,我们只需知道初始地址和数据类型就可以计算出任意索引的地址,a[i]_address = base_address + i * data_type_size。
面试常问,数组和链表的区别。很多人都回答说,“链表适合插入、删除,时间复杂度是O(1);数组适合查找,查找的时间复杂度为O(1)”。这样的说法是不准确的,因为即便是大小排列好的数组,用二分查找法,时间复杂度也是O(logn)。正确的表述是,数组支持随机访问,根据下标随机访问的时间复杂度是O(1)。
低效的“插入”和“删除”
ArrayList底层是数组实现,为了保持内存数据的连续性,会导致插入和删除两个操作比较低效。ArrayList在位置k添加和删除数据时,需要将k位置之后的元素做相应的操作,如果操作在数组末尾,时间复杂度是O(1)。如果操作在数组开头,时间复杂度是O(n)。平均时间复杂度为O(n)。如果数组中的数据是有序的,需要按照上面的描述操作。如果数据没有任何规律的话,可以优化一下,为了避免大规模的数据搬移,可以将k位置的数据直接搬移到数组末尾位置,再把新数据放到k位置。删除操作的时候也可以优化一下,可以将要删除的数据标记下来,当数组没有足够的空间时,将标记的数据统一删除,就可以提高很大的性能。也就是JVM标记清除垃圾回收的思想。
数组访问越界问题
Java语言会做数组越界检查,异常为ArrayIndexOutOfBoundsException。
容器能否完全代替数组?
Java中数组和ArrayList相比,ArrayList最大的优势是将很多数组操作的细节封装了起来,另外,还支持动态扩容。初始申请了大小为10的数组,每次扩容1.5倍。不过,因为扩容操作及内存的申请和数据搬移都比较耗时,所以,如果事先能确定数据大小,最好在ArrayList创建是指定数据大小。
数组也有很多优势,ArrayList无法存储基本类型,只能存储封装类型,而装箱和拆箱需要消耗性能。多维数组时,用数组会直观一些。
解答开篇
为什么很多编程语言中,数组要从0开始编号?从数组存储的内存模型上看,下标最确切的定义是偏移量,在计算a[i]的内存地址时,公式为a[i]_address = base_address + i * data_type_size,如果数组从1开始编号,公式为a[i]_address = base_address + (i -1) * data_type_size。对CPU而言,就多了一次减法指令。最主要的原因应该是历史问题,C语言的设计者使用了0开始编号,后续的很多语言也就沿用了这个规矩。