仔细想想,平时在用的时候,Java中的那些数据结构,本质上都是数组+引用。HashMap就不说了,链表呢?每个节点可以看成是一个length=1的数组。
数组在定义的时候就携带了一些枷锁:
- 使用前先申请确定的内存空间;
- 分配空间后,大小固定,不能再改变(数据溢出问题)
- 内存空间必须是连续的。在内存中有空间连续性的表现,中间不会存在其他程序需要调用的数据,为此数组的专用内存空间。
当数组在初始化后,其需要的连续内存空间就分配确定了,因此其起始内存地址是已知的,数组第一个元素(索引=0)的内存位址称为第一位址或基础位址。那么既然我们知道第一个索引位置的内存地址,由于连续性,其他索引的内存地址便可以直接通过简单一元一次函数(所谓线性函数)得出来。
例如,索引为0到3的32位(4x8bit)整数类型数组,可存储在内存位址为2000,2004,2008,2012的4个位置中,因此索引=i的元素,在内存中的地址就为2000+4×i,
也就是说只要知道了数组的下标(索引),就可以快速计算出其内存地址,也就是数组通过索引查询时间复杂度为O(1)。所以快。而链表所有的节点不在一个连续内存空间中,没这个特性,需要一个节点一个节点寻找,所以就相对不快。