详解ArrayList

浅浅的花香味﹌ 2023-09-24 18:34 96阅读 0赞

**目录**

1.数据结构

2.初始化

2.1.默认构造

2.2.带参构造

3.扩容

3.1.判断需要多少容量

3.2.判断是否需要扩容

3.3.扩容

4.遍历

5.拷贝

6.序列化

--------------------

**JDK版本：JDK8**

## 1.数据结构 ##

底层使用Object类型的数组实现，线程不安全，添加元素时如果内存已满则会开辟新空间，将原数组copy过去。

transient Object[] elementData;
    
    public boolean add(E var1) {
            this.ensureCapacityInternal(this.size + 1);
            this.elementData[this.size++] = var1;
            return true;
        }

## 2.初始化 ##

### 2.1.默认构造 ###

默认构造是将elementData的引用指向一个final类型的Object\[\]，这个final类型的Object\[\]在声明时指向的是一个空数组，因此采用默认构造实例化出来的ArrayList对象底层的elementData是没有容量的，因此第一次add就需要扩容。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
    public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

**这样设计的目的是节约内存，采用默认构造实例化的对象，在没有用到的时，所有数组都指向一块内存，只有用到时才从新分配。**

### 2.2.带参构造 ###

带参构造才会实例化出一个指定大小的elementData。

![729e81fe85d4485ea4a43662654b8460.png][]

## 3.扩容 ##

每次add时都会调用ensureCapacityInternal方法判断当前数组容量够不够，不够则扩容。

![fa1f6c9fe6f943b5b4b77dfa3c55f851.png][]

ensureCapacityInternal里需要干两件事：

1.  判断需要多少容量，即calculateCapacity方法。
2.  判断是否需要扩容，即ensureExplicitCapacity方法。

![b792e92618b14bd4bd628161a8bcb928.png][]

###  **3.1.判断需要多少容量** ###

这一步主要是判断如果是调用默认构造实例化的数组，需要扩容的大小是多少。

如果是采用默认构造实例化出的ArrayList对象，

elementData指向的是DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA，空间大小为0，

如果需要的空间数量不超过DEFAULT\_CAPACITY（即10个），则扩容出10个空间即可。

如果需要的空间数量超过DEFAULT\_CAPACITY（10个），则扩容出实际需要的空间数量。

![0cbf9ab3176b4b378bbcaf1f25157e66.png][]

### 3.2.判断是否需要扩容 ###

判断需要的容量是否超过当前数组的容量如果超过则扩容

![087a3797c9114e43a7faf18a1c6b8aeb.png][]

### 3.3.扩容 ###

新建一个新数组，长度为老数组的1.5倍（老数组长度+老数组长度右移1位（老数组长度/2^1）），然后将老数组中的元素copy到新数组中。

![1b13b8351bf74a8ab155912902107642.png][]

## 4.遍历 ##

ArrayList的遍历器（iterator）以内部类的方式实现，实现Iterator接口

![f1b6829cb15243d6b73aa06701531102.png][]

三个成员变量：

cursor：游标，用于遍历

lastRet：

expectedModCount:操作数，用来确认数据是否还有一致性

![b99dada8656e4cba943b32eea55ec0ae.png][]

**fail-fast：**

为了保证遍历时数据的一致性，ArrayList的iterator有一个fail-fast机制，

即使用iterator遍历期间，只允许通过iterator来对该对象中的数据进行操作。

![a1617bfda75c4262bde86dad01744705.png][]

而不允许在使用iterator遍历期间，通过其他手段修改对象中的数据。

![5d07ba8263434be386a946eb68f6627a.png][]

## 5.拷贝 ##

![90a91d4a90814cd397b854d797617b7c.png][]

ArrayList实现了Cloneable接口，默认实现浅拷贝，即栈上内容分裂，堆上内容公用。想实现深拷贝，需要手动对成员变量进行一次clone。

## 6.序列化 ##

![cd70b110e4be4cff854975f95c308db2.png][]

ArrayList实现了Serializable接口，

并且重写了writeObject()、readObject()，

elementData\[\]空间很可能没有全部用完，没用到的位置为空，为了避免浪费内存，所以拷贝时只需要将elementData中的非空元素序列化走。

重写的序列化读写方法主要是为了实现上面的想法。

elementData\[\]被transient修饰，不会被序列化。

![a7ce49a390f24e23ad047c183cef75dd.png][]

size记录了前面多少位存有元素，遍历、序列化至size位置即可。

![28c21f5315c54e39ae1ba9791efeb700.png][]

[729e81fe85d4485ea4a43662654b8460.png]: https://img-blog.csdnimg.cn/729e81fe85d4485ea4a43662654b8460.png
[fa1f6c9fe6f943b5b4b77dfa3c55f851.png]: https://img-blog.csdnimg.cn/fa1f6c9fe6f943b5b4b77dfa3c55f851.png
[b792e92618b14bd4bd628161a8bcb928.png]: https://img-blog.csdnimg.cn/b792e92618b14bd4bd628161a8bcb928.png
[0cbf9ab3176b4b378bbcaf1f25157e66.png]: https://img-blog.csdnimg.cn/0cbf9ab3176b4b378bbcaf1f25157e66.png
[087a3797c9114e43a7faf18a1c6b8aeb.png]: https://img-blog.csdnimg.cn/087a3797c9114e43a7faf18a1c6b8aeb.png
[1b13b8351bf74a8ab155912902107642.png]: https://img-blog.csdnimg.cn/1b13b8351bf74a8ab155912902107642.png
[f1b6829cb15243d6b73aa06701531102.png]: https://img-blog.csdnimg.cn/f1b6829cb15243d6b73aa06701531102.png
[b99dada8656e4cba943b32eea55ec0ae.png]: https://img-blog.csdnimg.cn/b99dada8656e4cba943b32eea55ec0ae.png
[a1617bfda75c4262bde86dad01744705.png]: https://img-blog.csdnimg.cn/a1617bfda75c4262bde86dad01744705.png
[5d07ba8263434be386a946eb68f6627a.png]: https://img-blog.csdnimg.cn/5d07ba8263434be386a946eb68f6627a.png
[90a91d4a90814cd397b854d797617b7c.png]: https://img-blog.csdnimg.cn/90a91d4a90814cd397b854d797617b7c.png
[cd70b110e4be4cff854975f95c308db2.png]: https://img-blog.csdnimg.cn/cd70b110e4be4cff854975f95c308db2.png
[a7ce49a390f24e23ad047c183cef75dd.png]: https://img-blog.csdnimg.cn/a7ce49a390f24e23ad047c183cef75dd.png
[28c21f5315c54e39ae1ba9791efeb700.png]: https://img-blog.csdnimg.cn/28c21f5315c54e39ae1ba9791efeb700.png