谈谈对ArrayList的理解以及扩容机制

2022-11-29 12:36:32 425 其他:www.kaotop.com/it/1077868.html

1.浅谈ArrayList

ArrayList类又称动态数组,同时实现了Collection和List接口,其内部数据结构由数组实现,因此可对容器内元素实现快速随机访问。但因为ArrayList中插入或删除一个元素需要移动其他元素,所以不适合在插入和删除操作频繁的场景下使用。

ArrayList的容量可以随着元素的增加而自动增加,因此不用担心ArrayList容量不足的问题。

ArrayList是非线程安全的。

先看看他的原码吧

1

2

3

4

5

6

7

8

9

10

11

12

13

14

// 默认的容量大小(常量)

privatestaticfinalintDEFAULT_CAPACITY =10;


// 定义的空数组(final修饰,大小固定为0)

privatestaticfinalObject[] EMPTY_ELEMENTDATA = {};


// 定义的默认空容量的数组(final修饰,大小固定为0)

privatestaticfinalObject[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


// 定义的不可被序列化的数组,实际存储元素的数组

transientObject[] elementData;


// 数组中元素的个数

privateintsize;

2.ArrayList有三种构造方法:     1.无参的构造方法

1

2

3

4

// 无参的构造方法

publicArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

可以看出来,当我们直接创建ArrayList时,elementData被赋予了默认空容量的数组。注意,因为默认空容量数组是被final修饰的,此时ArrayList数组是空的、固定长度的,也就是说其容量此时是0,元素个数size为默认值0。

2.根据传入的数值大小,创建指定长度的数组

1

2

3

4

5

6

7

8

9

10

11

// 传容量的构造方法

publicArrayList(intinitialCapacity) {

if(initialCapacity ;0) {

this.elementData =newObject[initialCapacity];

}elseif(initialCapacity ==0) {

this.elementData = EMPTY_ELEMENTDATA;

}else{

thrownewIllegalArgumentException("Illegal Capacity: "+

initialCapacity);

}

}

当initialCapacity ; 0时,会在堆上new一个大小为initialCapacity的数组,然后将其引用赋给elementData,此时ArrayList的容量为initialCapacity,元素个数size为默认值0。

当initialCapacity = 0时,elementData被赋予了默认空数组,因为其被final修饰了,所以此时ArrayList的容量为0,元素个数size为默认值0。

当initialCapacity ; 0时,会抛出异常。


3.通过传入Collection元素列表进行生成

1

2

3

4

5

6

7

8

9

10

11

12

13

// 传入Collection元素列表的构造方法

publicArrayList(Collection;--?extendsE--; c) {

// 将列表转化为对应的数组

elementData = c.toArray();

if((size = elementData.length) !=0) {

// 此处见下面详细解析

if(elementData.getClass() != Object[].class)

elementData = Arrays.copyOf(elementData, size, Object[].class);

}else{

// 赋予空数组

this.elementData = EMPTY_ELEMENTDATA;

}

}

传入Collection元素列表后,构造方法首先会将其转化为数组,将其索引赋给elementData。

如果此数组的长度为0,会重新赋予elementData为空数组,此时ArrayList的容量是0,元素个数size为0。

如果此数组的长度大于0,会更新size的大小为其长度,也就是元素的个数,然后执行里面的程序。大家对里面的代码可能不理解,让我们等会看下面解析。执行完后此时ArrayList的容量为传入序列的长度,也就是size的大小,同时元素个数也为size,也就是说,此时ArrayList是满的。

3.ArrayList的扩容机制

当我们探讨扩容时,肯定要从ArrayList的add方法走起,让我们来看看吧。

1

2

3

4

5

publicbooleanadd(E e) {

modCount++;

add(e, elementData, size);

returntrue;

}

这是最基本的add方法,当然,也是可以说明问题的。可以看到,此add方法的参数就是一个被加元素,moCount是记录ArrayList被修改次数的,可以不用管。然后是另一个add方法,所传的值是被加元素、当前数组和当前数组的元素个数,让我们来看看这个add方法吧。

1

2

3

4

5

6

7

privatevoidadd(E e, Object[] elementData,ints) {

// 判断元素个数是否等于当前容量

if(s == elementData.length)

elementData = grow();

elementData[s] = e;

size = s +1;

}

首先,它判断了元素个数是否等于当前数组的容量,也就是判断当前数组是不是满的,如果当前空间是满的,就需要扩容了,grow函数就是扩容函数了,扩容后再将被加元素加到数组中。

下面我们来看看grow函数是什么样子的:

1

2

3

privateObject[] grow() {

returngrow(size +1);

}

它里面又调用了一个带参的grow函数,参数是当前元素个数+1,也就是当前容量+1。返回的是这个函数的返回值,让我们进一步研究这个带参的函数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

privateObject[] grow(intminCapacity) {

// 获取老容量,也就是当前容量

intoldCapacity = elementData.length;

// 如果当前容量大于0 或者 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA

if(oldCapacity ;0|| elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

intnewCapacity = ArraysSupport.newLength(oldCapacity,

minCapacity - oldCapacity,

oldCapacity ;;1);

returnelementData = Arrays.copyOf(elementData, newCapacity);

// 如果 数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA(容量等于0的话,只剩这一种情况了)

}else{

returnelementData =newObject[Math.max(DEFAULT_CAPACITY, minCapacity)];

}

}

首先,它是记录了一下老容量的大小,然后再进行下面的操作。

如果当前容量大于0,或者当前数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,前面说明过,DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个被final修饰的空数组,在三个构造方法中,只有无参构造方法中elementData被赋予了DEFAULTCAPACITY_EMPTY_ELEMENTDATA。也就是说,这个if语句中不会处理用默认无参构造方法创建的数组的初始扩容情况,那么其余的扩容情况都是由此if语句来处理的。

我们来看一下if里面的操作,先创建一个新的数组,然后将旧数组拷贝到新数组并赋给elementData返回。ArraysSupport.newLength函数的作用是创建一个大小为oldCapacity + max(minimum growth, preferred growth)的数组。

minCapacity是传入的参数,我们上面看过,它的值是当前容量(老容量)+1,那么minCapacity - oldCapacity的值就恒为1,minimum growth的值也就恒为1。

oldCapacity ;; 1的功能是将oldCapacity 进行位运算,右移一位,也就是减半,preferred growth的值即为oldCapacity大小的一半。


4.总结

ArrayList的特点:

1.ArrayList的底层数据结构是数组,所以查找遍历快,增删慢。

2.ArrayList可随着元素的增长而自动扩容,正常扩容的话,每次扩容到原来的1.5倍。

3.ArrayList的线程是不安全的。

ArrayList的扩容:

扩容可分为两种情况:

第一种情况,当ArrayList的容量为0时,此时添加元素的话,需要扩容,三种构造方法创建的ArrayList在扩容时略有不同:

1.无参构造,创建ArrayList后容量为0,添加第一个元素后,容量变为10,此后若需要扩容,则正常扩容。

2.传容量构造,当参数为0时,创建ArrayList后容量为0,添加第一个元素后,容量为1,此时ArrayList是满的,下次添加元素时需正常扩容。

3.传列表构造,当列表为空时,创建ArrayList后容量为0,添加第一个元素后,容量为1,此时ArrayList是满的,下次添加元素时需正常扩容。

第二种情况,当ArrayList的容量大于0,并且ArrayList是满的时,此时添加元素的话,进行正常扩容,每次扩容到原来的1.5倍。

*特别说明:本文来自网络,如有侵权,请联系我们删除,非常感谢!